Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | marmelada.in, marmelada.out | Sursă | Algoritmiada 2009, runda 3 |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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 soselor 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 aibe ea.
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.
h2. Restricţii
- 1 ≤ N, M ≤ 100 000
- Lungimile soselelor sunt numere naturale mai mici decat 10 000
- Soselele sunt numerotate de la 1 la M in ordinea in care apar in fisierul de intrare
- Mereu exista cel putin un drum intre S si D
Exemplu
| marmelada.in | marmelada.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.
