스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
“Vilket är världens högsta berg? Den högsta punkten på Mount Everests topp. OK, men vilket är världens näst högsta berg? Den näst högsta punkten på Mount Everests topp såklart.” Med den här logiken blir listan på världens högsta berg väldigt dum. Men det finns en lösning, man introducerar begreppet primärfaktor. Primärfaktorn hos ett berg är det minsta avståndet i höjdled man måste gå ner från berget för att komma till ett strikt högre berg. Det funkar som ett slags mått på hur självständigt ett berg är, och om man rensar bort alla punkter med primärfaktor mindre än 200 m, så blir man av med alla fåniga små berg som egentligen sitter på högre berg. Det här problemet handlar om att hitta alla primärfaktorer i en graf.
Vi har en graf med n noder och m kanter, där varje nod i har ett icke-negativt heltal h(i), nodens höjd. En nods primärfaktor P(i) är den minsta höjden man måste gå ner från noden för att komma till en nod med strikt högre höjd. Här kommer en lite mer matematisk definition: Låt G(i) vara mängden av alla vägar från noden i till någon annan nod j sådan att h(j) > h(i). Primärfaktorn hos i definieras som
P(i) = min_{γ ∈ G(i)} { h(i) - min_{k ∈ γ}(h(k)) }
Om G(i) = ∅, dvs om det överhuvudtaget inte går att ta sig till en nod med högre höjd, så säger vi att primärfaktorn är h(i).
Givet en graf, hitta alla noders primärfaktorer.
Indata
En rad med två heltal, n och m. En rad med n heltal 0 ≤ h(i) ≤ 10^9, nodernas höjder. m rader med två heltal, a och b (1 ≤ a,b ≤ n), vilket betyder att en kant går mellan noderna a och b.
Utdata
En rad med n heltal, nodernas primärfaktorer.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
| Grupp | Poängvärde | Gränser |
| 1 | 25 | n ≤ 1000, m ≤ 4000 |
| 2 | 25 | n ≤ 100000, grafen är en linje, dvs kanterna är (1,2),(2,3) … (n-1,n) |
| 3 | 50 | n ≤ 100000, m ≤ 400000 |
예제
예제 1
5 4 3 2 5 1 6 1 2 2 3 3 4 4 5
1 0 4 0 6
예제 2
6 7 1 2 3 4 5 6 1 2 1 3 1 6 2 3 2 4 2 5 3 4
0 0 0 2 4 6