제출 #1347091

#제출 시각아이디문제언어결과실행 시간메모리
1347091SSKMFValley (BOI19_valley)C++20
100 / 100
111 ms52788 KiB
#include <bits/stdc++.h>
using namespace std;

vector < pair <int , int> > adiacenta[100001];
pair < int , pair <int64_t , int64_t> > urmatorul[100001][17];
int __nod[100001][2] , adancime[100001];
int64_t minim[100001];
bool tip[100001];

void Parcurgere (const int nod)
{
    minim[nod] = (tip[nod] ? 0 : INT64_MAX);
    for (auto& vecin : adiacenta[nod]) {
        if (vecin.first != urmatorul[nod][0].first)
        {
            adancime[vecin.first] = adancime[nod] + 1;
            urmatorul[vecin.first][0].second.first = vecin.second;
            urmatorul[vecin.first][0].first = nod;

            Parcurgere(vecin.first);

            if (minim[vecin.first] != INT64_MAX)
                { minim[nod] = min(minim[nod] , minim[vecin.first] + vecin.second); }
        }
    }
    
    urmatorul[nod][0].second.second = minim[nod];
}

void Build (const int nod)
{
    for (int exponent = 1 ; (1 << exponent) <= adancime[nod] ; exponent++)
    {
        urmatorul[nod][exponent].first = urmatorul[urmatorul[nod][exponent - 1].first][exponent - 1].first;
        urmatorul[nod][exponent].second.first = urmatorul[nod][exponent - 1].second.first + urmatorul[urmatorul[nod][exponent - 1].first][exponent - 1].second.first;
        urmatorul[nod][exponent].second.second = min(urmatorul[nod][exponent - 1].second.second , (urmatorul[urmatorul[nod][exponent - 1].first][exponent - 1].second.second == INT64_MAX ? INT64_MAX : urmatorul[urmatorul[nod][exponent - 1].first][exponent - 1].second.second + urmatorul[nod][exponent - 1].second.first));
    }

    for (auto& vecin : adiacenta[nod]) {
        if (vecin.first != urmatorul[nod][0].first)
            { Build(vecin.first); }
    }
}

pair <int , int64_t> Jump (int nod , int adancime)
{
    int64_t termen = 0 , __minim = INT64_MAX;
    for (int exponent = 16 ; exponent >= 0 ; exponent--) {
        if (adancime & (1 << exponent))
        {
            if (urmatorul[nod][exponent].second.second != INT64_MAX)
                { __minim = min(__minim , urmatorul[nod][exponent].second.second + termen); }

            termen += urmatorul[nod][exponent].second.first;
            nod = urmatorul[nod][exponent].first;
        }
    }

    if (minim[nod] != INT64_MAX)
        { __minim = min(__minim , minim[nod] + termen); }

    return {nod , __minim};
}

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

    int numar_noduri , special , numar_intrebari , radacina;
    cin >> numar_noduri >> special >> numar_intrebari >> radacina;

    for (int indice = 1 , cost ; indice < numar_noduri ; indice++)
    {
        cin >> __nod[indice][0] >> __nod[indice][1] >> cost;
        adiacenta[__nod[indice][0]].emplace_back(__nod[indice][1] , cost);
        adiacenta[__nod[indice][1]].emplace_back(__nod[indice][0] , cost);
    }

    while (special--)
    {
        int nod;
        cin >> nod;
        tip[nod] = true;
    }

    Parcurgere(radacina);
    Build(radacina);

    while (numar_intrebari--)
    {
        int indice , inceput;
        cin >> indice >> inceput;

        pair <int , int> muchie = {__nod[indice][0] , __nod[indice][1]};
        if (adancime[muchie.first] > adancime[muchie.second])
            { swap(muchie.first , muchie.second); }

        if (adancime[muchie.second] > adancime[inceput])
            { cout << "escaped\n"; continue; }

        const pair <int , int64_t> candidat = Jump(inceput , adancime[inceput] - adancime[muchie.second]);
        if (candidat.first != muchie.second)
            { cout << "escaped\n"; continue; }
        if (candidat.second == INT64_MAX)
            { cout << "oo\n"; continue; }
        cout << candidat.second << '\n';
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...