Submission #1094938

#TimeUsernameProblemLanguageResultExecution timeMemory
1094938vjudge1Valley (BOI19_valley)C++17
100 / 100
183 ms89684 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using ll = long long; const ll MAXN = 1e6 + 5; const ll INF = 1e16; const ll LOG = 30; #define pll pair <ll, ll> #define vll vector <ll> #define fi first #define se second #define endl '\n' #define debug(x) cout << #x << " " << (x) << endl; #define lc (pos<<1) #define rc ((pos<<1)+1) #define mid ((l+r)>>1) ll n, s, q, e; vector <vector <pll> > adj (MAXN); array <ll, 3> edg [MAXN]; bool b [MAXN]; ll dep [MAXN], dis [MAXN], val [MAXN]; ll anc [MAXN][LOG], spa [MAXN][LOG]; vll lis; void dfs(ll x, ll px){ anc[x][0] = px; val[x] = INF; if(b[x]) val[x] = dis[x]; for(auto nx : adj[x]){ ll y = nx.fi, w = nx.se; if(y == px) continue; dep[y] = dep[x] + 1; dis[y] = dis[x] + w; dfs(y, x); val[x] = min(val[x], val[y]); } spa[x][0] = val[x] - (2*dis[x]); if(val[x] == INF) spa[x][0] = INF; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> s >> q >> e; for(ll i = 1; i <= n-1; i++){ ll u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); edg[i] = {u, v, w}; } for(ll i = 1; i <= s; i++){ ll x; cin >> x; b[x] = 1; } dfs(e, 0); for(ll j = 1; j < LOG; j++){ for(ll i = 1; i <= n; i++){ anc[i][j] = anc[anc[i][j-1]][j-1]; spa[i][j] = min(spa[i][j-1], spa[anc[i][j-1]][j-1]); } } for(ll i = 1; i <= q; i++){ ll ed, x; cin >> ed >> x; ll u = edg[ed][0], v = edg[ed][1]; if(dep[u] > dep[v]) swap(u, v); if(dep[x] < dep[v]){ cout << "escaped" << endl; continue; } ll fw = x, mn = spa[fw][0]; for(ll j = LOG-1; j >= 0; j--){ if(dep[anc[fw][j]] >= dep[v]){ mn = min(mn, spa[fw][j]); fw = anc[fw][j]; mn = min(mn, spa[fw][0]); } } if(fw != v){ cout << "escaped" << endl; continue; } if(mn == INF) cout << "oo" << endl; else cout << dis[x] + mn << 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...