Zadanie

Každý dobre vie, že Michallius sa rád bije. Chcel sa prihlásiť na bitkársky turnaj konajúci sa na konci semestra, zaškrtol však zlú kolónku a ocitol sa na prestížnom gladiátorskom deathmatch-i1, na ktorý sa bude pozerať aj sám cézar. Na začiatku dostane každý gladiátor 1 bitkoin2 a za porazenie súpera získava všetky jeho bitkoiny. Takže gladiátori sa vedia pekne nabaliť. Bojuje sa v dvoch typoch súbojov: v boji s mečom a boji s kopijou. Na začiatku súboja sa vždy vyberie typ zbrane a táto zbraň sa počas súboja nezmení.

Chudák Michallius bol sprvu veľmi utrápený a bál sa. Kašľal na svoj bitkoin, chcel iba prežiť. Musel preto teda niečo robiť. Rozhodol sa preskúmať svoje sily a sily ostatných súperov. O každom gladiátorovi (vrátane seba) si poznačil jeho silu s mečom a s kopijou. Robil to dôkladne, žiadni dvaja bojovníci nemajú rovnakú silu v jednom type boja. Michallius cez skúškové trénoval, poctivo posilňoval, a aj sa správne stravoval. Zistil, že nakoniec je v tom bojovaní celkom dobrý, preto ho už začína zaujímať koľko by si vedel maximálne odniesť z tohto turnaja.

Zistite, aký maximálny zárobok si vie Michallius odniesť. A vlastne, keď už to zistíte o Michalliovi, zistite to isté o každom ďalšom gladiátorovi.

Úloha

Na turnaj sa prihlásilo \(n\) gladiátorov. O každom gladiátorovi vieme jeho silu v boji s mečom a silu v boji s kopijou (obe tieto sily sú celé čísla). Každý gladiátor dostane na začiatku 1 bitkoin. Turnaj má pomerne voľnú štruktúru, ktorá vyzerá nasledovne:

  1. Vylosujú sa dvaja gladiátori, ktorí ešte neprehrali.
  2. Vylosuje sa, či budú bojovať s kopijami, alebo s mečmi.
  3. Pobijú sa. Gladiátor, ktorý je v danom type boja silnejší, zvíťazí.
  4. Víťaz získa všetky bitkoiny porazeného a porazený vypadáva z turnaja (z pochopiteľných dôvodov).

Tieto štyri kroky sa opakujú, až kým turnaj cézara neomrzí. Môže sa tak stať, že na konci prežije viacero gladiátorov.

Chceme vedieť o každom gladiátorovi, koľko bitkoinov môže na turnaji maximálne zarobiť, ak by všetky losovania dopadli preňho najlepším možným spôsobom.

Formát vstupu

Na prvom riadku vstupu sa nachádza celé číslo \(n\) – počet gladiátorov na turnaji. Platí: \(1 \leq n \leq 100,000\). Nasleduje \(n\) riadkov. V \(i\)-tom riadku sa nachádzajú dve celé čísla oddelené medzerou: sila \(i\)-teho gladiátora v boji s mečom \(m_i\) a jeho sila v boji s kopijou \(k_i\). Platí \(1 \leq m_i , k_i \leq n\). Môžete predpokladať, že žiadni dvaja gladiátori nemajú rovnakú silu s mečom, ani rovnakú silu s kopijou.

Formát výstupu

Vypíšte \(n\) riadkov. V \(i\)-tom riadku vypíšte počet bitkoinov, ktoré môže \(i\)-ty gladiátor získať.

Príklady

Input:

4
2 3
3 2
1 1
4 4

Output:

3
3
1
4

Michallius (prvý gladiátor) dokáže poraziť druhého gladiátora ak budú bojovať s kopijou, tretieho v ľubovolnom boji. Druhý gladiátor porazí Michallia v boji s mečom a tretieho v ľubovolnom boji. Tretí gladiátor je bezmocná ovca, a štvrtý je Spartakus.

Input:

4
3 3
4 1
1 4
2 2

Output:

4
4
4
4

Všimnime si, že posledný gladiátor dokáže získať aj Michalliov bitkoin, hoci je slabší v oboch typoch boja.


  1. To znamená, že súboj pokračuje, dokým jeden z dvojice nezomrie

  2. bitkoin – drobná zlatá minca používaná medzi bitkármi (odtiaľ názov)

Koľko bitkoinov vie vyhrať gladiátor \(\boldsymbol{a}\)?

Aby sme zistili koľko bitkoinov môže zarobiť nejaký gladiátor \(a\), skúsme najskôr zistiť ktoré bitkoiny môže \(a\) získať.

Aby gladiátor \(a\) získal bitkoin, ktorý na začiatku turnaja patril gladiátorovi \(b\), musí k nemu tento bitkoin nejako doputovať. Táto púť bude vyzerať tak, že najskôr \(b\) prehrá súboj s nejakým iným gladiátorom, ten (ak to ešte nie je gladiátor \(a\)) potom prehrá s ďalším gladiátorom, ten prehrá s ďalším, atď., až nakoniec posledný gladiátor z tejto reťaze prehrá s gladiátorom \(a\).

Povedané formálne, \(a\) dokáže získať bitkoin od \(b\), vtedy a len vtedy, keď existuje postupnosť gladiátorov \(b = g_1, g_2, \ldots, g_k = a\) taká, že pre všetky prípustné \(i\) vie \(g_{i+1}\) poraziť \(g_i\) v aspoň jednom type súboja.

Máme teda dobre popísaný vzťah “\(a\) vie získať bitkoin \(b\)”. Viac bitkoinov než počet takýchto gladiátorov \(b\) gladiátor \(a\) nevie získať. Ale to, že \(a\) vie získať bitkoiny od \(b_1, \ldots, b_m\) ešte neznamená, že ich vie získať všetky v priebehu jedného turnaja. Ukazuje sa ale, že sa to dá.

Dobre sa to vysvetľuje z grafového hľadiska. Uvažujme orientovaný graf, v ktorom vrcholy reprezentujú gladiátorov, a je v ňom hrana \(x \rightarrow y\) vtedy, keď \(x\) vie poraziť \(y\) aspoň v jednom type súboja. Potom \(a\) vie získať bitkoiny práve tých gladiátorov, ktorí sú dosiahnuteľní z \(a\) (rozmyslite si).

Postupnosť zápasov, v ktorej \(a\) získa bitkoiny od všetkých takýchto gladiátorov, vieme nájsť nasledovne:

  1. Začneme s prázdnou postupnosťou zápasov.
  2. Spustime prehľadávanie (napríklad do hĺbky) z \(a\) a vždy, keď prejdeme po hrane do nejakého ešte nenavštíveného vrcholu, zafarbime túto hranu na červeno. Po skončení prehľadávania budú červené hrany tvoriť strom obsahujúci práve vrcholy dosiahnuteľné z \(a\).
  3. Z tohto stromu odstránime hranu \(x \rightarrow y\) vedúcu do listu a do postupnosti pridáme zápas medzi \(x, y\), pričom typ zápasu zvolíme tak, aby \(x\) vyhral.
  4. Opakujeme predchádzajúci krok, kým sú v grafe hrany.

(Prvá tabuľka zobrazuje sily jednotlivých gladiátorov. Druhá tabuľka obsahuje gladiátorov usporiadaných podľa ich síl. Tretia tabuľka zobrazuje zápasy v takom turnaji, v ktorom by gladiátor \(g_7\) získal všetky bitkoiny, ktoré vie získať.)

Prvý správny algoritmus

Predchádzajúca úvaha nám dáva jednoduchý algoritmus na riešenie úlohy: zostrojíme graf a postupne z každého vrcholu \(a\) spustíme prehľadávanie, ktorým zistíme, koľko vrcholov z neho vieme dosiahnuť. To je zároveň aj počet bitkoinov, ktorý si vie gladiátor \(a\) z turnaja odniesť.

Graf obsahuje \(n\) vrcholov a \(O(n^2)\) hrán, časová zložitosť je preto \(O(n^3)\). Pamäťová zložitosť je \(O(n^2)\) (ak v pamäti vytvoríme všetky hrany), prípadne \(O(n)\) (ak si pamätáme iba sily gladiátorov).

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> graf;
vector<int> navstivene;
int pocet;

void dfs(int v) {
  if (navstivene[v]) return;
  navstivene[v] = true;
  pocet++;

  for (int i = 0; i < graf[v].size(); ++i) {
    dfs(graf[v][i]);
  }
}

int main() {
  int n; scanf("%d", &n);
  vector<int> mec(n), kopija(n);
  navstivene.resize(n);

  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &mec[i], &kopija[i]);
  }

  graf.resize(n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (mec[i] > mec[j]) graf[i].push_back(j);
      if (kopija[i] > kopija[j]) graf[i].push_back(j);
    }
  }

  for (int i = 0; i < n; ++i) {
    pocet = 0;
    for(int j = 0;j < n;j++) navstivene[j] = 0;
    dfs(i);
    printf("%d\n", pocet);
  }

  return 0;
}

Predchádzajúce riešenie možno o rád zrýchliť nasledujúcim trikom: usporiadajme si gladiátorov do postupnosti \(g'_1, g'_2, \ldots, g'_n\) podľa rastúcej sily v boji s mečom. Potom nemusíme mať v grafe všetky hrany \(g'_i \rightarrow g'_j\) pre \(i > j\), stačí, ak v ňom budú hrany \(g'_i \rightarrow g'_{i - 1}\) pre všetky prípustné \(i\).

(Graf, v ktorom neuvažujeme zbytočné hrany. Pre každú silu \(k > 1\) a každý typ boja máme hranu vedúcu od gladiátora so silou \(k\) ku gladiátorovi so silou \(k - 1\). Zelené hrany zodpovedajú boju s mečom, modré hrany boju s kopijou.)

Prečo? Ak v pôvodnom grafe existovala cesta z \(a\) do nejakého \(b\), tak v novom grafe dostaneme cestu z \(a\) do \(b\) tak, že každú hranu na pôvodnej ceste, ktorá má tvar \(g_i \rightarrow g_j\) pre \(i > j\), nahradíme postupnosťou hrán \(g_i \rightarrow g_{i - 1}, g_{i - 1} \rightarrow g_{i - 2}, \ldots, g_{j + 1} \rightarrow g_j\). Takže pre ľubovoľný vrchol \(a\) je množina vrcholov dosiahnuteľných z \(a\) rovnaká, ako v pôvodnom grafe.

Rovnako vieme zredukovať počet hrán, ktoré zodpovedajú súbojom s kopijou. V novom grafe budeme mať \(2 \cdot (n - 1) = O(n)\) hrán, a vylepšíme tým časovú zložitosť algoritmu na \(O(n^2)\).

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

vector<vector<int>> graf;
vector<int> vysledok, navstivene;
int pocet;

void dfs(int v) {
  if (navstivene[v]) return;
  navstivene[v] = true;
  pocet++;

  for (int i = 0; i < graf[v].size(); ++i) {
    dfs(graf[v][i]);
  }
}

int main() {
  int n; scanf("%d", &n);
  vector<pii> mec(n), kopija(n);
  vysledok.resize(n);
  navstivene.resize(n);

  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &mec[i].first, &kopija[i].first);
    mec[i].second = kopija[i].second = i;
  }
  sort(mec.begin(), mec.end());
  sort(kopija.begin(), kopija.end());
  graf.resize(n);

  for (int i = 1; i < n; ++i) {
    graf[mec[i].second].push_back(mec[i-1].second);
    graf[kopija[i].second].push_back(kopija[i-1].second);
  }

  for (int i = 0; i < n; ++i) {
    pocet = 0;
    for(int j = 0;j < n;j++) navstivene[j] = 0;
    dfs(mec[i].second);
    vysledok[mec[i].second] = pocet;
  }

  for (int i = 0; i < n; ++i) {
    printf("%d\n", vysledok[i]);
  }

  return 0;
}

Vzorové riešenie

Majme gladiátorov \(g_1, g_2, \ldots, g_n\) usporiadaných vzostupne podľa sily v boji s mečom. Všimnime si, že všetky bitkoiny, ktoré vie získať \(g_i\), vie získať aj \(g_{i + 1}\). To ale znamená, že keď hľadáme vrcholy dosiahnuteľné z \(g_{i + 1}\), tak nám stačí hľadať iba také vrcholy, ktoré nie sú dosiahnuteľné z \(g_i\). Vrcholy dosiahnuteľné z \(g_i\) totiž môžeme zarátať automaticky.

Budeme teda púštať prehľadávanie postupne od najslabších gladiátorov k najsilnejším, teda v poradí \(g_1, g_2, \ldots, g_n\). Pre každého gladiátora si pamätáme, či sme ho už v niektorom prehľadávaní navštívili, a pamätáme si tiež počet už navštívených gladiátorov. Keď prehľadávame z \(g_i\), tak nenavštevujeme vrcholy, ktoré sme už navštívili v niektorom z predchádzajúcich prehľadávaní.

Rozmyslite si, že takýmto spôsobom sú po \(i\)-tom prehľadávaní navštívení práve tí gladiátori, ktorí sú dosiahnuteľní z \(g_i\). Práve od nich vie \(g_i\) získať bitkoin. Ich počet je teda počet bitkoinov, ktoré vie \(g_i\) získať.

Zložitosť

Na začiatku si potrebujeme utriediť gladiátorov podľa sily. To nám bude trvať \(O(n \log n)\). Počas prehľadávaní navštívime každý vrchol grafu najviac raz, čo je \(O(n)\) roboty (lebo graf má len \(n\) vrcholov a \(O(n)\) hrán). Preto je časová zložitosť celého algoritmu \(O(n \log n)\). Pamäťová zložitosť ostáva \(O(n)\).

Pritom časová zložitosť \(O(n \log n)\) je iba kvôli triedeniu, my však máme čísla z rozsahu od \(1\) po \(n\). Vieme ich teda utriediť count sortom, a dostaneme tak lepší čas \(O(n)\).

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

vector<vector<int>> graf;
vector<int> vysledok, navstivene;
int pocet;

void dfs(int v) {
  if (navstivene[v]) return;
  navstivene[v] = true;
  pocet++;

  for (int i = 0; i < graf[v].size(); ++i) {
    dfs(graf[v][i]);
  }
}

void countSort(vector<pii> &v) {
  vector<pii> utriedene(v.size());
  for (int i = 0; i < v.size(); ++i) {
    utriedene[v[i].first - 1] = v[i];
  }
  v = utriedene;
}

int main() {
  int n; scanf("%d", &n);
  vector<pii> mec(n), kopija(n);
  vysledok.resize(n);
  navstivene.resize(n);

  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &mec[i].first, &kopija[i].first);
    mec[i].second = kopija[i].second = i;
  }
  countSort(mec);
  countSort(kopija);
  graf.resize(n);

  for (int i = 1; i < n; ++i) {
    graf[mec[i].second].push_back(mec[i-1].second);
    graf[kopija[i].second].push_back(kopija[i-1].second);
  }

  for (int i = 0; i < n; ++i) {
    dfs(mec[i].second);
    vysledok[mec[i].second] = pocet;
  }

  for (int i = 0; i < n; ++i) {
    printf("%d\n", vysledok[i]);
  }

  return 0;
}

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