15157. Neptun [AL_07_08]

Zadanie:
https://pl.spoj.com/problems/AL_07_08

Skrócony opis problemu:

Mamy dane graf nieskierowany składający się z $v$ wierzchołków (ang. vertex), które numerujemy od 0 i $e$ krawędzi (and. edges). Następnie mamy podane $n$ i $n$ wierzchołków reprezentujących stolice państw, opisanych ich numerem oraz wartością $m$. Każda stolica podbija wszystkie sąsiednie i niepodbite jeszcze tereny (wierzchołki) po czasie $m$. Po czasie $2m$ każdy z nowopodbitych terenów podbija z kolei wszystkich swoich [niepoditych] sąsiadów, i tak do zużycia (podbicia) wszystkich wierzchołków. Następnie podana jest liczba $q$ (ang. query) oznaczająca ilość zapytań. Każde zapytanie składa się z dwóch liczb: $a$, $b$ i należy dla niego wypisać numer jednej ze $n$ stolic (numer, a nie wartość tak więc jeśli trzecią stolicą jest 5, to jej numerem jest 3), która okupuje w momencie $b$ teren (wierzchołek) $a$ Jeśli w momencie $b$ teren jest niezajęty, to należy wypisać "-". Jeśli w danej jednostce czasu jakiś teren chcą podbić dwie stolice to podbija go ta z mniejszym numerem.

Rozwiązanie:

Wszystkie $n$ stolic dodajemy do seta jako trójkę (moment podbicia, wartość stolicy, $m$ stolicy). Stolice mają moment podbicia równy 0. Następnie zdejmujemy trójkę $min$ o najmniejszym momencie podbicia, a jeśli jest ich więcej to o najmniejszym numerze stolicy. W trójce mamy wartość, a nie numer stolicy, ale będziemy mieć tablicę $who$, w której dla każdego wierzchołka będziemy przechowywać numer stolicy, do której należy. Tablica ta na początku będzie pusta, oprócz stolic, których numery będą podane. Tak więc jeśli trzecią stolicą jest 5, to $who[5]=3$. Na początku wszystkie trójki w secie będą miały moment podbicia 0 (bo będą to same stolice), więc wybierzemy z nich tą o numerze 1 (numerujemy od 1). Następnie dla wszystkich niepodbitych sąsiadów $min$ sprawdzamy czy zostały już podbite i jeśli nie, to czy moment ich podbicia jest większy od momentu podbicia $min$ powiększonego o $m$ stolicy dla $min$ i jeśli tak to aktualizujemy w tablicach $when$ i $who$ komórkę dla tego sąsiada (w tablicy $who$ trzymamy numer stolicy, do której należy dany wierzchołek, a w tablicy $when$ trzymamy moment, w którym został podbity przez tę stolicę). Innymi słowy, dla wierzchołków podbitych sprawdzamy czy przypadkiem ktoś wcześniej ich nie podbił. Jeśli bowiem ktoś podbije jakiś wierzchołek, to zostanie on na zawsze jego. A więc wystarczy tylko znaleźć dla każdego wierzchołka kto pierwszy do niego dotarł. Tak więc powtórzę - sprawdzamy czy wierzchołek nie został podbity lub zostałby podbity później niż dla $min$ i jeśli tak to aktualizujemy jego tablicę i dodajemy go do seta, jako trójkę (moment podbicia $min+$m$ stolicy $min$, wartość stolicy $min$, $m$ stolicy $min$). Po przetworzeniu każdego $min$ usuwamy go z seta i sprawdzamy następnego, aż set będzie pusty.

Dla każdego zapytania wystarczy zatem sprawdzić wartości tablicy $who$ i $when$ dla wierzchołka $a$. Jeśli $who[a]=0$ to znaczy, że $a$ nie zostało podbite (a więc graf jest niespójny), więc trzeba wypisać "-". Jeśli $when[a] > b$ to znaczy, że $a$ zostanie podbite po momencie $b$ i też należy wypisać "-". W przeciwnym wypadku należy wypisać $who[a]$.

Pozostaje kwestia implementacji. Ja będę poniżej uznawał, że jeśli $when[x]=0$ to $x$ nie zostało podbite. W każdym teście jest bowiem tylko 1 zestaw danych, więc mogę sobie zrobić zmienną globalną, w której od razu są same 0 i nie muszę jej zerować. W związku z tym dla stolic ustawiam $when[s]=-1$, bo nie psuje to powyższych warunków.

Złożoność: $O(v \log v + q)$, bo pesymistycznie każdego wierzchołka dodajemy najpierw do seta w czasie logarytmicznym, a potem go usuwamy (w czasie stałym, jako że to pierwszy element). Na zapytania odpowiadamy w czasie stałym.

Ostateczny algorytm:

struct triple
{
    int a, b, m;
    bool operator<(const triple &x)const
    {
        if(a == x.a)
            return b < x.b;
        return a < x.a;
    }
    triple() {}
    triple(int x, int y, int z) : a(x), b(y), m(z) {}
};

set<triple> heap;
vector<int> graph[1609];
int who[1609], when[1609];

int main()
{
    int v, e, n, q, i, a, b, m;
    triple t;

    get(v, e);
    while(e--)
    {
        get(a, b);
        graph[a].push_back(b);
        graph[b].push_back(a); // graf nieskierowany
    }
    get(n);
    for(i = 1; i <= n; ++i) // numerowanie od 1
    {
        get(a, m);
        heap.insert(triple(0, a, m)); // dodajemy stolicę z momentem podbicia 0
        who[a] = i; when[a] = -1; // ustawiamy tablice dla stolic
    }
    while(!heap.empty())
    {
        t = *heap.begin(); // zdejmujemy min
        heap.erase(heap.begin()); // usuwamy min
        for(i = 0; i < graph[t.b].size(); ++i) // dla każdego sąsiada
            if(!when[graph[t.b][i]] || when[graph[t.b][i]] > t.a+t.m || (when[graph[t.b][i]] == t.a+t.m && who[t.b] < who[graph[t.b][i]])) // jeśli sąsiad nie został podbity lub został, ale ktoś go wcześniej podbił lub został, ale ktoś go podbił w tym samym czasie o mniejszym numerze
            {
                when[graph[t.b][i]] = t.a+t.m; // to aktualizuj
                who[graph[t.b][i]] = who[t.b];
                heap.insert(triple(t.a+t.m, graph[t.b][i], t.m)); // i go dodaj do seta
            }
    }
    get(q);
    while(q--)
    {
        get(a, b);
        if(b < when[a] || !who[a])
            print("-");
        else
            print(who[a]);
    }
}

Testy