Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | arborigami.in, arborigami.out | Sursă | ONI 2022 Baraj Seniori Ziua 2 |
Autor | Vlad Gavrila | Adăugată de | Lorintz Alexandru •Alex_tz307 |
Timp execuţie pe test | 1 sec | Limită de memorie | 262144 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Miyuki vrea să împăturească arborigami
Kaguya, vicepreşedintele consiliului de studenţi, este răcită. Miyuki vrea, cum este tradiţional, să îi ofere cadou o mie de cocori de hârtie. Poate nu o mie... (prea exagerat pentru o simplă răceală), şi poate nu cocor... (prea tradiţional şi oricum nu am hârtie de origami...). Un arbore stea ar trebui să fie ideal!
Miyuki are un arbore (graf conex aciclic) format din N noduri numerotate de la 1 la N. El doreşte să îl transforme într-un arbore stea de dimensiune N − K, adică un graf conex aciclic care are cel puţin N − K − 1 frunze (noduri cu exact 1 vecin).
Pentru a transforma arborele său într-un arbore stea, Miyuki va efectua K operaţii de împăturire a câte două noduri. Pentru a i-a operaţie de împăturire, Miyuki:
- Alege două noduri distincte şi existente în acel moment în arbore.
- Notează cu V mulţimea vecinilor nodurilor şi (nodurile care au o muchie directă către cel puţin unul dintre sau ).
- Şterge din V nodurile şi , dacă acestea erau prezente.
- Şterge din arbore nodurile şi , cât şi muchiile care aveau cel puţin un capăt într-unul din nodurile şi .
- Adaugă în arbore un nod cu numărul N + i.
- Adaugă muchii între nodul N + i şi fiecare din nodurile din mulţimea V.
Date de intrare
Fişierul de intrare arborigami.in ...
Date de ieşire
În fişierul de ieşire arborigami.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
arborigami.in | arborigami.out |
---|---|
This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...