Submission #207132

#	Time	Username	Problem	Language	Result	Execution time	Memory
207132		brcode	Valley (BOI19_valley)	C++14	0 / 100	683 ms	29672 KiB

valley

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
vector<pair<int,int>> v1[MAXN];
int h[MAXN];
int cities[MAXN];
int distroot[MAXN];
int p[MAXN];
int dp[MAXN][25];
int nearest[MAXN];
int dp2[MAXN][25];
vector<pair<int,int>> edges;
void dfs(int curr,int par){
    //cout<<curr<<endl;
    if(curr!=par){
        h[curr] = h[par]+1;
        
    }
    
    if(cities[curr]){
        nearest[curr] = 0;
    }else{
        nearest[curr] = 1e9;
    }
    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(int x,int y){
    for(int j=20;j>=0;j--){
        if(h[dp[x][j]]>=h[y]){
            x = dp[x][j];
        }
    }
    return x == y;
}
int dist(int x,int y){
    return distroot[x]-distroot[y];
}
int jump(int x,int y){
    int ans = nearest[x];
    int og = x;
    for(int 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() {
    int n,s,q,e;
    edges.push_back(make_pair(0,0));
    cin>>n>>s>>q>>e;
    for(int i=1;i<n;i++){
        int 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(int i=1;i<=s;i++){
        int x;
        cin>>x;
        cities[x] = 1;
    }
    
    for(int i=0;i<=20;i++){
        for(int j=1;j<=n;j++){
            dp[j][i] = -1;
            dp2[j][i] = 1e9;
        }
    }
    dfs(e,e);
   for(int i=1;i<=n;i++){
      // cout<<dp2[i][0]<<endl;
   }
    for(int i=1;i<=20;i++){
        for(int 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(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            if(dp[j][i-1] == -1){
                dp2[j][i] = 1e9;
            }else{
                dp2[j][i] = min(dp2[j][i-1],dp2[dp[j][i-1]][i-1]+dist(j,dp[j][i-1]));
            }
        }
    }
   
    while(q--){
        int ind,r;
        cin>>ind>>r;
        int x = edges[ind].first;
        int y = edges[ind].second;
        if(h[x]>h[y]){
            swap(x,y);
        }
        if(isanc(r,x) && isanc(r,y)){
            
            if(jump(r,y) == 1e9){
                cout<<"oo"<<endl;
            }else{
                
                cout<<jump(r,y)<<endl;
            }
        }else{
            cout<<"escaped"<<endl;
        }
    }
    
}

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