Submission #1327585

#TimeUsernameProblemLanguageResultExecution timeMemory
1327585lizaValley (BOI19_valley)C++20
100 / 100
249 ms42504 KiB
#include <bits/stdc++.h>

using namespace std;

int n, s, q, e;
int const N = 100005;
vector<pair<int, int>> g[N];
vector <int> et;
pair<int, int> eti[N];
vector<int> shops;
map<int, int> isshop;
pair<int, int> roads[N];
void fet(int u, int p)
{
    et.push_back(u);
    eti[u]={et.size()-1, 0};
    for(auto i: g[u])
    {
        if(i.first == p)continue;
        fet(i.first, u);
    }
    et.push_back(u);
    eti[u]={eti[u].first, et.size()-1};
}

long long closest[N];
int const LOG = log2(N) + 2;
int par[N][LOG];
long long dist[N];
void clo(int u, int p)
{
    long long rez=1e18+5;
    closest[u]=1e18+5;
    par[u][0] = p;
    for(int i = 1; i < LOG; i++)
    {
        par[u][i]=par[par[u][i-1]][i-1];
    }
    for(auto i: g[u])
    {
        if(i.first == p)continue;
        dist[i.first] =dist[u]+i.second;
        clo(i.first, u);
        //if(rez==-1) rez = closest[i.first]+i.second;
        rez=min(rez, closest[i.first]+i.second);
    }

    if(isshop[u])
    {
        closest[u]=0;
    }
    else
    {
        closest[u]=rez;
    }
}

long long best[N][LOG];
void dfs(int u, int p)
{
    best[u][0] = dist[u] - dist[p] + closest[p];
    for(int i = 1; i < LOG; i++)
    {
        int jump = par[u][i-1];

        best[u][i] = min(best[u][i-1], dist[u]-dist[jump]+best[jump][i-1]);
    }
    for(auto i: g[u])
    {
        if(i.first==p)continue;
        dfs(i.first, u);
    }
}

long long get_best(int r, int u)
{
    long long cur = closest[r], di = 0;
    for(int i = LOG-1; i >= 0; i--)
    {
        int jump = par[r][i];
        if(eti[jump].first <= eti[u].first && eti[u].second <= eti[jump].second)
        {
            continue;
        }
        cur = min(cur, di+best[r][i]);
        di+=dist[r]-dist[jump];
        r=jump;

    }
    return cur;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s >> q >> e;
    for(int i = 0; i < n-1; i++)
    {
        int a, b, w; cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
        roads[i+1]={a, b};
    }
    for(int i =0; i < s; i++)
    {
        int x; cin >> x;
        shops.push_back(x);
        isshop[x]=1;
    }
    fet(e, e);
    clo(e, e);
    dfs(e, e);
    while(q--)
    {
        int i, r; cin >> i >> r;
        if(eti[roads[i].first].first <= eti[r].first && eti[roads[i].second].first <= eti[r].first && eti[roads[i].first].second >= eti[r].second && eti[roads[i].second].second >= eti[r].second)
        {
            int x = roads[i].first;
            if(dist[roads[i].first] > dist[roads[i].second])
            {
                x = roads[i].second;
            }
            long long rez = get_best(r, x);
            if(rez==1e18+5)
            {
                cout << "oo\n";
            }
            else
            {
                cout << rez << "\n";
            }
        }
        else
        {
            cout << "escaped\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...