Submission #1305359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305359		mayac	Valley (BOI19_valley)	C++20	23 / 100	332 ms	18840 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=(1e5)+1;
vector<int> h(maxn);
vector<vector<int>> jump(maxn,vector<int>(17,-1));
void initialize(){
    for(int j=1;j<17;j++){
        for(int i=0;i<maxn;i++){
            if(jump[i][j-1]!=-1)jump[i][j]=jump[jump[i][j-1]][j-1];
        }
    }
}
bool isf(int a,int b){
    //cout<<a<<" "<<b<<"\n";
    for(int i=16;i>0;i--){
        if((1<<i)<=(h[a]-h[b])){
            a=jump[a][i];
        }
    }
    //cout<<a<<" "<<b<<"\n";
    return (b==a)||(b==jump[a][0]);
}

int main(){
    ll n,s,k,e,a,b,c;
    cin>>n>>s>>k>>e;
    vector<pair<int,int>> ed(n);
    vector<vector<int>> g(n+1);
    vector<int> v(s);
    for(int i=1;i<n;i++){
        cin>>a>>b>>c;
        g[a].push_back(b);
        g[b].push_back(a);
        ed[i]={min(a,b),max(a,b)};
    }
    for(int i=0;i<s;i++)cin>>v[i];
    queue<int> q;h[e]=0;
    q.push(e);
    while(!q.empty()){
        a=q.front();q.pop();
        //cout<<a<<"\n";
        for(int u:g[a]){
            if(u!=jump[a][0]){
                jump[u][0]=a;
                h[u]=h[a]+1;
                q.push(u);
            }
        }
    }
    initialize();
    while(k--){
        cin>>b>>a;
        
        if(isf(a,ed[b].first)&&isf(a,ed[b].second)){
            cout<<"0\n";
        }else{
            cout<<"escaped\n";
        }
    }

}

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