Submission #650282

#TimeUsernameProblemLanguageResultExecution timeMemory
650282MEGalodonValley (BOI19_valley)C++14
0 / 100
352 ms19628 KiB
#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;
vector<int> adj_lst[MAXN];
int depth[MAXN];
int par[MAXN][20];
void dfs(int i){
    for( int j : adj_lst[i] ){
        if( depth[j] ) continue;
        par[j][0] = i; depth[j] = depth[i]+1;
        dfs(j);
    }
}
vector<pair<int, int>> edgeList;
int jmp(int i, int diff){
    for( int k{19} ; k >= 0 ; --k ) if( diff&(1<<k) ) i = par[i][k];
    return i;
}
int main(){
    int nodes, edges, shops, Q, E;
    cin>>nodes>>shops>>Q>>E; edges = nodes-1;
    while( edges-- ){
        int u, v, w;
        cin>>u>>v>>w;
        adj_lst[u].push_back(v);
        adj_lst[v].push_back(u);
        edgeList.push_back({u, v});
    }
    depth[E] = 1;
    dfs(E);
    //for( int i{1} ; i <= nodes ; ++i ) cout<<depth[i]<<" "; cout<<'\n';
    while( shops-- ){ int x; cin>>x; }
    for( int k{1} ; k < 20 ; ++k ) for( int i{1} ; i <= nodes ; ++i ) par[i][k] = par[par[i][k-1]][k-1];
    while( Q-- ){
        int i, r;
        cin>>i>>r;
        auto x = edgeList[i-1];
        int u = x.first, v = x.second;
        if( depth[u] < depth[v] ) swap(u, v);
        if( depth[r] < depth[u] ) cout<<"escaped\n";
        else{
            int diff = depth[r] - depth[u];
            int rch = jmp(r, diff);
            //cout<<diff<<" "<<rch<<'\n';
            if( rch == u ) cout<<r<<'\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...