Submission #1263920

#TimeUsernameProblemLanguageResultExecution timeMemory
1263920Bui_Quoc_CuongValley (BOI19_valley)C++20
100 / 100
199 ms45348 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAXN = 2e5 + 5; int N, S, Q, E; vector <pair <int, int>> adj[MAXN]; bool isspec[MAXN]; int h[MAXN]; long long sum[MAXN]; int par[MAXN], tin[MAXN], tout[MAXN], timeDFS; long long f[MAXN]; int P[MAXN][20]; void dfs(int u, int p = - 1){ f[u] = 2e18; if(isspec[u]) f[u] = sum[u]; tin[u] = ++ timeDFS; for(pair <int, int> &it : adj[u]) if(it.first != p){ int v = it.first, w = it.second; par[v] = u; h[v] = h[u] + 1; P[v][0] = u; for(int j = 1; (1 << j) <= N; j++){ P[v][j] = P[P[v][j - 1]][j - 1]; } sum[v] = sum[u] + w; dfs(v, u); f[u] = min(f[u], f[v]); } tout[u] = ++ timeDFS; } /// h[v] - 2 * sum LCA[u, v] int sz[MAXN], heavy[MAXN], arr[MAXN]; void dfs_sz(int u){ sz[u] = 1; for(auto it : adj[u]) if(it.first != par[u]){ int v = it.first; dfs_sz(v); sz[u]+= sz[v]; if(sz[v] > sz[heavy[u]]) heavy[u] = v; } } int head[MAXN], cur[MAXN], pos[MAXN], timedfs = 0, crt = 0; void dfs_hld(int u){ if(head[crt] == 0) head[crt] = u; pos[u] = ++ timedfs; cur[u] = crt; arr[pos[u]] = u; if(heavy[u]) dfs_hld(heavy[u]); for(auto it : adj[u]) if(it.first != par[u] && it.first != heavy[u]){ crt++; dfs_hld(it.first); } } long long st[4 * MAXN]; void build(int id, int l, int r){ if(l == r){ int u = arr[l]; st[id] = f[u] - 2 * sum[u]; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); st[id] = min(st[id << 1], st[id << 1 | 1]); } long long get(int id, int l, int r, int u, int v){ if(l > v || r < u) return 2e18; if(l >= u && r <= v) return st[id]; int mid = (l + r) >> 1; return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v)); } long long get(int u, int p){ long long res = 2e18; long long cur_sum = sum[u]; while(cur[u] != cur[p]){ res = min(res, get(1, 1, N, pos[head[cur[u]]], pos[u])); u = par[head[cur[u]]]; } res = min(res, get(1, 1, N, pos[p], pos[u])); if(res >= 1e18) return 1e18; return cur_sum + res; } bool isParent(int u, int v){ return tin[u] <= tin[v] && tout[u] >= tout[v]; } int LCA(int u, int v){ if(h[u] < h[v]) swap(u, v); int z = __lg(h[u]); for(int s = z; s >= 0; s--) if(h[u] - h[v] >= (1 << s)) u = P[u][s]; if(u == v) return u; for(int s = z; s >= 0; s--) if(P[u][s] != P[v][s]) u = P[u][s], v = P[v][s]; return P[u][0]; } int dist(int u, int v){ return h[u] + h[v] - 2 * h[LCA(u, v)]; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N >> S >> Q >> E; vector <array <int, 2>> edges(N + 5, {0, 0}); for(int i = 1; i <= N - 1; i++){ int u, v, w; cin >> u >> v >> w; adj[u].push_back(make_pair(v, w)); adj[v].push_back(make_pair(u, w)); edges[i] = {u, v}; } for(int i = 1; i <= S; i++){ int u; cin >> u; isspec[u] = true; } dfs(E); dfs_sz(E); dfs_hld(E); for(int i = 1; i <= 4 * N; i++){ st[i] = 2e18; } build(1, 1, N); while(Q--){ int id_road, id_node; cin >> id_road >> id_node; int u = edges[id_road][0], v = edges[id_road][1]; if(h[u] > h[v]) swap(u, v); if(dist(E, u) + dist(u, v) + dist(v, id_node) == dist(E, id_node)){ long long res = get(id_node, v); if(f[id_node] < 1e18) res = min(res, f[id_node] - sum[id_node]); if(res >= 1e18) cout << "oo\n"; else cout << res << "\n"; } else{ cout << "escaped" << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...