Submission #1259465

#TimeUsernameProblemLanguageResultExecution timeMemory
1259465tntValley (BOI19_valley)C++20
0 / 100
103 ms46864 KiB
#include <bits/stdc++.h> using namespace std; //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3") #define pb push_back #define ll long long #define int long long //#define sz(v) int(v.size()) #define all(v) v.begin(),v.end() #define f first #define s second int mod = 998244353; const long long inf = 1e18; const int N = 1e5 + 10; int dp[N],s[N],dist[N],pr[N]; vector <pair <int,int>> g[N]; int up[N][20],up1[N][20]; int tin[N],tout[N],depth[N]; int timer = 0; void dfs(int u,int p){ if(s[u] == 1) dp[u] = 0; else dp[u] = inf; pr[u] = p,tin[u] = ++timer; for(auto [to,w] : g[u]){ if(to == p) continue; dist[to] = dist[u] + w,depth[to] = depth[u] + 1; dfs(to,u); dp[u] = min(dp[to] + w,dp[u]); } tout[u] = timer; } void dfs1(int u,int p){ up[u][0] = p,up1[u][0] = min(dp[p] - dist[p],dp[u] - dist[u]); for(int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1]; for(int i = 1; i < 20; i++) up1[u][i] = min(up1[up[u][i - 1]][i - 1],up1[u][i - 1]); for(auto [to,w] : g[u]){ if(to == p) continue; dfs1(to,u); } } void solve(){ int n,m,q,x; cin >> n >> m >> q >> x; vector <pair <int,int>> qr; for(int i = 2; i <= n; i++){ int u,v,w; cin >> u >> v >> w; g[u].pb({v,w}),g[v].pb({u,w}); qr.pb({u,v}); } for(int i = 1; i <= m; i++){ int u; cin >> u; s[u] = 1; } dfs(x,x),dfs1(x,x); while(q--){ int i,d; cin >>i >> d; int u = qr[i - 1].f,v = qr[i - 1].s; if(pr[u] == v) swap(u,v); if(tin[v] <= tin[d] && tin[d] <= tout[v]){ int ans = inf,dist1 = depth[d] - depth[v],f = dist[d]; for(int i = 0; i < 20; i++){ if((dist1 >> i & 1) == 1){ ans = min(ans,up1[d][i]); d = up[d][i]; } } if(ans + f >= 1e15) cout << "oo\n"; else cout << ans + f << '\n'; } else{ cout << "escaped\n"; } } } signed main(){ //freopen("floor4.in", "r", stdin); //freopen("floor4.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); int t = 1; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...