루미 알고리즘

#1426다이아Primärfaktor

PO 2017 훈련 캠프코딩출제 Nils Gustafsson스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GruppPoängvärdeGränser
125n ≤ 1000, m ≤ 4000
225n ≤ 100000, grafen är en linje, dvs kanterna är (1,2),(2,3) … (n-1,n)
350n ≤ 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 

출처 표기

출처: Programmeringsolympiaden 2017년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.