Fişierul intrare/ieşire:marmelada.in, marmelada.outSursăAlgoritmiada 2009, runda 3
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Marmelada

Primarul judetului Marmelada trebuie sa refaca in totalitate reteaua stradala. In judet exista N orase numerotate cu numere naturale de la 1 la N. Se mai si stiu cele M sosele care trebuie construite, o sosea leaga direct doua orase si se poate circula pe ambele sensuri. Primarul trebuie sa decida acum ce lungime sa aibe fiecare sosea. Firma de constructii s-a oferit sa construiasca M sosele de lungimi C1, C2 ... CM si i-a lasat libertatea primarului de a decide pentru fiecare sosea din judet ce lungime sa aibe (altfel spus trebuie realizata o bijectie intre multimea de lungimi si multimea de sosele). Primarul are doua orase preferate, S si D si doreste ca dupa construirea soselelor sa existe cel mai scurt drum posibil intre cele doua orase. Un drum este o succesiune de sosele astfel incat oricare doua sosele consecutive au un oras in comun. Ajutati primarul orasului si determinati pentru fiecare sosea ce leaga doua orase ce lungime trebuie sa aiba.

Date de intrare

Fişierul de intrare marmelada.in contine pe prima linie patru numere naturale separate de un spatiu, N, M, S si D, avand semnificatia din enunt. Urmeaza apoi M linii, fiecare linie continand doua numere separate de un singur spatiu a si b avand semnificatia ca trebuie construita o sosea intre orasele a si b. Pe linia M+2 din fisier se afla M numere naturale C1, C2 ... CM, avand semnificatia din enunt.

Date de ieşire

În fişierul de ieşire marmelada.out se vor afisa M numere naturale cuprinse intre 1 si M (fiecare numar pe cate o linie). Daca al i-lea numar din fiser este j inseamna ca soseaua avand indicele i (soselele sunt numerotate de la 1 la M in ordinea in care apar in fisierul de intrare) i-a fost atribuita lungimea Cj. Daca exista mai multe solutii se poate afisa oricare dintre ele.

Restricţii

  • 1 ≤ N, M ≤ 100 000
  • Lungimile soselelor sunt numere naturale din intervalul [1, 10 000]
  • Soselele sunt numerotate de la 1 la M in ordinea in care apar in fisierul de intrare
  • Va exista mereu cel putin un drum intre S si D
  • Pot exista mai multe sosele intre doua orase si pot exista sosele ce leaga un oras cu el insusi

Exemplu

marmelada.inmarmelada.out
4 4 1 4
1 2
2 4
1 3
3 4
1 2 3 4
1
2
3
4

Explicaţie

Soseaua 1-2 are lungimea 1 iar soseaua 2-4 are lungimea 2, deci exista un drum de lungime 3 intre orasele 1 si 4. O solutie posibila era si 3 4 1 2. Nu exista o alta repartizare a lungimilor soselelor astfel incat sa se obtina un drum de lungime mai mica intre 1 si 4.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content