제출 #819619

#제출 시각아이디문제언어결과실행 시간메모리
819619aryan12Valley (BOI19_valley)C++17
23 / 100
120 ms57252 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]; int bestup[LG][N], tot_dist[LG][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); tot_dist[0][to] = wt; dist_in_subtree[node] = min(dist_in_subtree[node], dist_in_subtree[to] + wt); bestup[0][to] = min(dist_in_subtree[to], dist_in_subtree[node] + 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; } dist_in_subtree[0] = INF; 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]]; tot_dist[i][j] = tot_dist[i - 1][lift[i - 1][j]] + tot_dist[i - 1][j]; bestup[i][j] = min(bestup[i - 1][j], bestup[i - 1][lift[i - 1][j]] + tot_dist[i - 1][j]); } } for(int i = 1; i <= q; i++) { int idx, node; cin >> idx >> node; idx -= 1; if(tin[edges[idx][0]] <= tin[edges[idx][1]]) { swap(edges[idx][0], edges[idx][1]); } if(tin[edges[idx][0]] <= tin[node] && tout[node] <= tout[edges[idx][0]]) { if(dist_in_subtree[edges[idx][0]] >= INF) { cout << "oo\n"; } else { if(shop[node]) { cout << "0\n"; continue; } int cur_dist = 0, tot_ans = INF; for(int j = LG - 1; j >= 0; j--) { // cout << "j = " << j << ", node = " << node << "\n"; // cout << lift[j][node] << "\n"; if(lift[j][node] == 0) { continue; } if(tin[lift[j][node]] <= tin[edges[idx][1]] && tout[edges[idx][1]] <= tout[lift[j][node]]) { continue; } else { tot_ans = min(tot_ans, cur_dist + bestup[j][node]); cur_dist += tot_dist[j][node]; node = lift[j][node]; } } // cout << "node = " << node << "\n"; // assert(tot_ans < INF); cout << tot_ans << "\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...