5. Neprísť do školy (vzorové riešenie) - Korešpondenčný seminár z programovania

Zadanie

V Krajine Školských Povinností (KŠP) sa zaviedol nový sviatok, takzvaný “opposite day” – opačný deň – v ktorý by sa všetko malo robiť naopak.

Študenti Feľmi Kvalitnej Školy (FKŠ) sa zhodli, že to teda nesmú prísť do školy. Ľahké splniť, všakže?

Na FKŠ však existuje populárny poobedňajší krúžok – Kamaráti Musia Športovať (KMŠ) – ktorí zhrozene pozerajú do rozvrhu na vymeškané športové popoludnie.

Rozhodli sa tak, že všetci členovia krúžku niekam predsalen prísť musia, za účelom udržania kondičky.

Otázka je, kam?

Úloha

Mesto v ktorom sídli FKŠ si vieme reprezentovať budovami, v ktorých bývajú študenti, a cestami ktoré ich prepájajú. Mesto bolo navrhnuté tak, že sa z každej budovy dá cestami dostať do každej inej práve jedným spôsobom.

V každej bytovke býva nezáporné množstvo členov KMŠ, a každá cesta má nejakú kladnú dĺžku v metroch.

Daný je takýto popis mesta, a je určené ktorá z budov je FKŠ.

Športový výkon si zadefinujeme ako súčet dĺžok trás, ktorú prejdú členovia KMŠ aby prišli k zvolenej budove.

Zvyčajne by sa snažilo KMŠ o najväčší športový výkon, keďže je však opposite day, budú sa snažiť o výkon čo najmenší…

Ktorú budovu si majú zvoliť ako stretávacie miesto, aby toto dosiahli?

Formát vstupu

V prvom riadku vstupu sú čísla $n$ a $f$: počet budov v meste a číslo budovy FKŠ.

V druhom riadku je $n$ čísel $k_i$: počet členov KMŠ, ktorí bývajú v budove $i$¹.

V každom z nasledujúcich $n-1$ riadkov sú čísla $a_i\ b_i\ d_i$, znázorňujúce cestu medzi budovami $a_i$ a $b_i$ dlhú $d_i$ metrov. Budovy sú očíslované od $1$ po $n$.

Je zaručené, že sa z každej budovy dá dostať ku každej inej budove.

Formát výstupu

Vypíšte číslo budovy, rôzne od $f$, ku ktorej je súčet dĺžok trás všetkých členov KMŠ najmenší. Ak je takýchto budov viac, vypíšte tú s najmenším číslom.

Obmedzenia

Platí $2 \leq n \leq 100,000$ a $1 \leq f \leq n$.

$0 \leq k_i \leq 10^4$.

$1 \leq a_i \neq b_i \leq n$ a $1 \leq d_i \leq 10^4$.

Sú štyri sady vstupov.

V prvej navyše platí $n \leq 1\,000$.

V druhej zasa platí že $a_i, b_i = i, i+1$ – teda celé mesto leží na čiare.

Príklady

Input:

Output:

Tento vstup je príkladom z druhej sady. Športové výkony ktoré by KMŠ podalo pre danú vybratú budovu sú postupne 125, 69, 45, 55. Pre budovu 3 je športový výkon najmenší, tak si vyberú ju. Jej športový výkon je 45, pretože KMŠák z budovy 1 prejde trasu 13, z budovy 2 prejdú dvaja študenti trasu 6, KMŠáci v tretej budove zídu na prízemie výťahom, a zo štvrtej budovy prídu štyria KMŠáci cestou dĺžky 5. Dokopy teda KMŠ podalo výkon $1*13 + 2*6 + 3*0 + 4*5 = 45$.

Input:

Output:

Vedúci KMŠ by radšej zostal vo FKŠ, je však opačný deň, tak ku FKŠ prísť nemôže. Pre obe iné budovy by jeho športový výkon bol 47, tak si vyberie tú s menším číslom.

Input:

6 4
5 8 2 3 1 4
4 5 3
5 6 8
1 3 1
2 5 1
3 6 9

Output:

Áno, niektorí študenti sú premotivovaní, a bývajú v škole. To preto, že je feľmi kvalitná.↩︎

Najprv si prejdeme základnou terminológiou. Mesto je graf, presnejšie strom - budovy sú vrcholy, a cesty medzi nimi sú hrany. Hrany majú dĺžku, a počet členov KMŠ v každej budove nazveme jej váhou. Vrchol číslo $f$ budeme jednoducho volať škola.

Skúšame všetky budovy

Ako je už zvykom, prvá sada je stvorená na preskúšanie vašej hrubej sily. Môžeme totiž jednoducho spustiť prehľadávanie z každého vrcholu, pamätať si akú vzdialenosť sme zatiaľ prešli, a každému vrcholu ku ktorému prídeme pričítať výkon ktorý sme podali cestou k nemu - rovný prejdenej dĺžke krát váhou vrcholu, z ktorého prehľadávame.

Nakoniec len prejdeme všetky budovy, a zapamätáme si prvú s najmenším podaným výkonom (dávajúc si pozor aby sme nezarátali školu).

V takomto riešení $n$ krát prehľadáme celý graf o $n$ vrcholoch aby sme zrátali výkony, a potom ich raz prejdeme na nájdenie výsledku. Prvá časť nám zaberie $O(n^2)$, druhá $O(n)$, naša časová zložitosť je teda $O(n^2)$.

Okrem vstupu si musíme ku každému vrcholu pamätať konštantný počet premenných (napr. súčet výkonov ktoré sme zrátali, a či sme ho už prehľadali v tejto iterácií). Pamäť je teda $O(n)$.

#include <bits/stdc++.h>

using namespace std;

struct cesta
{
    long long destinacia, dlzka;
};

struct vrchol
{
    vector<cesta> cesty;
    long long ludia;
    long long vykon = 0;
    int naposledy_prejdeny = -1;
};

vector<vrchol> KSP;

void prejdi(int kde, int odkial, long long dlzka, int iteracia)
{
    KSP[kde].naposledy_prejdeny = iteracia;
    KSP[kde].vykon += KSP[odkial].ludia * dlzka;

    for(cesta c : KSP[kde].cesty)
    {
        if(KSP[c.destinacia].naposledy_prejdeny == iteracia)
            continue;

        prejdi(c.destinacia, odkial, dlzka + c.dlzka, iteracia);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,f;
    cin >> n >> f;

    --f;
    KSP.resize(n);

    for(int i=0;i<n;++i)
        cin >> KSP[i].ludia;

    for(int i=0;i<n-1;++i)
    {
        int a,b,d;
        cin >> a >> b >> d;
        --a,--b;
        KSP[a].cesty.push_back({b,d});
        KSP[b].cesty.push_back({a,d});
    }

    // od kazdeho vrcholu sa prejdeme
    // ku kazdemu miestu priratame kolko vykonu sme pritom podali
    for(int i=0;i<n;++i)
        if(KSP[i].ludia != 0)
            prejdi(i, i, 0, i);

    // ako prvu odpoved si dame vrchol 0, ale ak je to FKS, tak vrchol 1
    int kde_najmenej = (f==0);
    long long najmensi_vykon = KSP[(f==0)].vykon;

    for(int i=0;i<n;++i)
    {
        cerr << KSP[i].vykon << "\n";
        if(i==f) continue;
        if(najmensi_vykon > KSP[i].vykon)
        {
            kde_najmenej = i;
            najmensi_vykon = KSP[i].vykon;
        }
    }

    cout << kde_najmenej + 1 << "\n";

}

Počítame za chodu

Druhá sada bola zamýšľaná ako nápoveda. Vieme na takomto grafe pre každý vrchol zrátať výkon podaný aby k nemu všetci prišli, ale akosi naraz? Áno! Predstavme si že graf zavesíme za vrchol číslo $1$, a zrátame si koľko ľudí k nemu musí prísť, a aký celkový výkon pritom podajú (rovnaké prehľadávanie ako v prvej sade). Čo sa zmení, keď sa všetci rozhodnú prísť do budovy $2$? Všetci ktorí sem prišli z budov $2$ až $n$ sa prejdú menej - neprejdú totiž poslednú hranu medzi $1$ a $2$. KMŠáci z budovy $1$ naopak túto hranu predtým prejsť nemuseli, ale ak chcú prísť k budove $2$, už to budú musieť spraviť.

Vo všeobecnosti máme teda nasledovný stav: sme v nejakom vrchole $i$, a vieme aký je celkový výkon podaný aby sem všetci prišli, $V$. Tiež vieme, koľko ľudí k nám prišlo zdola (z vrcholov s väčším číslom), $D$, a koľko ľudí k nám prišlo zhora (z vrcholov s menším číslom), $H$..

Keď sa teraz presunieme do vrchola $i+1$, hranou dĺžky $L$, tieto hodnoty sa zmenia nasledovne:

$H = H + $ počet ľudí vo vrchole $i$ (ľudia vo vrchole $i$ odteraz idú smerom dole)
$V = V - H \cdot L + D \cdot L$ (ľudia zhora prejdú $L$ naviac, ľudia zdola prejdú $L$ menej)
$D = D - $ počet ľudí vo vrchole $i+1$ (ľudia vo vrchole $i+1$ už nejdú smerom hore)

Takto vieme v $O(1)$ postupne, krok po kroku, zrátať celkový výkon pre každý vrchol. Stačí si nám zapamätať si ho a potom vybrať ten optimálny, alebo si toto pamätať už za chodu.

Takto prejdeme graf dva krát - najprv aby sme zistili výkon a počet ľudí idúc zdola do vrcholu $1$, a potom postupne spravíme krok k vrcholu $2, 3, \cdot, n$, udržujúc si všetky potrebné informácie. Každý krok je $O(1)$, máme teda zložitosť $O(n)$.

Okrem vstupu si teraz pamätáme konštantne veľa premenných naviac, pamäť je teda opäť $O(n)$.

#include <bits/stdc++.h>

using namespace std;

struct vrchol
{
    long long ludia, cesta_doprava;
};

const long long velmi_vela = 1e18;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,f;
    cin >> n  >> f;
    --f;

    if(n<=1000) ; //bruteforce();

    vector<vrchol> KSP(n);
    for(int i=0;i<n;++i)
        cin >> KSP[i].ludia;

    for(int i=0;i<n-1;++i)
    {
        int nepotrebujem;
        cin >> nepotrebujem >> nepotrebujem >> KSP[i].cesta_doprava;
    }

    long long najmensi_vykon = velmi_vela, kde = -1;

    // zratame aky vykon treba podat aby sme prisli do mesta 0

    long long ludia_vpravo = 0, ludia_vlavo = 0, vykon = 0;
    for(int i=n-1;i>0;--i)
    {
        ludia_vpravo += KSP[i].ludia;
        vykon += ludia_vpravo * KSP[i-1].cesta_doprava;
    }

    if(f != 0)
        najmensi_vykon = vykon, kde = 0;

    // a teraz budeme posuvat cielove mesto doprava

    for(int i=1;i<n;++i)
    {
        ludia_vlavo += KSP[i-1].ludia;
        vykon += ludia_vlavo * KSP[i-1].cesta_doprava;

        vykon -= ludia_vpravo * KSP[i-1].cesta_doprava;
        ludia_vpravo -= KSP[i].ludia;

        if(i != f && najmensi_vykon > vykon)
        {
            najmensi_vykon = vykon;
            kde = i;
        }

    }

    cout << kde + 1 << "\n";
}

A trochu všeobecnejšie…

Techniku z predošlej sady vieme implementovať aj všeobecnejšie. Musíme byť len šikovnejší, pretože v našom zakorenenom strome budú vrcholy mať viacero synov do ktorých môžeme vkročiť.

Na začiatku si pustíme prehľadávanie z vrcholu $1$, a pre každý vrchol si zapamätáme koľko ľudí býva v jeho podstrome, a aký výkon dokopy podali aby k nemu prišli.

Teraz pustíme nové prehľadávanie, v ktorom si budeme udržiavať počet ľudí ktorí k nám prichádzajú zhora, a aký výkon na to podali. Celkový výkon pre daný vrchol je potom výkon podaný zhora plus výkon zdola, ktorý sme si predtým predpočítali.

Keď začíname vrcholom $1$, 0 ľudí prichádza zhora, a podali nulový výkon.

Keď sa teraz presúvame z vrcholu $i$ do niektorého syna $S$ hranou dĺžky $L$, platí nasledovné:

Všetci, čo prichádzali do $i$ zhora, prichádzajú aj do $S$ zhora, a prejdú $L$ dĺžky navyše.
Navyše, všetci ľudia v synoch $i$, ktorí niesu $S$, doteraz prichádzali do $i$ zdola, ale do $S$ budú prichádzať zhora. Aj tí prejdú $L$ navyše.

Hodnotu číslo 1. si udržiavame v našom prehľadávaní, a hodnotu číslo 2. si vieme vypočítať ako počet ľudí čo prišli do $i$ zdola, mínus počet ľudí čo prišli do $S$ zdola (toto sme si zrátali pre každý vrchol v prvom prehľadávaní).

Naše riešenie má rovnaké zložitosti ako v jednoduchšej verzií. Dvakrát prehľadáme náš graf, pre každú hranu spravíme konštantne veľa operácií (prerátame nejaké celočíselné premenné). Časová zložitosť je teda $O(n)$. Pre každý vrchol si niekoľko z týchto premenných zapamätáme navyše, aj pamäťová zložitosť je teda $O(n)$.

#include <bits/stdc++.h>

using namespace std;

struct cesta
{
    long long destinacia, dlzka;
};

struct vrchol
{
    bool som_FKS = false;
    vector<cesta> cesty;
    long long dokopy_ludia, dokopy_vykony = 0;
    bool zratane = false, prejdene = false;
};

struct odpoved
{
    long long kde, vykon;
};

vector<vrchol> KSP;

// zrata, kolko ludi by muselo prejst vrcholom kde,
// aby prisli k vrcholu na ktorom sa zrataj_ludi zavola najprv
void zrataj(int kde)
{
    KSP[kde].zratane = true;

    for(cesta c : KSP[kde].cesty)
    {
        // nejdeme tam, odkial sme prisli
        if(KSP[c.destinacia].zratane)
            continue;

        zrataj(c.destinacia);
        KSP[kde].dokopy_ludia += KSP[c.destinacia].dokopy_ludia;

        // ked k nam pridu ludia z c.destinacia, vsetci sa prejdu o c.dlzka viac
        long long zvysenie_vykonu = KSP[c.destinacia].dokopy_ludia * c.dlzka;
        KSP[kde].dokopy_vykony += KSP[c.destinacia].dokopy_vykony + zvysenie_vykonu;
    }

}

// cislo vacsie ako najvacsia odpoved
const long long velmi_vela = 1e18;

// vyrata aky vykon treba podat aby sa KMSaci stretli v kde
// a potom vyskusa posunut miesto stretnutia na vsetky svoje deti
// vrati najmensi vykon co najde, a kde to bolo
// (mozeme kludne pouzit pair alebo struct cesta, ale je to prehladnejsie :) )
odpoved prejdi(int kde,long long ludia_zhora, long long vykon_zhora)
{
    KSP[kde].prejdene = true;

    odpoved najlepsi_vykon = {-1, velmi_vela};

    // ak nie som FKS, zratam aky vykon je potrebny aby sa vsetci stretli pri mne
    if(KSP[kde].som_FKS == false)
        najlepsi_vykon = {kde, KSP[kde].dokopy_vykony + vykon_zhora};

    // skusim posunut miesto stretnutia na vrcholy podomnou
    for(int i=0;i<KSP[kde].cesty.size();++i)
    {
        cesta c = KSP[kde].cesty[i];
        // nejdeme dohora
        if(KSP[c.destinacia].prejdene) continue;
    
        // ked sa posuvame z kde do c.destinacia, tak:
        // ludia co pojdu 'zhora' su ti co uz zhora isli, plus vsetci ktori prisli do kde, okrem tych ktori prisli z c.destinacia
        long long novi_ludia_zhora = ludia_zhora + KSP[kde].dokopy_ludia - KSP[c.destinacia].dokopy_ludia;

        // novy vykon zhora je ten co uz bol, plus vsetci ludia zhora prejdu cestou c
        // vsetci co nejak prisli do kde tiez podaju ten vykon
        // ale ti ludia co sem prisli z c.destinacia ho nepodaju zhora, a navyse neprejdu ani cestou c
        long long novy_vykon_zhora = vykon_zhora + (novi_ludia_zhora * c.dlzka) + KSP[kde].dokopy_vykony - KSP[c.destinacia].dokopy_vykony - KSP[c.destinacia].dokopy_ludia * c.dlzka;

        odpoved posunuta = prejdi(c.destinacia, novi_ludia_zhora, novy_vykon_zhora);

        if(posunuta.vykon < najlepsi_vykon.vykon || (posunuta.vykon == najlepsi_vykon.vykon && posunuta.kde < najlepsi_vykon.kde))
        {
            najlepsi_vykon = posunuta;
        }
    }

    return najlepsi_vykon;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,f;
    cin >> n >> f;

    KSP.resize(n);
    KSP[f-1].som_FKS = true;

    for(int i=0;i<n;++i)
        cin >> KSP[i].dokopy_ludia;

    for(int i=0;i<n-1;++i)
    {
        int a,b,d;
        cin >> a >> b >> d;
        --a,--b;
        KSP[a].cesty.push_back({b,d});
        KSP[b].cesty.push_back({a,d});
    }

    zrataj(0);
    odpoved ans = prejdi(0, 0, 0);
    cout << ans.kde + 1 << "\n";
}

from dataclasses import dataclass
from typing import List
import sys

sys.setrecursionlimit(123456)

@dataclass
class cesta:
    destinacia: int 
    dlzka: int 

@dataclass
class vrchol:
    som_FKS: bool = False
    cesty: List[cesta] = None
    dokopy_ludia: int = 0
    dokopy_vykony: int = 0
    zratane: bool = False
    prejdene: bool = False

@dataclass
class odpoved:
    kde: int
    vykon: int

n, f = [int(x) for x in input().split()]

KSP = [ vrchol() for _ in range(n)]
for i in range(n):
    KSP[i].cesty = []
KSP[f-1].som_FKS = True

kms = [int(x) for x in input().split()]
for i in range(n):
    KSP[i].dokopy_ludia = kms[i]

for i in range(n-1):
    a,b,d = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    KSP[a].cesty.append(cesta(b,d))
    KSP[b].cesty.append(cesta(a,d))

def zrataj(kde):
    KSP[kde].zratane = True 

    for c in KSP[kde].cesty:

        if KSP[c.destinacia].zratane:
            continue

        zrataj(c.destinacia)
        KSP[kde].dokopy_ludia += KSP[c.destinacia].dokopy_ludia

        zvysenie_vykonu = KSP[c.destinacia].dokopy_ludia * c.dlzka
        KSP[kde].dokopy_vykony += KSP[c.destinacia].dokopy_vykony + zvysenie_vykonu

zrataj(0)

velmi_vela = 1e28

def prejdi(kde, ludia_zhora, vykon_zhora):
    KSP[kde].prejdene = True

    najlepsi_vykon = odpoved(-1, velmi_vela)

    if KSP[kde].som_FKS == False:
        najlepsi_vykon = odpoved(kde, KSP[kde].dokopy_vykony + vykon_zhora)

    for c in KSP[kde].cesty:

        if KSP[c.destinacia].prejdene:
            continue

        novi_ludia_zhora = ludia_zhora + KSP[kde].dokopy_ludia - KSP[c.destinacia].dokopy_ludia;

        novy_vykon_zhora = vykon_zhora + (novi_ludia_zhora * c.dlzka) + KSP[kde].dokopy_vykony - KSP[c.destinacia].dokopy_vykony - KSP[c.destinacia].dokopy_ludia * c.dlzka;

        posunuta = prejdi(c.destinacia, novi_ludia_zhora, novy_vykon_zhora);

        if (posunuta.vykon < najlepsi_vykon.vykon) or ( (posunuta.vykon == najlepsi_vykon.vykon) and (posunuta.kde < najlepsi_vykon.kde) ):
            najlepsi_vykon = posunuta;

    return najlepsi_vykon
        

ans = prejdi(0,0,0)
print(ans.kde+1)

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ť.

5. Neprísť do školy vzorové riešenie

Zadanie

Úloha

Formát vstupu

Formát výstupu

Obmedzenia

Príklady

Skúšame všetky budovy

Počítame za chodu

A trochu všeobecnejšie…

Diskusia