Submission #819573

#TimeUsernameProblemLanguageResultExecution timeMemory
819573aryan12Valley (BOI19_valley)C++17
0 / 100
120 ms30408 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 5, LG = 17, INF = 1e18; vector<pair<int, int> > g[N]; bool shop[N]; int lift[LG][N], tin[N], tout[N], tim = 0; int dist_in_subtree[N]; void dfs(int node, int par) { if(shop[node]) { dist_in_subtree[node] = 0; } else { dist_in_subtree[node] = INF; } tin[node] = ++tim; lift[0][node] = par; for(auto [to, wt]: g[node]) { if(to == par) continue; dfs(to, node); dist_in_subtree[node] = min(dist_in_subtree[node], dist_in_subtree[to] + wt); } tout[node] = tim; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, s, q, e; cin >> n >> s >> q >> e; vector<array<int, 3> > edges; for(int i = 1; i < n; i++) { int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w}); edges.push_back({u, v, w}); } for(int i = 1; i <= s; i++) { int x; cin >> x; shop[x] = true; } dfs(e, 0); for(int i = 1; i < LG; i++) { for(int j = 1; j <= n; j++) { lift[i][j] = lift[i - 1][lift[i - 1][j]]; } } for(int i = 1; i <= q; i++) { int idx, node; cin >> idx >> node; idx -= 1; if(tin[edges[i][0]] <= tin[edges[i][1]]) { swap(edges[i][0], edges[i][1]); } if(tin[edges[idx][0]] <= tin[node] && tout[node] <= tout[edges[idx][0]]) { if(dist_in_subtree[edges[i][0]] >= INF) { cout << "oo\n"; } else { cout << "0\n"; } } else { cout << "escaped\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...