Submission #937711

#	Time	Username	Problem	Language	Result	Execution time	Memory
937711		naneosmic	Valley (BOI19_valley)	C++14	100 / 100	357 ms	67012 KiB

valley

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int long long
#define endl "\n"
using namespace std;
vector<vector<pair<int,int>>>tree;
vector<bool>village;
vector<pair<int,int>>edges;
vector<int>depth;
vector<int>closest;
vector<int>visited;
vector<vector<pair<int,int>>>lifting;
vector<vector<int>>lifting2;
int n,e;
void dfs(int i,int k){
    if(visited[i]==true)return;
    visited[i]=true;
    depth[i]=k;
    int N=tree[i].size();
    for(int j=0;j<N;j++){
        dfs(tree[i][j].first,k+1);
    }
}
int dfs2(int i){
    if(visited[i]==true)return -1;
    visited[i]=true;
    int N=tree[i].size();
    int distance=LLONG_MAX;
    for(int j=0;j<N;j++){
        pair<int,int>a=tree[i][j];
        int current=dfs2(a.first);
        if(current!=-1&&current!=LLONG_MAX){
            current+=a.second;
            distance=min(current,distance);
        }
    }
    if(village[i]==true){
        return closest[i]=0;
    }
    closest[i]=distance;
    return distance;
}
void dfs3(int i,int p,int l){
    if(visited[i]==true)return;
    visited[i]=true;
    if(i!=e){
        pair<int,int>a=make_pair(p,l);
        int lim=1;
        while(lim<=depth[i]){
            lifting[i].push_back(a);
            int N1=lifting[i].size();
            int N2=lifting[a.first].size();
            if(N1<=N2){
                a.second+=lifting[a.first][N1-1].second;
                a.first=lifting[a.first][N1-1].first;
            }
            lim*=2;
        }
    }
    
    int N=tree[i].size();
    for(int j=0;j<N;j++){
        pair<int,int>a=tree[i][j];
        dfs3(a.first,i,a.second);
    }
}
int bit(int k){
    for(int i=62;i>=0;i--){
        if(((1LL<<i)&k)!=0){
            return i;
        }
    }
    return -1;
}
pair<int,int>lift(int i,int k){
    pair<int,int>ans;
    if(k==0){
        return make_pair(i,0);
    }else if(k==1){
        return lifting[i][0];
    }else{
        int l=bit(k);
        int b=(1LL<<l);
        ans=lifting[i][l];
        pair<int,int>c=lift(ans.first,k-b);
        ans.first=c.first;
        ans.second+=c.second;
    }
    return ans;
}
void dfs4(int i){
    if(visited[i]==true)return;
    visited[i]=true;
    if(i!=e){
        int ancestor=i;
        int a=closest[i];
        int lim=1;
        while(lim<=depth[i]){
            lifting2[i].push_back(a);
            int N1=lifting2[i].size();
            ancestor=lifting[i][N1-1].first;
            int val=lifting[i][N1-1].second;
            int N2=lifting2[ancestor].size();
            if(N1<=N2){
                int x=lifting2[ancestor][N1-1];
                if(x!=LLONG_MAX){
                    a=min(x+val,lifting2[i][N1-1]);
                }
            }
            lim*=2;
        }
    }
    int N=tree[i].size();
    for(int j=0;j<N;j++){
        pair<int,int>g=tree[i][j];
        dfs4(g.first);
    }
}
int end(int i,int k){
    int l=bit(k);
    int b=(1LL<<l);
    if(k==b){
        return lifting2[i][l];
    }
    int ans=lifting2[i][l];
    int NODE=lifting[i][l].first;
    int DIST=lifting[i][l].second;
    int sec=end(NODE,k-b);
    ans=min(ans,max(sec,sec+DIST));
    return ans;
}
void solve(){
    int r,i;
    cin>>r>>i;
    r--;
    i--;
    
    pair<int,int>edge=edges[r];
    int node;
    if(depth[edge.first]>depth[edge.second]){
        node=edge.first;
    }else{
        node=edge.second;
    }
    int d1=depth[i];
    int d2=depth[node];
    if(d1<d2){
        cout<<"escaped\n";
        return;
    }
    int dist=d1-d2;
    pair<int,int>par=lift(i,dist);
    if(par.first!=node){
        cout<<"escaped\n";
        return;
    }
    if(closest[node]==LLONG_MAX){
        cout<<"oo\n";
        return;
    }
    cout<<end(i,dist+1)<<endl;
    return;
}
signed main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int s,q;
    cin>>n>>s>>q>>e;
    e--;
    tree.resize(n);
    edges.resize(n-1);
    village.resize(n,false);
    visited.resize(n,false);
    depth.resize(n);
    closest.resize(n);
    lifting.resize(n);
    lifting2.resize(n);
    for(int i=0;i<n-1;i++){
        int a,b,w;
        cin>>a>>b>>w;
        a--;
        b--;
        pair<int,int>a1=make_pair(a,w);
        pair<int,int>b1=make_pair(b,w);
        tree[a].push_back(b1);
        tree[b].push_back(a1);
        edges[i]=make_pair(a,b);
    }
    for(int i=0;i<s;i++){
        int a;
        cin>>a;
        a--;
        village[a]=true;
    }
    village[e]=true;
    dfs(e,0);
    for(int i=0;i<n;i++)visited[i]=false;
    dfs2(e);
    for(int i=0;i<n;i++)visited[i]=false;
    dfs3(e,0,0);
    for(int i=0;i<n;i++)visited[i]=false;
    dfs4(e);
    while(q--)solve();
}

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