Fişierul intrare/ieşire:ecotraseu.in, ecotraseu.outSursăONIS 2015, Runda 3
AutorVlad ManeaAdăugată devlad.maneaVlad Manea vlad.manea
Timp execuţie pe test2.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ecotraseu

În centrul vechi al oraşului Copenhaga nu circulă maşini. De aceea, companiile de turism parchează autobuzele de hop-on hop-off în apropierea intersecţiilor de la margine. Oraşul este modelat astfel încât între oricare două intersecţii există un drum simplu unic. Intersecţiile de la extremitatea unei singure străzi sunt staţiile de autobuz, iar cele care leagă mai multe străzi - obiective turistice.

Fiecare stradă din Copenhaga are asociat un avantaj. De exemplu, pe străzile cu avantaj negativ sunt strategic poziţionaţi tinerii de la organizaţiile nonprofit în căutare de donaţii, iar pe străzile cu avantaj pozitiv - magazinele cu bere aproape gratis. Suma avantajelor străzilor care formează un drum este avantajul acelui drum. Un drum simplu de avantaj 0, cu staţii de autobuz distincte în extremităţi, se numeşte ecotraseu.

Companiile de turism ştiu că în oraş există un ecotraseu, dar ar vrea să gasească şi extremităţile unuia pentru a parca autobuzele în ele.

Date de intrare

Pe prima linie a fişierului de intrare ecotraseu.in se găseşte numărul T de teste. Fiecare test începe apoi pe linie nouă. Pe prima linie a unui test se găseşte numărul N de intersecţii. Pe următoarele linii se găsesc triplete de numere separate prin spaţiu, unde fiecare triplet de forma x y a reprezintă cele două intersecţii x şi y, urmate de avantajul străzii a. Fişierul se termină cu caracterul sfârşit de linie.

Date de ieşire

Fişierul de ieşire ecotraseu.out conţine T linii cu câte două numere separate prin spaţiu, care indică extremităţile unui ecotraseu pentru un test dat. Fişierul se termină cu caracterul sfârşit de linie.

Restricţii

  • 1 <= x, y <= N <= 105
  • |a| <= 104
  • 1 <= T <= 20
  • Cel mult 10 teste au 1 <= N <= 104
  • Cel mult 10 teste au 104 <= N <= 105

Exemplu

ecotraseu.inecotraseu.out
2
2
1 2 0
3
1 2 -1
1 3 1
1 2
2 3

Explicaţie

Sunt două teste. În primul test, drumul 1 - 2 este un ecotraseu. În al doilea test, drumul 2 - 1 - 3 este un ecotraseu.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content