제출 #563137

#제출 시각아이디문제언어결과실행 시간메모리
563137inluminasValley (BOI19_valley)C++17
23 / 100
374 ms40312 KiB
#include"bits/stdc++.h" using namespace std; #define ll long long #define endl "\n" #define fastio ios_base::sync_with_stdio(false) #define inf LLONG_MAX #define l first #define r second struct ed{ ll v=0,w=0,s=-1,val=1e9; ed(ll _v=0,ll _w=0,ll _s=0,ll _val=0){ v=_v,w=_w,s=_s,val=_val; } }; const ll lmt=2e5+10; vector<ed>adj[lmt]; ll n,S,q,e,par[lmt][20],to[lmt],top[lmt],lvl[lmt]; ll till[lmt],tillp[lmt]; bool ok[lmt]; void dfs(ll u,ll p){ for(ed x:adj[u]){ if(x.v==p) continue; lvl[x.v]=lvl[u]+1; dfs(x.v,u); par[x.v][0]=u; } } void dfS(ll u,ll p){ if(ok[u]){ till[u]=0,to[u]=u; } for(ed &x:adj[u]){ if(x.v==p) continue; dfS(x.v,u); x.s=to[x.v],x.val=till[x.v]; if(till[u]>x.val+x.w){ till[u]=x.val+x.w,to[u]=x.s; } } } void dFs(ll u,ll p){ ll mn=1e17+10,mn2=1e17+10,idx=0,idx2=0; for(ed &x:adj[u]){ if(x.v==p){ x.s=top[u],x.val=tillp[u]-x.w; continue; } top[x.v]=top[u],tillp[x.v]=tillp[u]+x.w; if(x.val+x.w<mn){ mn2=mn,idx2=idx; mn=x.val+x.w,idx=x.s; }else if(x.val+x.w<mn2){ mn2=x.val+x.w,idx2=x.s; } } for(ed &x:adj[u]){ if(x.v==p) continue; if(x.s==idx){ if(tillp[x.v]>mn2+x.w){ tillp[x.v]=mn2+x.w,top[x.v]=idx2; } }else{ if(tillp[x.v]>mn+x.w){ tillp[x.v]=mn+x.w,top[x.v]=idx; } } } for(ed x:adj[u]){ if(x.v==p) continue; dFs(x.v,u); } } ll lca(ll p,ll q){ if(lvl[p]<lvl[q]) swap(p,q); for(ll i=19;i>=0;i--){ if(lvl[p]-(1<<i)>=lvl[q]){ p=par[p][i]; } } if(p==q) return p; for(ll i=19;i>=0;i--){ if(par[p][i]!=-1 && par[p][i]!=par[q][i]){ p=par[p][i],q=par[q][i]; } } return par[p][0]; } ll Up(ll p,ll val){ for(ll j=19;j>=0;j--){ if(val>=(1<<j) && par[p][j]!=-1){ p=par[p][j]; val-=(1<<j); } } return p; } bool yes(ll o,ll p,ll q){ ll l=lca(p,q); if(lvl[l]<=lvl[o] && lvl[o]<=lvl[p] && o==Up(p,lvl[p]-lvl[o])) return true; else if(lvl[l]<=lvl[o] && lvl[o]<=lvl[q] && o==Up(q,lvl[q]-lvl[o])) return true; return false; } int main(){ fastio; cin>>n>>S>>q>>e; for(ll i=0;i<=n;i++){ for(ll j=0;j<20;j++) par[i][j]=-1; } vector<pair<ll,ll>>egg; for(ll i=1;i<n;i++){ ll u,v; ll w; cin>>u>>v>>w; egg.push_back({u,v}); adj[u].push_back(ed(v,w,0,1e16+10)); adj[v].push_back(ed(u,w,0,1e16+10)); } for(ll i=1;i<=S;i++){ ll u; cin>>u; ok[u]=1; } dfs(1,0); for(ll j=1;j<20;j++){ for(ll i=1;i<=n;i++){ if(par[i][j-1]==-1) continue; par[i][j]=par[par[i][j-1]][j-1]; } } for(ll i=1;i<=n;i++){ till[i]=1e17+10,tillp[i]=1e17+10; } dfS(1,0); dFs(1,0); while(q--){ ll idx,x; cin>>idx>>x; ll u=egg[idx-1].l,v=egg[idx-1].r; if(!yes(u,x,e) || !yes(v,x,e)){ cout<<"escaped"<<endl; continue; } if(ok[x]){ cout<<0<<endl; continue; } ll ans=1e17; for(ed X:adj[x]){ if(X.s<=0) continue; if(yes(u,X.s,x) && yes(v,X.s,x)) continue; ans=min(ans,X.w+X.val); } if(ans>=1e15) cout<<"oo"<<endl; else cout<<ans<<endl; } 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...