Zadanie
Život súťažného bojovníka v Ríme je náročná záležitosť. Okrem všetkých zjavných výziev, s ktorými sa každodenne stretávajú je tu aj hlboký a fundamentálny problém, kvôli ktorému to mnohí bojoví géniovia vzdávajú hneď na začiatku. Týmto problémom je príprava tesne pred súbojom.
Asi si to viete predstaviť. Musím si nasadiť zbroj. Musím si upevniť koženú čiapku. Musím sa obuť. Musím si nasadiť holenné chrániče… Ajajáj, veď som už obutý! Musím sa vyzuť a nasadiť si holenné chrániče. Ej bisťu, zabudol som na správne bojové pomaľovanie! A všetko odznova.
Uznajte, že takýmto tempom by aj vás akurát tak porazilo. Aby Rím neprichádzal o talenty, všetky významnejšie arény začali zamestnávať prípravných špecialistov. Ich úlohou je pre každého bojovníka usporiadať jeho prípravné akcie tak, aby vzájomne nekolidovali.
Úloha
V bojovníckom svete existuje \(n\) rôznych možných prípravných akcií. Každý bojovník pri príprave na boj potrebuje vykonať niektoré z nich (nie nutne všetky). Pre niektoré dvojice akcií \(A\) a \(B\) platí, že keď niekedy vykonáme \(A\), už nikdy nebudeme vedieť vykonať \(B\) (napríklad, ak si oblečieme krúžkovú košeľu, už si nemôžeme obliecť tielko, alebo ak si nasadíme chrániče predlaktí, už si nemôžeme obliecť krúžkovú košeľu). Našťastie existuje poradie, v ktorom sa dajú vykonať všetky akcie.
Dostanete zoznam spomenutých závislostí medzi akciami. Ďalej dostanete \(q\) bojovníkov, každý z nich bude chcieť vykonať nejaký zoznam akcií. Vašou úlohou bude usporiadať akcie pre každého bojovníka.
Formát vstupu
Na prvom riadku dostanete čísla \(n\), \(m\) a \(q\) (\(1 \leq n, m, q \leq 100\,000\)) – počet rôznych možných akcií, počet závislostí medzi nimi a počet bojovníkov. Akcie sú očíslované od \(1\) po \(n\).
Nasleduje \(m\) riadkov, v každom z nich dostanete dve rôzne čísla \(A_i\) a \(B_i\) (\(1 \leq A_i, B_i \leq n\)), ktoré označujú, že keď vykonáme akciu \(A_i\), už nebudeme vedieť vykonať akciu \(B_i\).
Nakoniec nasleduje \(q\) riadkov, \(i\)-ty z nich začína celým číslom \(q_i\) (\(1 \leq q_i \leq n\)) – počtom akcií \(i\)-teho bojovníka. Za týmto číslom nasleduje \(q_i\) ďalších čísel z rozsahu \(1\) až \(n\) – čísla akcií \(i\)-teho bojovníka.
Počet všetkých akcií, ktoré chcú bojovníci vykonať (súčet všetkých \(q_i\)), neprekročí \(100\,000\). Môžete predpokladať, že prípravné kroky každého bojovníka sa dajú usporiadať tak, aby nebola porušená žiadna závislosť.
Formát výstupu
Vypíšte \(q\) riadkov, v \(i\)-tom z nich \(q_i\) čísel – zoznam krokov \(i\)-teho bojovníka v poradí, v akom ich má vykonať. Ak existuje viacero možných poradí, vypíšte ľubovoľné z nich.
Príklad
Input:
5 5 3
4 3
2 4
3 1
2 1
5 4
4 1 4 3 2
2 1 4
1 5
Output:
1 3 4 2
4 1
5
Prvý bojovník má iba jedno vhodné poradie akcií. Druhý bojovník by mohol akcie vykonať aj v opačnom poradí.
Táto úloha pozostáva z dvoch podproblémov:
Ako vieme k nejakému zoznamu akcií zistiť poradie, v ktorom ich vieme vykonať
Ako vieme rýchlo spracovať podmnožiny, v ktorých sa môžu prvky opakovať
Najprv rozoberieme riešenie prvého podproblému a potom to celé poskladáme dohromady. Pre ľahší popis časovej zložitosti budeme celkový počet akcií (súčet \(q_i\) zo vstupu) označovať ako \(s\).
Topologické usporiadanie
Prvý problém bol mierne zamaskovaný problém topologického usporiadania. Najprv si uvedomíme, že podmienka ,,po vykonaní \(A\) nemôžeš vykonať \(B\)’‘je rovnaká, ako podmienka ,,ak chceš vykonať \(A\) aj \(B\), musíš najprv vykonať \(B\) a až potom \(A\)’’.
Akcie usporiadame nasledovne: Najprv si pre každú akciu spočítame, koľko iných akcií musíme vykonať pred ňou, toto číslo budeme dalej volať počet závislostí. Niektoré akcie budú mať nula závislostí; ktorúkoľvek z nich vieme vykonať. Keď ju vykonáme, všetkým akciám, ktoré na nej záviseli, znížime počítadlo o jedna. Tým môže niektorým akciám klesnúť počet závislostí tiež na nulu.
Aby sme nemuseli pred vykonávaním každej akcie prejsť cez všetky a hľadať nejakú, ktorú môžeme vykonať, inšpirujeme sa prehľadávaním grafu do šírky. Na začiatku všetky akcie s nula závislosťami hodíme do fronty na spracovanie. S každým znížením počtu závislostí nejakej akcii skontrolujeme, či tento počet neklesol na nulu. Ak klesol, akciu pridáme do fronty.
Vo všeobecnosti by sa mohlo stať, že v niektorom momente nevieme vykonať žiadnu akciu, lebo všetky majú nejakú nevykonanú závislosť. V zadaní je však garantované, že všetky akcie sa dajú vykonať v nejakom poradí a teda takáto situácia nemôže nastať.
Pokiaľ potrebujeme usporiadať \(n\) akcií s \(m\) závislosťami, celé nám to bude trvať čas \(O(n+m)\), lebo každú závislosť práve raz započítame a raz odpočítame, a každú akciu raz pridáme do fronty a raz spracujeme.
Viacero bojovníkov
Keď vieme robiť topologické usporiadanie, môžeme rovno spraviť riešenie polohrubou silou. Pre každého bojovníka vezmeme jeho zoznam akcií, vyberieme relevantné závislosti a topologicky ich usporiadame. Dostaneme tým riešenie s časovou zložitosťou \(O((n+m) \cdot q)\).
Lepšie riešenie však dostaneme, keď využijeme nasledujúce pozorovanie: Ak vieme vykonať všetky akcie v nejakom poradí, v tom istom poradí môžeme vykonať akcie každého bojovníka (s tým, že niektoré jednoducho vynecháme).
Na začiatku teda zistíme poradie, v ktorom sa dajú vykonať všetky akcie. Pre každého bojovníka usporiadame jeho zoznam akcií svojim obľúbeným (rýchlym) triediacim algoritmom. Keď nasčítame členy v tvare \(q_i \cdot \log(q_i)\), dostaneme časovú zložitosť \(O(s \log(s) + n + m)\).
#include <bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i = 0; i < n; i++)
int main () {
int n, m, q;
cin >> n >> m >> q;
vector<vector<int> > zavislosti(n);
vector<int> predomnou(n, 0);
// Nacitame zavislosti a spocitame pocet zavislosti pre kazdu akciu
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
// Akcie budeme vnutorne reprezentovat o jedna mensim cislom
a --; b--;
zavislosti [b].push_back(a);
predomnou [a] ++;
}
// Vypocitame topologicke usporiadanie
vector<int> poradie;
queue<int> nasprac;
// Najprv do fronty pridame vsetky akcie, ktore nemali ziadne
// zavislosti
for(int i = 0; i < n; i++) {
if (predomnou [i] == 0) nasprac.push(i);
}
// Dalej ich spracujeme
while (!nasprac.empty()) {
int aktualny = nasprac.front();
poradie.push_back(aktualny);
nasprac.pop();
// Znizime pocty zavislosti
for (int zavislost : zavislosti [aktualny]) {
predomnou [zavislost] --;
// Ak treba, pridame akciu do fronty
if (predomnou [zavislost] == 0) nasprac.push (zavislost);
}
}
// Toto pole bude oznacovat, kolka v poradi je ktora akcia,
// invporadie [7] oznacuje, kolka v poradi sa vykona osma akcia
vector<int> invporadie(n);
For(i, n) invporadie [poradie [i]] = i;
vector<int> bojovnik;
// Nakoniec spracujeme bojovnikov
for (int i = 0; i < q; i++) {
int qi;
cin >> qi;
bojovnik.resize(qi);
for(int j = 0; j < qi; j++) {
cin >> bojovnik [j];
bojovnik [j] --;
}
// Tu vyuzivame pole invporadie
sort(bojovnik.begin(), bojovnik.end(), [&invporadie](int a, int b) {return invporadie [a] < invporadie [b];});
cout << bojovnik [0] + 1;
for(int j = 1; j < qi; j++) cout << ' ' << bojovnik [j] + 1;
cout << '\n';
}
}
Optimálne riešenie
Predošlé riešenie stačilo na to, aby sme získali všetky body od testovača. Existuje však komplikovanejšie riešenie, ktoré bude mať lepšiu časovú zložitosť. Využijeme fakt, že bojovníci sa pýtajú stále na ,,tie isté’’ akcie.
Najprv nájdeme topologické usporiadanie všetkých akcií v čase \(O(n+m)\). Ďalej načítame akcie všetkých bojovníkov, ale uložíme si ich ,,čudne’’: Pre každú z \(n\) akcií si budeme pamätať zoznam bojovníkov, ktorí ju chceli vykonať (v čase \(O(s + n)\)).
Nakoniec budeme vytvárať pre každého bojovníka jeho usporiadaný zoznam akcií, na začiatku prázdny zoznam. Spracujeme všetky akcie v ich topologickom usporiadaní. Keď spracúvame akciu \(X\), pre všetkých bojovníkov, ktorí ju chcú vykonať, ju pridáme na koniec ich aktuálnych zoznamov. Táto časť programu sa bude vykonávať v čase \(O(n + s)\).
Nakoniec vypíšeme všetky skonštruované zoznamy pre bojovníkov. Celková časová zložitosť bude \(O(n + m + s)\).
#include <bits/stdc++.h>
using namespace std;
int main () {
int n, m, q;
cin >> n >> m >> q;
vector<vector<int> > zavislosti(n);
vector<int> predomnou(n, 0);
// Zaciatok je zhodny s predoslym riesenim
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a --; b--;
zavislosti [b].push_back(a);
predomnou [a] ++;
}
vector<int> poradie;
queue<int> nasprac;
for(int i = 0; i < n; i++) {
if (predomnou [i] == 0) nasprac.push(i);
}
while (!nasprac.empty()) {
int aktualny = nasprac.front();
poradie.push_back(aktualny);
nasprac.pop();
for (int zavislost : zavislosti [aktualny]) {
predomnou [zavislost] --;
if (predomnou [zavislost] == 0) nasprac.push (zavislost);
}
}
/** --------------------------
* Tu sa zacinaju nove veci
* -------------------------- */
// Najprv pre kazdu akciu vytvorime zoznam bojovnikov, ktori ju chcu vykonat
vector<vector<int> > bojovnici_s_akciou(n);
for (int i = 0; i < q; i++) {
int qi;
cin >> qi;
for(int j = 0; j < qi; j++) {
int x;
cin >> x;
x --;
bojovnici_s_akciou [x].push_back(i);
}
}
// Dalej budeme vytvarat usporiadany zoznam akcii pre kazdeho bojovnika
vector<vector<int> > vystup(q);
for(int akcia : poradie) {
for (int boj : bojovnici_s_akciou [akcia]) {
vystup [boj].push_back(akcia);
}
}
// Nakoniec vsetko vypiseme
for (int i = 0; i < q; i++) {
cout << vystup [i][0] + 1;
for (int j = 1; j < (int) vystup [i].size(); j++) {
cout << ' ' << vystup [i][j] + 1;
}
cout << '\n';
}
}
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ť.
Matej Novota
Aký je rozdiel medzi s a q?
Matej Novota
Pod q sa myslí počet otázok a pod s sa myslí súčet všetkých počtov?
Dávid Barbora
Áno.