Submission #491847

#TimeUsernameProblemLanguageResultExecution timeMemory
491847codr0Valley (BOI19_valley)C++14
23 / 100
244 ms56112 KiB
// Code by Parsa Eslami #include <bits/stdc++.h> #define FOR(i,a,b) for(long long i=a;i<=b;i++) #define FORR(i,a,b) for(long long i=a;i>=b;i--) #define S second #define F first #define pb push_back #define SZ(x) ((long long)x.size()) using namespace std; const long long N=1e5+4; const long long Lg=22; const long long INF=1e17+100; long long par[N][Lg]; long long K[N],hw[N],h[N],st[N],en[N],Tme; long long dp[N][Lg]; vector<long long> adj[N]; vector<long long> W[N]; long long n,s,q,e; bool bit(long long i,long long j){ return ((j>>i)&1); } void pre(){ FOR(i,0,N-1) K[i]=INF; FOR(i,0,N-1) FOR(j,0,Lg-1) dp[i][j]=INF; } void dfs(long long v,long long p){ par[v][0]=p; st[v]=Tme++; FOR(i,0,SZ(adj[v])-1){ long long u=adj[v][i]; long long w=W[v][i]; if(u!=p){ hw[u]=hw[v]+w; h[u]=h[v]+1; dfs(u,v); K[v]=min(K[v],K[u]+w); } } en[v]=Tme++; } void FILL(){ FOR(i,1,n) FOR(j,1,Lg-1) par[i][j]=par[par[i][j-1]][j-1]; FOR(i,1,n) dp[i][0]=K[i]; FOR(j,1,Lg-1) FOR(i,1,n){ dp[i][j]=min(dp[i][j-1],(hw[i]-hw[par[i][j-1]]+dp[par[i][j-1]][j-1])); } } long long ans(long long v,long long X){ X++; long long rt=INF; long long dist=0; FOR(i,0,21){ if(bit(i,X)){ rt=min(rt,dist+dp[v][i]); dist+=(hw[v]-hw[par[v][i]]); v=par[v][i]; } } return rt; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); pre(); cin>>n>>s>>q>>e; vector<pair<long long,long long>> M; FOR(i,1,n-1){ long long u,v,w; cin>>u>>v>>w; M.pb({u,v}); adj[u].pb(v); W[u].pb(w); adj[v].pb(u); W[v].pb(w); } FOR(i,1,s){ long long x0; cin>>x0; K[x0]=0; } dfs(e,e); FILL(); FOR(i,1,q){ long long E,V; cin>>E>>V; long long u=M[E-1].F; long long v=M[E-1].S; if(st[v]<st[u]) swap(u,v); if(st[V]>=st[v]&&en[V]<=en[v]){ long long ot=ans(V,h[V]-h[v]); if(ot>=INF) cout<<"oo\n"; else cout<<ot<<'\n'; }else{ cout<<"escaped\n"; } } 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...