Zoznam úloh

4. Ísť po počítač

Mladý Emanuel má jasný životný cieľ – kúpiť si nový, neuveriteľne výkonný herný počítač, aby sa mohol hrať s Jozefom online hry. To však má jeden háčik - nie je medzi nimi natiahnutá sieť, teda nevedia spolu rozumne rýchlo komunikovať. Musí sa teda vybudovať nová optická sieť medzi nimi.

Sieťari vybudujú a otvoria stanicu $i$, až keď do nej vedie aspoň $r_i$ plne dokončených optických liniek, skôr sa im to neoplatí. Otvorenie stanice zároveň naštartuje ďalších, ktorí sa hneď pustia do budovania všetkých zvyšných plánovaných liniek vedúcich z nej. Stavba každej linky trvá rok, takže sa spojazdní až od nasledujúceho roka. Zopár nadšených staníc je otvorených odjakživa a všetky linky z nich sú už dávno hotové.

Pomôžte Emanuelovi zistiť, za koľko rokov sa najskôr dokáže spojiť s Jozefom a hrať sa svoju obľúbenú hru - kedy si má ten herný počítač kúpiť.

Úloha

Máme danú krajinu s $n$ stanicami očíslovanými od $0$ po $n - 1$ a $m$ obojsmernými linkami medzi nimi. Každá stanica $i$ má stanovený limit otvorenia $r_i \geq 0$.

  • Každá stanica s limitom $r_i = 0$ je otvorená odjakživa a všetky linky vedúce z nej sú už dokončené, prevádzkyschopné od roku $0$.
  • Každá ostatná stanica sa otvorí v najskoršom roku, v ktorom je aspoň $r_i$ liniek vedúcich z nej dokončených.

Keď sa takáto stanica otvorí v roku $y$, začne stavať všetky svoje linky, ktoré doteraz neboli dokončené, a tie sú prevádzkyschopné od roku $y + 1$. Linku medzi dvoma stanicami teda postaví tá z nich, ktorá sa otvorí skôr. Stanica, ku ktorej nikdy nepovedie aspoň $r_i$ dokončených liniek, sa neotvorí nikdy.

Emanuel je napojený k stanici $s$ a Jozef býva pri stanici $t$. Dáta môžu tiecť iba cez už postavené linky a už otvorené stanice. Zistite, za koľko najmenej rokov bude Emanuel vedieť komunikovať s Jozefom cez novú optickú sieť.

Formát vstupu

V prvom riadku vstupu sú štyri celé čísla $n, m, s, t$ ($1 \leq n \leq 200\,000$, $0 \leq m \leq 200\,000$, $0 \leq s, t \leq n - 1$), kde $n$ je počet staníc, $m$ počet liniek, $s$ Emanuelova stanica a $t$ Jozefova stanica. V druhom riadku je $n$ celých čísel $r_0, r_1, \dots, r_{n-1}$ ($0 \leq r_i \leq n$), kde $r_i$ udáva limit otvorenia stanice $i$. Nasleduje $m$ riadkov, z ktorých každý obsahuje dve celé čísla $u$ a $v$ ($0 \leq u, v \leq n - 1, u \neq v$), čo znamená, že medzi stanicami $u$ a $v$ je naplánovaná obojsmerná linka. Medzi žiadnymi dvoma stanicami nevedie viac ako jedna linka a žiadna linka nevedie zo stanice do nej samej.

Formát výstupu

Vypíšte jedno celé číslo – za koľko najmenej rokov Emanuel vie začat komunikovať s Jozefom, teda vie poslať správu zo stanice $s$ do stanice $t$. Ak sa to nestane nikdy, vypíšte $-1$.

Hodnotenie

V jednotlivých testovacích sadách platia nasledujúce obmedzenia:

Sada $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$
$1 \leq n, m \leq$ $50$ $1\,000$ $200\,000$ $200\,000$ $200\,000$ $200\,000$ $100\,000$ $200\,000$

Navyše v 3. sade platí, že všetky $r_i \leq 1$, vo 4. sade tvoria trate súvislý strom, teda $m = n - 1$, v 5. sade platí, že súčet všetkých $r_i$ nepresiahne $2\,000$, a v 6. sade sa zaručene každá stanica raz otvorí a odpoveď nie je $-1$.

Príklady

Vstup

5 6 0 4
0 1 2 1 2
0 1
0 3
1 2
3 2
2 4
1 4

Výstup

2

Stanica 0 v roku 0 sprevádzkuje linky do staníc 1 a 3, čím obe okamžite otvorí. V roku 1 stanice 1 a 3 dokončia svoje linky do stanice 2 a otvoria ju, vďaka čomu sa v roku 2 dokončí aj druhá linka do cieľovej stanice 4 a Emanuel do vie začat komunikovať s Jozefom po trase $0 \to 1 \to 2 \to 4$.

Vstup

5 4 0 4
0 1 3 0 1
0 1
1 2
3 4
2 4

Výstup

-1

Stanica 0 v roku 0 otvorí stanicu 1 a stanica 3 rovnako otvorí stanicu 4. Spojovacia stanica 2 však vyžaduje až 3 dokončené trate, no vedú do nej iba 2 trate (zo staníc 1 a 4), takže sa nikdy neotvorí a Emanuel sa z Jozefom nikdy nespojí.

Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty