Submission #207134

#	Time	Username	Problem	Language	Result	Execution time	Memory
207134		brcode	Valley (BOI19_valley)	C++14	100 / 100	891 ms	61392 KiB

valley

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e5+5;
vector<pair<long long,long long>> v1[MAXN];
long long h[MAXN];
long long cities[MAXN];
long long distroot[MAXN];
long long p[MAXN];
long long dp[MAXN][25];
long long nearest[MAXN];
long long dp2[MAXN][25];
vector<pair<long long,long long>> edges;
void dfs(long long curr,long long par){
    //cout<<curr<<endl;
    if(curr!=par){
        h[curr] = h[par]+1;
        
    }
    
    if(cities[curr]){
        nearest[curr] = 0;
    }else{
        nearest[curr] = 1e18;
    }
    p[curr] = par;
    dp[curr][0] = par;
    for(auto x:v1[curr]){
        if(x.first!=par){
            distroot[x.first] = distroot[curr]+ x.second;
           dfs(x.first,curr);  
           nearest[curr] = min(nearest[curr],nearest[x.first]+x.second);
           
        }
        
        
    }
    for(auto x:v1[curr]){
        if(x.first!=par){
           
          dp2[x.first][0] = min(nearest[x.first],nearest[curr]+x.second);
           
        }
        
        
    }
    
}
bool isanc(long long x,long long y){
    for(long long j=20;j>=0;j--){
        if(h[dp[x][j]]>=h[y]){
            x = dp[x][j];
        }
    }
    return x == y;
}
long long dist(long long x,long long y){
    return distroot[x]-distroot[y];
}
long long jump(long long x,long long y){
    long long ans = nearest[x];
    long long og = x;
    for(long long j=20;j>=0;j--){
        if(h[dp[x][j]]>=h[y]){
            
            ans = min(ans,dp2[x][j]+dist(og,x));
            //cout<<x<<" "<<dp2[x][j]<<endl;
            x = dp[x][j];
            //cout<<ans<<endl;
        }
        
    }
    return ans;
}

int main() {
    long long n,s,q,e;
    edges.push_back(make_pair(0,0));
    cin>>n>>s>>q>>e;
    for(long long i=1;i<n;i++){
        long long x,y,w;
        cin>>x>>y>>w;
        v1[x].push_back(make_pair(y,w));
        v1[y].push_back(make_pair(x,w));
        edges.push_back(make_pair(x,y));
    }
    for(long long i=1;i<=s;i++){
        long long x;
        cin>>x;
        cities[x] = 1;
    }
    
    for(long long i=0;i<=20;i++){
        for(long long j=1;j<=n;j++){
            dp[j][i] = -1;
            dp2[j][i] = 1e18;
        }
    }
    dfs(e,e);
   for(long long i=1;i<=n;i++){
      // cout<<dp2[i][0]<<endl;
   }
    for(long long i=1;i<=20;i++){
        for(long long j=1;j<=n;j++){
            if(dp[j][i-1] == -1){
                dp[j][i] = -1;
            }else{
                dp[j][i] = dp[dp[j][i-1]][i-1];
            }
        }
    }
    for(long long i=1;i<=20;i++){
        for(long long j=1;j<=n;j++){
            if(dp[j][i-1] == -1){
                dp2[j][i] = 1e18;
            }else{
                dp2[j][i] = min(dp2[j][i-1],dp2[dp[j][i-1]][i-1]+dist(j,dp[j][i-1]));
            }
        }
    }
   
    while(q--){
        long long ind,r;
        cin>>ind>>r;
        long long x = edges[ind].first;
        long long y = edges[ind].second;
        if(h[x]>h[y]){
            swap(x,y);
        }
        if(isanc(r,x) && isanc(r,y)){
            
            if(jump(r,y) == 1e18){
                cout<<"oo"<<endl;
            }else{
                
                cout<<jump(r,y)<<endl;
            }
        }else{
            cout<<"escaped"<<endl;
        }
    }
    
}

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