Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | portale.in, portale.out | Sursă | Summer Challenge 2021 |
| Autor | Luca Perju Verzotti | Adăugată de |  comisia summer 2k21 •summer21 |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Portale
Work in progress
Intr-un alt episod in care Rick si Morty pleaca sa salveze Atlantida, Citadela se afla, din nou, in pericol datorita unui Portal Gun pierdut. Rezistenta Morty-lor, obtinand aceasta arma, planuieste o revolutie, creand un sistem de portale, sub forma unui arbore ascuns, intre n locatii principale (numerotate de la 1 la n).
Stiind ca dimensiunea Citadelei este suprasolicitata, Militia Rick poate schimba fortat reteaua de portaluri pentru a o determina. Astfel, aceasta poate introduce intr-un Portal Gun coordonatele a doua locatii cheie (a,b) determinand una din doua posibilitati: arma returneaza (0,0) semn ca un portal deja exista intre a si b ori returneaza un dublet (x,y) semnaland ca un nou portal se va deschide intre a si b, in timp ce, portalul dintre x si y se va inchide pentru a preveni aparitia unui ciclu, mentinand forma de arbore a retelei.
Ajutati Militia Rick sa gaseasca sistemul de portaluri pentru a preveni ranirea inutila a Morty-lor.
Interactiune
Initial se citeste din stdin numarul T reprezentand numarul de teste.
Pentru fiecare test se citeste, apoi, N numarul de noduri ale arborelui.
Programul vostru are voie să pună query-uri scriind în standard output:
- "? a b" reprezentând introducerea unui dublet in Portal Gun.
Dupa fiecare astfel de query, interactorul va raspunde in stdin astfel:
- "0 0": daca muchia (a,b) exista deja in arbore.
- "x y": daca muchia (a,b) nu exista, dubletul (x,y) reprezinta muchia care se va sterge din graf odata cu adaugarea muchiei (a,b) pentru a pastra forma de arbore.
După ce aţi aflat muchile arborelui, afişati "!" pe o singura linie urmat de n-1 linii cu "a b" semnificand ca exista o muchie intre a si b.
După fiecare query si dupa ce afisati rezultatul unui test, trebuie sa afişaţi '\n' şi să daţi flush la standard output. Pentru a da flush vă puteţi folosi de următorul tabel:
| Limbaj | C/C++ | Pascal | Python | Java | Rust |
|---|---|---|---|---|---|
| Header necesar | import sys | use std::io::{self,Write}; | |||
| Functie | fflush(stdout) sau cout.flush() | flush(output) | sys.stdout.flush() | System.out.flush() | io::stdout().flush().unwrap(); |
Restricţii si precizari
- ... ≤ ... ≤ ...
Punctare
Exemplu
| Stdin | Stdout | Explicatie | |
|---|---|---|---|
| 2 3 | |||
| This is some text written on multiple lines. | This is another text written on multiple lines. | ||
Explicaţie
...
