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 ai şi bi existente în acel moment în arbore.
* Notează cu V mulţimea vecinilor nodurilor ai şi bi (nodurile care au o muchie directă către cel puţin
unul dintre ai sau bi).
* Şterge din V nodurile ai şi bi, dacă acestea erau prezente.
* Şterge din arbore nodurile ai şi bi, cât şi muchiile care aveau cel puţin un capăt într-unul din
nodurile ai şi bi.
* 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
...
