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ť.
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$.
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ť.
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.
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$.
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$.
5 6 0 4
0 1 2 1 2
0 1
0 3
1 2
3 2
2 4
1 4
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$.
5 4 0 4
0 1 3 0 1
0 1
1 2
3 4
2 4
-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í.
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete