Zadanie

Malá T našla niekoľko modrých guličiek a nanukových paličiek, tak ich začala lepiť dokopy a staviať z nich. Začala tým, že ich pospájala tak, aby každá nanuková palička spája dve guličky, avšak jedna gulička može byť pripojená na ľubovoľne veľa paličiek. Tiež platí, že celé dielo je súvislé, ale ak by sme ľubovoľnú paličku zobrali, rozpadlo by sa na dva kusy.

Po chvíli si však malá T uvedomila, že jej výtvor je príliš veľký a ťažko sa jej prenáša, takže chcela by ho zmenšiť. Existuje však len jeden spôsob, ako je ochotná zmenšiť svoj výtvor – zoberie jednu guličku preč a spolu s ňou aj všetky paličky, ktoré boli k nej prilepené. Je možné, že dielo sa následne rozpadne na niekoľko kusov, čo nie je dobré, preto by T chcela pridať niekoľko nových paličiek spajajúcich dve guličky tak, aby výtvor bol znovu súvislý. Dostane tak útvar, ktorý má o jednu guličku menej. Nie je to však také jednoduché. Keďže narábanie s lepiacou pištoľou je nebezpečné, bolo by dobré tých nových paličiek pridať čo najmenej. Navyše guličky sú rôznych odtieňov modrej a aby bol výsledný útvar pekný, bolo by vhodné, keby nové paličky spájali guličky s podobnými farbami.

Úloha

Malá T má \(n\) guličiek rôznych odtieňov modrej. T očíslovala guličky od najsvetlejšej po najtmavšiu od \(1\) po \(n\). Následne ich pospájala paličkami tak, že ak si predstavíme guličky ako vrcholy a paličky ako hrany medzi nimi, dostaneme strom. Teraz uvažuje nad tým, že jednu z guličiek spolu s paličkami, na ktoré je prilepená, odstráni. Následne chce znovu pozliepať dokopy všetky časti diela (až na odstránenú guličku) čo najmenej paličkami tak, aby bolo znovu súvislé. Kontrast novovytvoreného guličkového diela je súčet rozdielov (v absolútnej hodnote) medzi číslami novopospájaných dvojíc guličiek. T by chcela dosiahnúť čo najmenší kontrast. Hľadá teda spôsob, ako znovu pospájať guličky tak, aby v prvom rade urobila čo najmenej spojov a spomedzi všetkých takýchto spôsobov hľadá ten, kde nové paličky vytvárajú dokopy čo najmenší kontrast.

Nie je si však istá, ako toto urobiť, a preto necháva túto úlohu na vás, šikovných programátorov. A keďže nevie ešte ktorú guličku odstráni, chce, aby ste vypočítali minimálny počet potrebných paličiek a minimálny možný kontrast pre takéto pospájanie pre každú možnú odstránenú guličku. A ideálne by bolo, keby ste jej aj našli návod, ako pozliepať útvar, aby tieto hodnoty dosiahla. Ak existuje viacero riešení s rovnakým kontrastom a počtom pridaných paličiek, vypíšte akékoľvek.

Formát vstupu

V prvom riadku vstupu je číslo \(t\) (\(1 \leq t \leq 10^5\)) udávajúce počet útvarov, pre ktoré máte úlohu riešiť.

Potom nasleduje \(t\) popisov stromov. V prvom riadku každého popisu je \(n\) (\(1 \leq n \leq 10^5\)), počet guličiek a nasleduje \(n-1\) riadkov popisujúcich dvojice guličiek, ktoré sú spojené paličkou. Guličky sú očíslované od \(1\) po \(n\) podľa ich farby, takže kontrast guličiek s číslami \(a\) a \(b\) je \(|a-b|\).

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1, 2 3, 4
\(1 \leq n \leq\) \(1000\) \(10^5\)

Za každú sadu sa dajú získať \(2\) body. Sady \(1\) a \(3\) sú špeciálne – na ich vyriešenie stačí len nájsť minimálny počet paličiek a minimálny dosiahnuteľný kontrast po odstránení každého vrcholu, ale nemusíte nájsť správny návod na dosiahnutie tohto minima.

Formát výstupu

Pre každý z \(t\) problémov treba vypísať \(n\) popisov riešení, jeden pre odstránenie každého z vrcholov. Keďže T ešte nevie ktorú guličku odstráni, chcela by vedieť ako postupovať, bez ohľadu na to ktorý si vyberie. Vypíšte preto postupne riešenia pre prípad že odstráni prvú, druhú, atď. až po \(n\)-tú guličky.

V prvom riadku popisu riešenia vypíšte dve čísla – minimálny počet paličiek ktoré treba pridať aby sme strom zase pospájali (označme si ho \(e\)) a najmenší možný súčet kontrastov pridaných paličiek. Následne vypíšte \(e\) riadkov popisujúcich jeden spôsob, ako tieto hodnoty dosiahnúť – v každom riadku vypíšte čísla dvoch vrcholov, ktoré chcete spojiť. Medzi riešeniami pre jednotlivé vrcholy vypíšte prázdny riadok

Na získanie bodov za sady \(1\) a \(3\) vám stačí len vypísať \(e\), minimálny kontrast a následne \(e\) riadkov, pričom v každom riadku môžu byť ľubovoľné dve čísla. Čiže nikto nebude kontrolovať, či vami nájdený návod funguje.

Príklad

Input:

2
4
2 3
1 2
1 4
6
1 2
1 3
2 4
2 5
3 6

Output:

1 1
3 4

1 1
3 4

0 0

0 0

1 1
5 6

2 2
4 3
4 5

1 1
6 5

0 0

0 0

0 0

Vzorový vstup obsahuje dva stromy, pre ktoré budeme úlohu riešiť. V prvom z nich, keď odstránime vrchol \(1\), strom sa nám rozpadne na dve časti, jedna časť sú vrcholy \(2\) a \(3\) spojené hranou a druhá časť je samostatný vrchol \(4\). Pridaním hrany medzi vrcholy \(3\) a \(4\) strom opravíme. Kontrast tohto pospájania je rovný \(1\). Vieme si rozmyslieť, že menší počet hrán či kontrast nevieme dosiahnuť.

Prerekvizity: Kruskalov algoritmus (vedieť, ako a prečo funguje), union-find, binary-lifting (budeme používať takú tú tabuľku čo staviame keď chceme hladať LCA) a DFS.

Implementácia tejto úlohy je pomerne náročná a je ľahké sa v nej zamotať, ak si po prečítaní vzoráku stále nie si istý, ako na to, odporúčam začať preriešením si nasledujúcich úloh z testovača KSP: Sneh, Kostry, Počet komponentov, Najnižší spoločný predok, Vzdialenosť v strome.

A už dosť rečí, ide sa na vec!

Dolný odhad na odpoveď

Najprv sa zamyslíme, že koľko hrán musíme pridať po odobratí vrchola \(i\) a všetkých hrán, ktoré s ním susedia.

Nech jeho stupeň (teda počet hrán, ktoré s ním susedia) je \(d_i\). To znamená, že máme \(d_i\) komponentov, ktoré musíme pospájať. Ľahko si rozmyslíme, že vždy vieme pridať hranu ktorá spojí dva komponenty, a zároveň nikdy nevieme hranou naraz spojiť viac ako dva komponenty, preto v optimálnom riešení pridáme \(d_i - 1\) hrán.

Teraz musíme určiť, aký najmenší súčet hrán novo pridaných hrán vieme dosiahnuť. V prvom rade, keďže každá hrana spájajúca dva rôzne vrcholy má cenu aspoň \(1\), celkový súčet musí byť aspoň \(d_i - 1\). V prípade, že \(i\) nie je \(1\) ani \(n\), vieme urobiť ďalšie jednoduché pozorovanie: ak neexistuje hrana, ktorá spája vrchol s číslom menším ako \(i\) s vrcholom s číslom väčším ako \(i\), tak jedna novo pridaná hrana bude mať určite cenu aspoň dva. Prečo? Môžeme si uvedomiť, že každá takáto hrana má cenu aspoň dva, no a zároveň určite aspoň jednu takúto hranu potrebujeme, ináč by nový graf nebol súvislý (vieme ho rozdeliť na tie malé a na tie veľké vrcholy). To znamená, že v tomto prípade celkový súčet musí byť aspoň \(d_i\).

Vieme nájsť aj nejaké ďalšie dolné ohraničenia na to, že aká veľká musí byť tá výsledná cena? Nie? Ako uvidíme neskôr, tento odhad je skutočne optimálny. Zároveň existuje niekoľko spôsobov ako implementovať vyššie opísané počítanie hrán a cien, podľa presnej časovej zložitosti môžeme za toto riešenie získať 2 až 4 body. 

// O(n log n) riesenie, len pocitame odpoved
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

const int inf = 1e9 + 5; // nekonecno 
struct interval
    // reprezentuje interval [l, r], prvky pridavame cez upd () a [l, r] je vzdy najmensi interval ktory pokryva vsetky pridane prvky
{
    int l, r;
    interval() { l = inf, r = -inf; }
    void upd(int x) { l = min(l, x), r = max(r, x); }
};
vector<vector<int> > g; // vstupny graf
vector<vector<interval>> m;
// pre kazdy vrchol si zistime intervaly pokryvajuce komponenty na ktore sa strom rozpadne ked ho odstranime

vector<interval> s; // pre kazdy podstrom si zistime najmensie a najvacsie cislo vrcholu v nom
void dfs1(int u, int p)
{
    if (p != u)
    {
        g[u].erase(find(g[u].begin(), g[u].end(), p));
        // odstranime otca z mojich susedov aby tam ostali len moje deti
        // inak pozor ked pouzivas funkcie find a erase, casova zlozitost
        // je linearna od velkosti vrcholu z ktoreho mazes
    }
    s[u].l = s[u].r = u;
    for (int v : g[u])
    {
        dfs1(v, u);
        m[u].push_back(s[v]); // pridame interval podstromu dietata medzi moje intervaly
        s[u].upd(s[v].l);
        s[u].upd(s[v].r);
    }
}
// ideme pre kazdy vrchol spocitat interval prisluchajuci podstromu ktory ma jeho otec ked zoberieme prec tento vrchol
void dfs2(int u, interval otcov)
{
    vector<interval> pf(g[u].size() + 1), sf(g[u].size() + 1);
    pf[0] = otcov, sf[0] = otcov;
    pf[0].upd(u), sf[0].upd(u);
    // ok teraz detom musim pomoct spocitat tie intervaly tiez
    for (int i = 0; i < g[u].size(); i++)
    {
        pf[i + 1] = pf[i], pf[i + 1].upd(s[g[u][i]].l), pf[i + 1].upd(s[g[u][i]].r);
        sf[i + 1] = sf[i], sf[i + 1].upd(s[g[u][g[u].size() - 1 - i]].l), sf[i + 1].upd(s[g[u][g[u].size() - 1 - i]].r);
    }
    for (int i = 0; i < g[u].size(); i++)
    {
        interval now = pf[i];
        now.upd(sf[g[u].size() - i - 1].l), now.upd(sf[g[u].size() - i - 1].r);
        if (otcov.l != inf) m[u].push_back(otcov);
        dfs2(g[u][i], now);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); // rychle nacitavanie
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        // ideme vycistit vsetky polia - velmi dolezite pri ulohach s viacerymi vstupmi!
        g.assign(n, {}), s.assign(n, interval()), m.assign(n, {});
        // nacitame strom a spustime predpocitavanie
        for (int i = 0, u, v; i < n - 1; i++) cin >> u >> v, g[--u].push_back(--v), g[v].push_back(u);
        dfs1(0, 0);
        dfs2(0, interval());
        for (int i = 0; i < n; i++)
        {
            if (g[i].empty())
            {
                // som list - strom zostane cely aj bez mna, takze netreba nic robit
                cout << "0 0\n";
                continue;
            }
            int edges = g[i].size();
            if (!i) edges--; // koren nema otca
            int coins = edges;
            bool overlap = false; // mame interval ktory prekryva i
            for (interval in : m[i])
            {
                if (in.l <= i && i <= in.r)
                {
                    overlap = true;
                }
            }
            if (!overlap && 0 < i && i + 1 < n)
            {
                coins++;
            }
            cout << edges << " " << coins << "\n";
            for (int j = 0; j < edges; j++) cout << "0 0\n";
            cout << "\n";
        }
    }
    return 0;
}

Ako skonštruovať hľadanú množinu hrán?

Najprv taká úvaha na úvod, aký algoritmus by sme asi mohli použiť na postavenie toho nového grafu? Pridávame hrany tak aby sme mali súvislý graf a chceme čo najmenšiu cenu… To znie presne ako Kruskalov algoritmus. Čo by sme teda mohli urobiť je, že nejakým spôsobom nájdeme množinu hrán a potom na nich pustíme Kruskalov algoritmus aby našíel najlacnejší spôsob, ako vybrať podmnožinu hrán tak, aby bol výsledný graf súvislý.

Jeden jednoduchý príklad na takúto množinu sú hrany \((1, 2), (2, 3), ..., (i-1, i+1), ..., (n-1, n)\). Ľahko si môžeme rozmyslieť, že keďže sami o sebe tvoria súvislý graf (až na odstránený vrchol \(i\)), tak ak na rozpadnutom grafe + tejto množine spustíme Kruskalov algoritmus, dostaneme tiež súvislý graf. Dôležité pozorovanie: Iné hrany ako tie v tejto množine sa nám ani neoplatí používať. Skutočne, ak by sme v optimálnom riešení mali hranu medzi \((a, b), a + 1 < b\) (pre jednoduchosť uvažujme prípad \(b < i\), ostatné sa dokazujú podobne), mohli by sme ju nahradiť hranami \((a, a+1), (a+1, a+2), ..., (b-1, b)\), cena sa nezmení a ak boli predtým dva vrcholy spojené, určite budú spojené aj teraz. No lenže graf bol súvislý už aj predtým, a my sme teraz nejaké hrany pridali, to znamená, že sa vytvoril aspoň jeden nový cyklus. To znamená, že nejaké z nových hrán môžeme odstrániť, graf bude naďalej súvislý a dokonca ešte lacnejší a to je spor s tým, že sme predpokladali, že riešenie bolo optimálne.

Teraz už vieme urobiť \(O(n^2 \log n)\) riešenie za 4 body - postupne skúsime odobrať každý vrchol \(i\) a hrany s ním susediace, ostatným pôvodným hranám priradíme cenu \(0\), následne pridáme hrany \((1, 2), (2, 3), ..., (i-1, i+1), ..., (n-1, n)\) (každej priradíme cenu rovnú jej kontrastu) a nájdeme minimálnu kostru, ako sme ukázali, to je optimálna množina hrán ktorú chceme v grafe mať po tomto odobraní. Ak ešte tieto sady vyriešené nemáš, odporúčam si ísť toto riešenie ihneď naprogramovať skôr než sa pustíš do čítania zvyšku vzoráku. Môže sa ti neskôr hodiť aj ako bruteforce, proti ktorému možno testovať nefungujúce rýchlejšie riešenia.

Vzorové riešenie

Ako uvidíme zachvíľu, riešenie na plný počet bodov má v princípe rovnakú myšlienku, ale nemôžeme si dovoliť zakaždým staviať také veľké kostry. Označme si množiny vrcholov patriacich do toho istého komponentu po odobratí vrcholu \(i\) ako \(C_i (1), C_i (2), ..., C_i (d_i)\). Prichádza asi najtrikovejšie pozorovanie celej úlohy: Existuje optimálne riešenie, ktoré pridáva len hrany spomedzi \((min(C_i (1)) - 1, min(C_i (1)), ..., (min(C_i(d_i)) - 1,\) \(min(C_i (d_i)), (max(C_i (1)) - 1, max(C_i (1)), ..., (max(C_i (d_i)) - 1, max(C_i (d_i)),\) \((i-1, i+1)\).

Odporúčam sa v tomto momente zastaviť, nakresliť si niekoľko príkladov, že ako táto množina vyzerá pre konkrétne grafy a pokúsiť sa najprv samostatne dokázať, prečo je optimálna.

Dôkaz trikového pozorovania: Najprv ukážeme, že po pridaní všetkých navrhovaných hrán bude graf opäť súvislý. Ak by to nebola pravda, ozančme si \(a\) najmenší vrchol taký, že vrcholy \(a\) a \(a+1\) sú v rôznych komponentoch. Ak \(a \neq i, i-1\) tak potom \(a+1\) je zjavne najmenší vrchol vo svojom komponente (lebo zjavne všetky vrcholy \(1, ..., a\) sú v rovnakom komponente) a preto existuje hrana z \(a+1\) do \(a\) ktorú sme mohli pridať a zvýšiť tým počet súvislých komponentov. Ak \(a = i\) alebo \(a = i+1\), spor sa ukáže veľmi podobne, stačí sa pozrieť buď na dvojicu \((a, a+2)\), alebo na dvojicu \(b,b+1\), kde \(b\) je druhý najmenší vrchol taký, že \(b\) a \(b+1\) nie sú v rovnakom komponente. Teraz už len stačí ukázať, že kostra ktorú nájdeme bude skutočne najlacnejšia. To si vieme rozmyslieť tak, že sa pozrieme na to, čo spoja hrany dĺžky \(1\) - uvidíme, že dva komponenty, a teda potreba pridať hranu dĺžky \(2\), vznikne len a len vtedy, ak v pôvodonom grafe neexistovala hrana spájajúca vrchol s menším číslom ako \(i\) a vrchol s väčším číslom ako \(i\), teda cena nájdená týmto riešením sa zhoduje s dolným odhadom na cenu nájdeným na začiatku vzoráku.

Na to, aby sme efektívnejšie vedeli simulovať hladanie kostry ju nebudeme staviať na celom pôvodnom grafe, ale len na susedoch vrcholu \(i\). Keď rozmýšlame, či pridať nejakú hranu, nahradíme čísla vrcholov jej koncov číslami susedov vrcholu \(i\), do ktorých komponentov tieto vrcholy patria. Toto vieme robiť pomocou techniky známej ako binary lifting.

Pre samotný Kruskalov algoritmus si postavíme union find, ale aby sme nemuseli to pole predkov a veľkostí vždy vytvoriť nanovo, použijeme zakaždým to isté pole, ale medzi jednotlivými iteráciami mazania vrcholov vždy napravíme tie hodnoty, ktoré sme práve menili (čiže políčka zodpovedajúce susedom vrcholu \(i\)).

Tiež si na samotnom začiatku pre každú hranu spočítame minimum a maximum v dvoch komponentoch ktoré dostaneme po jej odobratí, toto sa dá napríklad pomocou dvoch DFS: zakoreníme si strom v ľubovoľnom vrchole a najprv spočítame minimum a maximum pre podstrom každého vrcholu a potom pomocou nich spočítame tieto hodnoty aj pre tie “opačné” podstromy.

Vďaka tomuto predpočítavaniu vieme nájsť riešenie po zmazaní vrcholu \(i\) v časovej zložitosti \(O(d_i \log n)\), čo sa sčíta na celkovú časovú zložitosť \(O(n \log n)\).

Pamäťová zložitosť je tiež \(O(n \log n)\), bottle-neck je pole predpočítaných hodnôt pre binary lifting.

// O(n log n) vzorove riesenie
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

const int inf = 1e9 + 5, logn = 17; // nekonecno a log n (aby sme vedeli najst k-teho predka)
struct interval 
    // reprezentuje interval [l, r], prvky pridavame cez upd () a [l, r] je vzdy najmensi interval ktory pokryva vsetky pridane prvky
{
    int l, r;
    interval() { l = inf, r = -inf; }
    void upd(int x) { l = min(l, x), r = max(r, x); }
};
vector<vector<int> > g; // vstupny graf
vector<int> d; // hlbky vrcholov
vector<vector<int> > l; // binary lifting
vector<vector<interval>> m;
// pre kazdy vrchol si zistime intervaly pokryvajuce komponenty na ktore sa strom rozpadne ked ho odstranime
vector<int> p; // rodicia v union finde (pozor, nie rodicia v strome)
// nasleduju klasicke union find funkcie
int root(int i) { return i == p[i] ? i : p[i] = root(p[i]); }
bool merge(int i, int j)
{
    i = root(i), j = root(j);
    if (i == j) return false;
    p[i] = j;
    return true;
}
// koniec union findu
vector<interval> s; // pre kazdy podstrom si zistime najmensie a najvacsie cislo vrcholu v nom
void dfs1(int u, int p)
{
    if (p != u)
    {
        g[u].erase(find(g[u].begin(), g[u].end(), p));
        // odstranime otca z mojich susedov aby tam ostali len moje deti
        // inak pozor ked pouzivas funkcie find a erase, casova zlozitost
        // je linearna od velkosti vrcholu z ktoreho mazes
    }
    // ideme vypocitat skoky 1, 2, 4, 8, ... vrcholov nahor aby sme vedeli hladat k-teho predka
    l[0][u] = p;
    for (int i = 1; i < logn; i++) l[i][u] = l[i - 1][l[i - 1][u]];
    s[u].l = s[u].r = u;
    for (int v : g[u])
    {
        d[v] = d[u] + 1;
        dfs1(v, u);
        m[u].push_back(s[v]); // pridame interval podstromu dietata medzi moje intervaly
        s[u].upd(s[v].l);
        s[u].upd(s[v].r);
    }
}
// funkcia ktora zisti, v podstrome ktoreho suseda u sa nachadza vrchol v
int cislo_suseda(int u, int v)
{
    if (d[v] <= d[u]) return (u == v ? u : l[0][u]);
    int k = d[v] - d[u] - 1;
    for (int i = logn - 1; i >= 0; i--) if ((1 << i) <= k) k -= (1 << i), v = l[i][v];
    if (l[0][v] == u) return v;
    return l[0][u];
}
// ideme pre kazdy vrchol spocitat interval prisluchajuci podstromu ktory ma jeho otec ked zoberieme prec tento vrchol
void dfs2(int u, interval otcov)
{
    vector<interval> pf(g[u].size() + 1), sf(g[u].size() + 1);
    pf[0] = otcov, sf[0] = otcov;
    pf[0].upd(u), sf[0].upd(u);
    // ok teraz detom musim pomoct spocitat tie intervaly tiez
    for (int i = 0; i < g[u].size(); i++)
    {
        pf[i + 1] = pf[i], pf[i + 1].upd(s[g[u][i]].l), pf[i + 1].upd(s[g[u][i]].r);
        sf[i + 1] = sf[i], sf[i + 1].upd(s[g[u][g[u].size() - 1 - i]].l), sf[i + 1].upd(s[g[u][g[u].size() - 1 - i]].r);
    }
    for (int i = 0; i < g[u].size(); i++)
    {
        interval now = pf[i];
        now.upd(sf[g[u].size() - i - 1].l), now.upd(sf[g[u].size() - i - 1].r);
        if (otcov.l != inf) m[u].push_back(otcov);
        dfs2(g[u][i], now);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); // rychle nacitavanie
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        // ideme vycistit vsetky polia - velmi dolezite pri ulohach s viacerymi vstupmi!
        g.assign(n, {}), s.assign(n, interval()), m.assign(n, {}), l.assign(logn, vector<int>(n, 0)), d.assign(n, 0), p.assign(n, -1);
        // nacitame strom a spustime predpocitavanie
        for (int i = 0, u, v; i < n - 1; i++) cin >> u >> v, g[--u].push_back(--v), g[v].push_back(u);
        dfs1(0, 0);
        dfs2(0, interval());
        for (int i = 0; i < n; i++)
        {
            if (g[i].empty())
            {
                // som list - strom zostane cely aj bez mna, takze netreba nic robit
                cout << "0 0\n";
                continue;
            }
            if (i) g[i].push_back(l[0][i]);
            for (int j : g[i]) p[j] = j;
            int edges = g[i].size() - 1, coins = 0;
            vector<pair<int, int> > ans; vector<pair<int, int> > v;
            // najdeme relevantne hrany a skusime ich pridat
            for (interval j : m[i]) v.push_back({ j.l, j.l - 1 }), v.push_back({ j.r, j.r + 1 });
            for (pair<int, int> j : v)
            {
                if (j.second >= 0 && j.second < n && j.second != i)
                {
                    // ideme si vypocitat ktorych dvoch mojich susedov sa tyka tato hrana
                    int a = cislo_suseda(i, j.first), b = cislo_suseda(i, j.second);
                    // pozrieme sa ci ju chceme zobrat
                    if (merge(a, b)) ans.push_back(j);
                }
            }
            // skontrolujeme ci este treba pridat tu specialnu hranu s cenou dva
            if (i && i + 1 < n && merge(cislo_suseda(i, i - 1), cislo_suseda(i, i + 1))) ans.push_back({ i - 1, i + 1 });
            // spocitame kolko minci nas to vlastne stalo a vypiseme odpoved
            for (pair<int, int> j : ans) coins += abs(j.first - j.second);
            cout << edges << " " << coins << "\n";
            for (pair<int, int> j : ans) cout << j.first + 1 << " " << j.second + 1 << "\n";
            cout << "\n";
        }
    }
    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ť.