Submission #720067

#TimeUsernameProblemLanguageResultExecution timeMemory
720067konstantysValley (BOI19_valley)C++14
23 / 100
340 ms57560 KiB
#include<iostream> #include<cstdlib> #include<cstdio> #include<vector> #define DUZO 1000000000000000LL; using namespace std; int n,s,q,e,a,b,c,parnt[20][100005],dpth[100005],ord[2][100005],l; long long il[20][100005],dl[20][100005],x,y; bool czy[100005]; vector<pair<int,long long>> v[100005]; int krw[2][100005]; long long DFS(int x,int f){ l++; ord[0][x]=l; parnt[0][x]=f; long long wyn=DUZO; if(czy[x]) wyn=0; //cerr<<x<<" "<<dpth[x]<<"p\n"; for(auto u:v[x]){ if(u.first==f) continue; dpth[u.first]=dpth[x]+1; //cerr<<u.first<<" "<<x<<"!!!\n"; dl[0][u.first]=u.second; wyn=min(wyn,u.second+DFS(u.first,x)); } //cerr<<x<<" "<<dpth[x]<<"\n"; il[0][x]=wyn; ord[1][x]=l; return wyn; } int main(){ ios_base::sync_with_stdio(0); cin>>n>>s>>q>>e; for(int i=1;i<n;i++){ //prnt[0][i]=i; cin>>a>>b>>c; v[a].push_back({b,c}); v[b].push_back({a,c}); krw[0][i]=a; krw[1][i]=b; } for(int i=0;i<s;i++){ cin>>a; czy[a]=1; } DFS(e,-1); parnt[0][e]=e; for(int i=1;i<20;i++) for(int u=1;u<=n;u++){ parnt[i][u]=parnt[i-1][parnt[i-1][u]]; dl[i][u]=dl[i-1][u]+dl[i-1][parnt[i-1][u]]; il[i][u]=min(il[i-1][u],il[i-1][parnt[i-1][u]]+dl[i-1][u]); } for(int i=0;i<q;i++){ cin>>a>>c; b=krw[1][a]; a=krw[0][a]; //cerr<<dpth[a]<<" "<<dpth[b]<<"!!\n"; if(dpth[a]<dpth[b]) swap(a,b); //a nizej b wyzej //cerr<<a<<" "<<ord[0][a]<<" "<<ord[1][a]<<" "<<c<<" "<<ord[0][c]<<"\n"; if(ord[0][a]<=ord[0][c] && ord[0][c]<=ord[1][a]){ x=DUZO; y=0; a=c; //cerr<<b<<"!!!\n"; for(int u=19;u>=0;u--){ //cerr<<u<<" "<<a<<" "<<parnt[u][a]<<"\n"; if(dpth[parnt[u][a]]>=dpth[b]){ x=min(il[u][a]+y,x); // cerr<<il[u][a]<<"???\n"; y+=dl[u][a]; a=parnt[u][a]; } if(a==b) break; } if(x==1000000000000000LL) cout<<"oo\n"; else cout<<x<<"\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...