제출 #708326

#제출 시각아이디문제언어결과실행 시간메모리
708326DeepessonValley (BOI19_valley)C++17
0 / 100
192 ms47072 KiB
#include <bits/stdc++.h> #define MAX 105000 using ll = long long; typedef std::pair<ll,ll> pii; std::vector<pii> con[MAX]; ll lift[MAX][20],prof[MAX],dist[MAX],plift[MAX][20]; bool shops[MAX]; ll inf = 1LL<<60LL; ll dfs(ll pos,ll prev,ll depth,ll d){ prof[pos]=depth; dist[pos]=d; lift[pos][0]=prev; ll min = inf; if(shops[pos])min=dist[pos]; for(auto&x:con[pos]){ if(x.first==prev)continue; min=std::min(min,dfs(x.first,pos,depth+1,d+x.second)); } plift[pos][0]=min-(2*dist[pos]); for(int i=1;i!=20;++i){ lift[pos][i]=lift[lift[pos][i-1]][i-1]; plift[pos][i]=std::min(plift[pos][i-1],plift[lift[pos][i-1]][i-1]); } return min; } pii climb(int pos,int b){ ll min=inf; for(int i=19;i!=-1;--i){ if(b&(1<<i)){ pos=lift[pos][i]; min=std::min(min,plift[pos][i]); } } return {pos,min}; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int N,S,Q,E; std::cin>>N>>S>>Q>>E;--E; std::vector<pii> conlis; for(int i=1;i!=N;++i){ int a,b,c; std::cin>>a>>b>>c; --a;--b; con[a].push_back({b,c}); con[b].push_back({a,c}); conlis.push_back({a,b}); } for(int i=0;i!=S;++i){ int x; std::cin>>x; --x; shops[x]=1; } dfs(E,E,0,0); for(int i=0;i!=Q;++i){ int a,b; std::cin>>a>>b; --a;--b; pii bloq = conlis[a]; int peq = bloq.first; if(prof[bloq.second]>=prof[bloq.first])peq=bloq.second; if(prof[peq]>prof[b]){ std::cout<<"escaped\n"; continue; } int dif = prof[b]-prof[peq]; auto res = climb(b,dif); if(res.first!=peq){ std::cout<<"escaped\n"; continue; } ll ans = res.second+dist[b]; if(ans<(1LL<<50LL)){ std::cout<<ans<<"\n"; }else std::cout<<"oo\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...