제출 #695784

#제출 시각아이디문제언어결과실행 시간메모리
695784AlishValley (BOI19_valley)C++14
0 / 100
279 ms90596 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define F first #define S second #define pb push_back #define endl '\n' #define Mp make_pair #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " = " << x << endl #define set_dec(x) cout << fixed << setprecision(x); #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout); ll mod = 1e9+7 ; ll power(ll a, ll b) { return (!b ? 1 : (b & 1 ? a * power(a * a % mod, b / 2) % mod : power(a * a % mod, b / 2) % mod)); } const ll N = 2e5+23 , L = 32, INF = 1e18 ; ll D[N] , dist[N] , par[N][L] , mn[N][L], num[N]; int h[N] , st[N] , ft[N] , t=0; vector<pii> E; vector<pii> g[N] ; int n , s, q, e; int vis[N]; void dfs(int v, int p=0, int d=0, int H=0){ par[v][0]=p; dist[v]=d; h[v]=H; st[v]=t; t++; for(auto pp: g[v]){ int u=pp.F, w=pp.S; if(u==p) continue; dfs(u, v, d+w, H+1); D[v]=min(D[v], D[u]+w); } ft[v]=t; t++; } int main(){ fast_io cin>>n>>s>>q>>e; for(int i=0; i<n-1; i++){ int u, v, w; cin>>v>>u>>w; g[v].pb({u, w}); g[u].pb({v, w}); E.pb({u, v}); } memset(D, 63 , sizeof(D)); for (int i=1; i<=n; i++)par[i][0]=i; for(int i=0; i<s; i++){ int C; cin>>C; D[C]=0; } memset(mn , 63 , sizeof(mn)); dfs(e, e) ; for(int i=0; i<n-1; i++){ if(h[E[i].F] < h[E[i].S]) swap(E[i].F , E[i].S); } for(int j=1; j<L; j++){ for(int i=1; i<=n; i++){ par[i][j]=par[par[i][j-1]][j-1]; } } for(int i=1; i<=n; i++){ num[i]=D[i]-dist[i]; } for(int i=0; i<=n; i++){ mn[i][0]=num[par[i][0]]; } for(int j=1; j<L; j++){ for(int i=0; i<=n; i++){ mn[i][j]=min(mn[i][j-1], mn[par[i][j-1]][j-1]); } } while(q--){ int ed, a; cin>>ed>>a; ed--; if(st[E[ed].F] <=st[a] && ft[E[ed].F]>=st[a]){ int b=E[ed].F; ll ans=num[a]; ll d= h[a]-h[b]; int c=a ; for(int i=L-1; i>=0; i--){ if(d& ( 1<<i)){ ans= min(ans, mn[a][i]); a=par[a][i]; } } ans=min(ans, num[b]); //cout<<ans<<" "<<dist[c]<<endl; ans+=dist[c]; if(ans<=1e18) cout<<ans<<endl; else cout<<"oo"<<endl; } else cout<<"escaped"<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...