Submission #650284

#	Time	Username	Problem	Language	Result	Execution time	Memory
650284		MEGalodon	Valley (BOI19_valley)	C++14	23 / 100	404 ms	22300 KiB

valley

#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<<"0"<<'\n';
            else cout<<"escaped\n";
        }
    }
    return 0;
}

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