Fişierul intrare/ieşire:dw.in, dw.outSursăInfoOltenia 2018 - Clasele 11 - 12 Echipe
AutorBogdan IordacheAdăugată deinfoolteniaInfo-Oltenia 2018 infooltenia
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Doctor Who

"People assume that time is a strict progression of cause to effect, but actually, from a nonlinear, non-subjective viewpoint, it's more like a big ball of wibbly-wobbly, timey-wimey... stuff.."

Doctorul trebuie să salveze universul… din nou. Cu ajutorul T.A.R.D.I.S.-ului acesta poate ajunge în mai multe momente ale istoriei, pe care le poate influenţa pentru a salva prezentul. Cum timpul are o structura complexă, unul din modurile în care poate fi reprezentat este printr-un graf orientat în care nodurile reprezintă evenimente, iar muchiile relaţii de tip cauză-efect. Pentru orice eveniment i, notăm cu vi importanţa acestuia.
Fie x1, x2, …, xk o secvenţă de evenimente. Doctorul poate influenţa această secvenţă dacă şi numai dacă sunt îndeplinite următoarele condiţii: pentru orice i (1 ≤ ik-1), vxi < vxi+1, iar în reprezentarea timpului ca graf orientat, avem drum de la nodul corespunzător lui xi la nodul corespunzător lui xi+1 (prin existenţa unui drum de la a la b înţelegem că se poate ajunge de la a la b, mergând doar pe muchii din graf şi numai în sensul corespunzător).

Doctorul trebuie să influenţeze cât mai multe evenimente pentru a salva universul, aşa că vă roagă pe voi să găsiţi lungimea maximă a unei secvenţe de evenimente ce respectă restricţiile de mai sus.

Date de intrare

Prima linie a fişierului dw.in va conţine două numere naturale N şi M, reprezentând numărul total de evenimente şi numărul de relaţii cauză-efect.
Pe cea de a doua linie, se vor găsi N numere naturale, al i-lea dintre acestea reprezentând importanţa celui de-al i-lea eveniment.
Pe fiecare dintre următoarele M linii, se vor găsi două numere naturale, x şi y, cu semnificaţia că există o muchie orientată de la nodul corespunzător evenimentului x la nodul corespunzător evenimentului y (evenimentele sunt indexate cu numere naturale de la 1 la N).

Date de ieşire

Pe prima linie a fişierului dw.out afişaţi K, lungimea maximă a unei secvenţe valide de evenimente.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 200.000
  • În toate testele graful orientat respectă următoarea condiţie: oricare ar fi 3 noduri A, B, C, dacă există drum de la A la C si de la B la C, atunci există drum de la A la B, sau de la B la A, sau ambele.
  • În toate testele există un nod de la care se poate ajunge la oricare alt nod.
  • pentru 10% din teste 1 ≤ N ≤ 20
  • pentru 40% din teste 1 ≤ N ≤ 1000, 1 ≤ M ≤ 2000
  • pentru 60% din teste graful este aciclic
  • subtask-urile de mai sus se pot suprapune
  • importanta unui eveniment se afla in intervalul [1, 100.000]

Exemplu

dw.indw.out
5 8
1 3 1 4 2
1 2
2 3
3 4
4 2
4 3
4 5
3 5
1 5
3

Explicaţie

Se aleg nodurile 1, 2 şi 4 cu valorile respective 1, 3 şi 4.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?