제출 #1190334

#제출 시각아이디문제언어결과실행 시간메모리
1190334qrnValley (BOI19_valley)C++20
23 / 100
123 ms74672 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> using namespace std; // using namespace __gnu_pbds; #define pb push_back #define ins insert #define fi first #define se second #define endl "\n" #define ALL(x) x.begin(), x.end() #define intt long long const intt mod = 1e9 + 7; const intt base = 9973; const intt inf = 1e18; const intt mxN = 5e5 + 5; const intt L = 21; vector<vector<pair<intt,intt>>> graph; vector<vector<intt>> up, mn; vector<intt> in(mxN), out(mxN), sub(mxN), depth(mxN), H(mxN), is(mxN), cost(mxN); intt N, S, Q, E, timer; void dfs(intt node, intt parent){ in[node] = timer++; up[0][node] = parent; for(intt i = 1; i < L; i++) { up[i][node] = up[i-1][up[i-1][node]]; } for(auto u : graph[node]) { if(u.fi != parent) { depth[u.fi] = depth[node] + 1; cost[u.fi] = cost[node] + u.se; dfs(u.fi, node); } } out[node] = timer++; if(is[node]) { H[node] = 0; } else { for(auto u : graph[node]) { if(u.fi != parent) { H[node] = min(H[node], H[u.fi] + u.se); } } } } bool isata(intt a, intt b) { return in[a] <= in[b] && out[a] >= out[b]; } void solve() { cin >> N >> S >> Q >> E; graph.assign(N + 1, vector<pair<intt,intt>> {}); up.assign(L, vector<intt> (N + 1, 0ll)); mn.assign(L, vector<intt> (N + 1, inf)); H.assign(N + 1, inf); vector<pair<intt,intt>> edge(N+1); for(intt i = 1; i <= N - 1; i++) { intt a, b, w; cin >> a >> b >> w; graph[a].pb({b, w}); graph[b].pb({a, w}); edge[i] = {a, b}; } for(intt i = 1; i <= S; i++) { intt node; cin >> node; is[node] = 1; } dfs(E, E); for(intt i = 1; i <= N; i++) { // cout << i << endl; // cout << H[i] << " : " << up[0][i] << endl; // cout << mn[0].size() << endl; mn[0][i] = min(H[i], H[up[0][i]]); } for(intt j = 1; j < L; j++) { for(intt i = 1; i <= N; i++) { mn[j][i] = min(mn[j][i], mn[j-1][up[j-1][i]]); } } while(Q--) { intt node, idx; cin >> idx >> node; intt a = edge[idx].fi, b = edge[idx].se; if(depth[a] > depth[b]) { swap(a, b); } if(!isata(b, node)) { cout << "escaped" << endl; continue; } if(is[node]) { cout << 0 << endl; continue; } intt yol = depth[node] - depth[b], qaldir = node, ans = inf, nod = 0; for(intt i = L - 1; i >= 0; i--) { if((1 << i) & yol) { if(ans > mn[i][qaldir]) { ans = mn[i][qaldir]; nod = i; } qaldir = up[i][qaldir]; } } qaldir = node; intt add = cost[node] - cost[up[nod][node]]; // cout << nod << " " << add << " " << yol << endl; if(ans == inf) { cout << "oo" << endl; } else { cout << ans + add << endl; } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); intt tst = 1; // cin >> tst; while(tst--) { 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...