Zadanie

Samo má doma veľa hadov. Chcel si kúpiť veľa hadíc (samíc hadov), aby neskôr mal aj veľa háďat. Tak si ich objednal z nemenovaného internetového obchodu, ale keď mu prišla zásielka, postihlo ho nepríjemné prekvapenie. Miesto hadíc (samíc hadov) mu omylom poslali hadice (hadice). No čo už, pomyslel si, nájdem si teda inú zábavu. A našiel si inú zábavu.

Úloha

Máme sústavu \(n\) nádob poprepájaných hadičkami. Na začiatku sú všetky nádoby prázdne. Nad prvou nádobou je kohútik, cez ktorý sa do tohto systému napúšťa voda. Funguje princíp spojených nádob.

Hadičkou začne voda pretekať, až jej hladina v niektorej z incidentných nádob dosiahne úroveň najvyššieho bodu danej hadičky. Vtedy sa rast hladiny v tej nádobe zastaví a začne sa napúšťať tá druhá a cez ňu prípadne ďalšie. Až sa hladiny vyrovnajú, zostanú vyrovnané navždy a ak napúšťanie pokračuje, budú stúpať súčasne.

Vašou úlohou je zistiť, z ktorej nádoby voda pretečie.

Formát vstupu

Na prvom riadku sú dve medzerou oddelené čísla \(n\) a \(k\) – počet nádob a počet hadičiek. Nádoby sú očíslované od \(1\) po \(n\).

Na druhom riadku je \(n\) čísel, \(d_1\) až \(d_n\) – výšky, v ktorých sa nachádza dno danej nádoby. Na treťom riadku je \(n\) čísel, \(h_1\) až \(h_n\) – výšky horných okrajov jednotlivých nádob.

Nasleduje \(k\) riadkov popisujúcich jednotlivé hadičky. Na \(i\)-tom riadku je päť medzerou oddelených celých čísel, \(x_i\), \(y_i\), \(a_i\), \(b_i\), \(c_i\). Táto hadica spája nádoby \(x_i\) a \(y_i\). Platí \(x_i \neq y_i\). Pripája sa do nádoby \(x_i\) vo výške \(a_i\) a do nádoby \(y_i\) vo výške \(b_i\). Jej najvyšší bod je vo výške \(c_i\). Platí \(a_i < c_i > b_i\) a koncové body hadice sú vyššie ako dno nádoby ku ktorej sa pripájajú. Koncový bod však môže byť vyššie ako horný okraj nádoby, v takomto prípade cez neho môže do nádoby voda iba natekať (vytekať nie).

Medzi tou istou dvojicou nádob môže viesť aj viac ako jedna hadička.

Všetky výškové údaje sú celé čísla z intervalu od \(0\) do \(10^9\) vrátane a sú navzájom rôzne.

Formát výstupu

Vypíšte jedno číslo, číslo nádoby ktorá pretečie.

Hodnotenie

Je 8 sád vstupov. Platia v nich nasledujúce obmedzenia:

Sada 1–2 3–5 6 7–8
\(1 \leq n \leq\) \(100\) \(1\,000\) \(10\,000\) \(100\,000\)
\(1 \leq k \leq\) \(1\,000\) \(10\,000\) \(100\,000\) \(100\,000\)

Príklad

Input:

3 3
20 10 0
90 50 60
1 2 25 15 35
2 3 30 40 45
1 3 70 75 80

Output:

2

Keď hladina v nádobe 1 dosiahne výšku 35, začne sa napĺňať nádoba 2. Potom čo aj v nádobe 2 dosiahne výšku 35, voda začne stúpať v oboch nádobách súčasne, až kým nedosiahne výšku 45, kedy sa začne napúšťať nádoba 3. Keď voda aj v nej dosiahne výšku 45, začne voda stúpať vo všetkých nádobách súčasne, až dokým nedosiahne výšku 50, keď začne pretekať cez okraj nádoby 2 a hladina už ďalej stúpať nebude nikde.

Input:

5 6
30 50 70 40 90
300 280 290 210 110
1 2 220 200 230
3 4 100 120 170
3 4 130 60 150
4 5 160 190 260
1 5 180 250 270
4 2 140 80 240

Output:

4

Hoci je nádoba 5 najnižšia, voda sa do nej nedostane, skôr sa vyleje z nádoby 4.

V tejto úlohe sme mali sústavu spojených nádob poprepájaných hadičkami, pričom do prvej nádoby sa napúšťala voda. Našou úlohou bolo zistiť, z ktorej nádoby sa voda vyleje.

Pozorovania

Môžme si všimnúť, že mnohé informácie, ktoré na vstupe dostaneme, pre nás vlastne nemajú žiaden význam. Voda začne tiecť z jednej nádoby do druhej, keď hladina dosiahne výšku najvyššieho bodu hadice, ktorou sú prepojené. Výšky koncových bodov hadice na to nemajú žiaden vplyv, môžme ich teda ignorovať. Výška dna nádoby tiež nič neovplyvňuje.

Pomalé riešenie

Budeme si pamätať, v ktorých nádobách už je voda, a v ktorých ešte nie.

Zakaždým preiterujeme všetky hadičky, aby sme našli tú, ktorá spája už zaplavenú nádobu s ešte nezaplavenou a spomedzi všetkých takýchto má najnižší vrchol. To nám povie, ktorá nádoba sa najbližšie zaplaví. Ak je však najnižšia výška vrchného okraja spomedzi už zaplavených nádob nižšia ako vrchol tejto hadičky, voda sa vyleje z najnižšej spomedzi už zaplavených nádob.

Časová zložitosť takéhoto riešenia je \(O(n \cdot k)\).

Vzorové riešenie

Problém s predchádzajúcim riešením je, že zakaždým, keď sme chceli vedieť, do ktorej nádoby voda ďalej potečie, nám to zabralo veľmi veľa času. Tu nám pomôže halda.

Použijeme haldu, na ktorej budú udalosti dvoch typov, pretečenie cez okraj nádoby a pretečenie z jednej nádoby do druhej. Halda bude utriedená podľa výšky, ktorú musí voda dosiahnuť, aby udalosť nastala (teda pri udalostiach prvého typu výška nádoby, a pri udalostiach druhého typu výška najvyššieho bodu hadice). Udalosť s najnižšou výškou bude na vrchu haldy.

Na začiatku máme v halde iba udalosti, ktoré sa týkajú prvej nádoby.

Simulácia teda bude vyzerať takto. Zakaždým z haldy vyberieme udalosť s najnižšou výškou. Ak je to pretečenie cez hadičku do druhej nádoby, v ktorej ešte voda nie je, udalosti súvisiace s touto nádobou (pretečenie cez jej okraj, a cez hadičky do susedných nádob) pridáme do haldy a zapamätáme si, že tu je voda. Ak je to pretečenie cez okraj, máme odpoveď, ďalej už simulovať nemusíme.

Časová zložitosť

Jedna operácia vkladania alebo vyberania z haldy s \(s\) prvkami nám zaberie \(O(\log s)\). Na halde môže byť najviac \(2k+n\) udalostí (pre každú nádobu pretečenie cez okraj a pre každú hadičku pretečenie do jednej alebo druhej strany). Koľko operácii budeme robiť? Určite nie viac ako \(4k+2n\), pretože každú udalosť môžme najviac raz vložiť a raz vybrať z haldy. Časová zložitosť teda bude \(O((4k+2n)\cdot \log(4k+2n)) = O((n+k)\cdot \log(n+k))\).

Pamäťová zložitosť

Okrem vecí zo vstupu si potrebujeme držať v pamäti ešte našu haldu (\(O(n+k)\)) a jedno pole, na to, aby sme vedeli, v ktorých nádobách už je voda (\(O(n)\)), čo je dokopy \(O(n+k)\).

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main(){
    int n,k,_;
    cin >> n >> k;
    for(int i=0; i<n; i++){
        cin>>_;
    }
    vector<int> hor(n);
    for(int i=0; i<n; i++){
        cin >> hor[i];
    }
    vector<vector<pair<int,int>>> graf(n);
    for(int i=0; i<k; i++){
        int x,y,c;
        cin >> x >> y >> _ >> _ >> c;
        x--; y--;
        graf[x].push_back(pair<int,int>(y,c));
        graf[y].push_back(pair<int,int>(x,c));
    }

    vector<bool> voda(n);
    priority_queue<pair<int,pair<bool,int>>,std::vector<pair<int,pair<bool,int>>>,std::greater<pair<int,pair<bool,int>>>> halda;

    voda[0] = true;
    for(unsigned int i=0; i<graf[0].size(); i++){
        pair<int,int> h = graf[0][i];
        halda.push(pair<int,pair<bool,int>>(h.second, pair<bool,int>(false,h.first)));
    }
    halda.push(pair<int,pair<bool,int>>(hor[0], pair<bool,int>(true,0)));

    while(true){
        pair<bool,int> event = halda.top().second;
        halda.pop();
        if(event.first){
            cout<<event.second+1<<'\n';
            return 0;
        }else{
            int v = event.second;
            if (voda[v]){
                continue;
            }
            voda[v] = true;
            for(unsigned int i=0; i<graf[v].size(); i++){
                pair<int,int> h = graf[v][i];
                halda.push(pair<int,pair<bool,int>>(h.second, pair<bool,int>(false,h.first)));
            }
            halda.push(pair<int,pair<bool,int>>(hor[v], pair<bool,int>(true,v)));
        }
    }
}
from heapq import heappush,heappop

n,k = map(int,input().split())
input()
hor = list(map(int,input().split()))

graf = [[] for _ in range(n)]
for _ in range(k):
    x,y,_,_,c = map(int,input().split())
    x -= 1
    y -= 1
    graf[x].append((y,c))
    graf[y].append((x,c))

voda = [False] * n
halda = []

voda[0] = True
for sused,c in graf[0]:
    heappush(halda, (c, False, sused))
heappush(halda, (hor[0], True, 0))

while True:
    _, pretieklo, v = heappop(halda)
    if pretieklo:
        print(v+1)
        exit()
    else:
        if voda[v]:
            continue
        voda[v] = True
        for sused,c in graf[v]:
            heappush(halda, (c, False, sused))
        heappush(halda, (hor[v], True, v))

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.