제출 #493638

#제출 시각아이디문제언어결과실행 시간메모리
493638FystyValley (BOI19_valley)C++14
23 / 100
216 ms50172 KiB
#include <bits/stdc++.h> #include <random> #include <chrono> using namespace std; //#pragma GCC optimize("Ofast") //#pragma GCC optimize ("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<double,double> pdd; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template<typename T> void _do(T x){cerr<<x<<"\n";} template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);} #define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__); const int MOD1=1e9+7; const int MOD2=998244353; const ll INF=3e18; const ld PI=3.14159265358979323846; ll gcd(ll a,ll b){if(b==0) return a; return gcd(b,a%b);} ll fpow(ll a,ll b,ll m) { if(!b) return 1; ll ans=fpow(a*a%m,b/2,m); return (b%2?ans*a%m:ans); } ll inv(ll a,ll m) {return fpow(a,m-2,m);} #define MottoHayaku ios::sync_with_stdio(false);cin.tie(0); //#define int ll #define rep(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define repk(i,m,n) for(int i=m;i<n;i++) #define F first #define S second #define pb push_back #define lb lower_bound #define ub upper_bound #define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end()))) #define unisort(c) sort(c.begin(),c.end()),uni(c) const int N=1e5+1; ll dep[N],dist[N],tmp[N],in[N],out[N],an[18][N],mn[18][N],t=0; bool is[N]; vector<pll> ed[N]; void dfs(ll n,ll p) { in[n]=t++; dep[n]=(p==0?0:dep[p]+1); if(is[n]) tmp[n]=dist[n]; for(pll u:ed[n]) { if(u.F==p) continue; dist[u.F]=dist[n]+u.S; dfs(u.F,n); an[0][u.F]=n; mn[0][u.F]=min(tmp[n]-dist[n]*2,tmp[u.F]-dist[u.F]*2); tmp[n]=min(tmp[n],tmp[u.F]); } out[n]=t++; } bool isan(ll u,ll v){return (in[u]<=in[v]&&out[v]<=out[u]);} signed main() { MottoHayaku ll n,s,q,a; cin>>n>>s>>q>>a; vector<pll> e; rep1(i,n) tmp[i]=INF; rep(i,n-1) { ll u,v,w; cin>>u>>v>>w; e.pb({u,v}); ed[u].pb({v,w}); ed[v].pb({u,w}); } rep(i,s) { ll c; cin>>c; is[c]=1; } an[0][a]=a; dfs(a,0); rep1(i,17) { rep1(j,n) { an[i][j]=an[i-1][an[i-1][j]]; mn[i][j]=min(mn[i-1][j],mn[i-1][an[i-1][j]]); } } while(q--) { ll id,x; cin>>id>>x; id--; pll p=e[id]; if(dep[p.F]<dep[p.S]) swap(p.F,p.S); if(!isan(p.F,x)) cout<<"escaped\n"; else { if(tmp[p.F]==INF) { cout<<"oo\n"; continue; } if(p.F==x) { cout<<"0\n"; continue; } ll ans=tmp[x]-dist[x]; ll k=dist[x],cur=INF; for(int i=17;i>=0;i--) { if(isan(an[i][x],p.F)) continue; cur=min(cur,mn[i][x]); x=an[i][x]; } cur=min(cur,mn[0][x]); cout<<min(ans,k+cur)<<"\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...