Submission #1011345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011345		alexdd	Valley (BOI19_valley)	C++17	100 / 100	118 ms	38996 KiB

valley

#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int n,s,q,e;
vector<pair<int,int>> con[100005];
pair<int,int> edges[100005];
int tin[100005],tout[100005],timer;
bool iss[100005];
long long depth[100005];
long long mindist[100005];

int anc[1000005][17];
long long min_anc[1000005][17];

void dfs(int nod, int par)
{
    tin[nod]=++timer;
    mindist[nod]=INF;
    if(iss[nod]) mindist[nod]=0;
    for(auto [adj,c]:con[nod])
    {
        if(adj!=par)
        {
            anc[adj][0]=nod;
            depth[adj] = depth[nod]+c;
            dfs(adj,nod);
            mindist[nod] = min(mindist[nod], mindist[adj]+c);
        }
    }
    //cout<<nod<<" "<<mindist[nod]<<" mindist\n";
    min_anc[nod][0] = mindist[nod] - depth[nod];
    if(mindist[nod]==INF) min_anc[nod][0]=INF;
    tout[nod]=++timer;
}
bool isanc(int x, int y)
{
    if(tin[x]<=tin[y] && tout[x]>=tout[y])
        return 1;
    return 0;
}
long long calc_min(int nod, int lim)
{
    long long aux=INF;
    //cout<<nod<<" "<<lim<<" calc_min\n";
    for(int p=16;p>=0;p--)
    {
        if(!isanc(anc[nod][p],lim))
        {
            aux = min(aux, min_anc[nod][p]);
            nod = anc[nod][p];
        }
    }
    aux = min(aux, min_anc[nod][0]);
    return aux;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>s>>q>>e;
    int u,v,w;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v>>w;
        con[u].push_back({v,w});
        con[v].push_back({u,w});
        edges[i] = {u,v};
    }
    for(int i=1;i<=s;i++)
    {
        cin>>u;
        iss[u]=1;
    }
    dfs(e,-1);
    anc[e][0]=e;
    for(int p=1;p<17;p++)
    {
        for(int i=1;i<=n;i++)
        {
            anc[i][p] = anc[anc[i][p-1]][p-1];
            min_anc[i][p] = min(min_anc[i][p-1], min_anc[anc[i][p-1]][p-1]);
        }
    }
    for(int i=1;i<n;i++)
        if(anc[edges[i].first][0] == edges[i].second)
            swap(edges[i].first, edges[i].second);
    while(q--)
    {
        cin>>u>>v;
        if(isanc(edges[u].second,v))
        {
            long long x = calc_min(v,edges[u].first);
            if(x>=INF) cout<<"oo\n";
            else cout<<x+depth[v]<<"\n";
        }
        else
        {
            cout<<"escaped\n";
        }
    }
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41