Diferente pentru problema/marmelada intre reviziile #15 si #21

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="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 $C{~1~}, C{~2~} ... C{~M~}$ 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.
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 $C{~1~}, C{~2~} ... C{~M~}$ 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.
h2. Date de intrare
h2. Restricţii
* $1 ≤ N, M ≤ 100 000$
* Lungimile soselelor sunt numere naturale mai mici decat $10 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

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3659