제출 #937391

#제출 시각아이디문제언어결과실행 시간메모리
937391naneosmicValley (BOI19_valley)C++14
23 / 100
191 ms50376 KiB
#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; 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 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; } cout<<0<<endl; } 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); 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); cout<<endl; while(q--)solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...