Submission #132608

#TimeUsernameProblemLanguageResultExecution timeMemory
132608EntityITValley (BOI19_valley)C++14
32 / 100
462 ms62072 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pb push_back using ll = long long; const int N = (int)1e5 + 5, LOG = __lg(N) + 1, inf = (int)1e9 + 123; const ll infll = (ll)1e18 + 123; int n, n_shop, n_query, exit_ver, be[N], en[N], par[N][LOG], depth[N], edge_ver[N]; pair<int, int> edge[N]; ll min_down[N][3], min_up[N], f_minus[N][LOG], f_plus[N][LOG], depth_cap[N]; bool have_shop[N]; vector< pair<int, int> > gr[N]; void dfs (int u, int p) { static int i_tour = 0; be[u] = ++i_tour; par[u][0] = p; for (int i = 1; i < LOG; ++i) par[u][i] = par[ par[u][i - 1] ][i - 1]; depth[u] = depth[p] + 1; for (auto _ : gr[u]) { int v = _.fi; edge_ver[v] = _.se; if (v == p) continue ; depth_cap[v] = depth_cap[u] + edge_ver[v]; dfs(v, u); } en[u] = i_tour; } int check_bit (int _a, int _i) { return (_a >> _i) & 1; } int find_lca (int u, int v) { if (depth[u] > depth[v]) swap(u, v); int diff = depth[v] - depth[u]; for (int i = LOG - 1; i >= 0; --i) if (check_bit(diff, i) ) v = par[v][i]; for (int i = LOG - 1; i >= 0; --i) if (par[u][i] != par[v][i]) { u = par[u][i]; v = par[v][i]; } return (u == v) ? u : par[u][0]; } void cal_min_down (int u) { min_down[u][0] = min_down[u][1] = min_down[u][2] = infll; if (have_shop[u]) min_down[u][0] = 0; for (auto _ : gr[u]) { int v = _.fi, w = _.se; if (v == par[u][0]) continue ; cal_min_down(v); ll n_val = min_down[v][0] + w; for (int i = 0; i < 3; ++i) if (min_down[u][i] > n_val) swap(min_down[u][i], n_val); } } void cal_min_up (int u) { if (have_shop[u]) min_up[u] = 0; for (auto _ : gr[u]) { int v = _.fi, w = _.se; if (v == par[u][0]) continue ; min_up[v] = infll; min_up[v] = min(min_up[v], min_up[u] + w); if (min_down[v][0] + w == min_down[u][0]) min_up[v] = min(min_up[v], min_down[u][1] + w); else min_up[v] = min(min_up[v], min_down[u][0] + w); cal_min_up(v); } } void cal_f (int u) { for (int i = 1; i < LOG; ++i) { f_minus[u][i] = min(f_minus[u][i - 1], f_minus[ par[u][i - 1] ][i - 1]); f_plus[u][i] = min(f_plus[u][i - 1], f_plus[ par[u][i - 1] ][i - 1]); } for (auto _ : gr[u]) { int v = _.fi, w = _.se; if (v == par[u][0]) continue ; if (min_down[v][0] + w == min_down[u][0]) f_minus[v][0] = f_plus[v][0] = min_down[u][1]; else f_minus[v][0] = f_plus[v][0] = min_down[u][0]; f_minus[v][0] -= depth_cap[u]; f_plus[v][0] += depth_cap[u]; cal_f(v); } } bool descendant (int u, int p) { return be[p] <= be[u] && en[u] <= en[p]; } ll get_f_minus (int u, int heigh) { ll ret = infll; for (int i = LOG - 1; i >= 0; --i) if (check_bit(heigh, i) ) { ret = min(ret, f_minus[u][i]); u = par[u][i]; } return ret; } ll get_f_plus (int u, int heigh) { ll ret = infll; for (int i = LOG - 1; i >= 0; --i) if (check_bit(heigh, i) ) { ret = min(ret, f_plus[u][i]); u = par[u][i]; } return ret; } int find_ancestor (int u, int heigh) { for (int i = LOG - 1; i >= 0; --i) if (check_bit(heigh, i) ) u = par[u][i]; return u; } int32_t main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("test.INP", "r", stdin); // freopen("test.OUT", "w", stdout); cin >> n >> n_shop >> n_query >> exit_ver; for (int i = 1; i < n; ++i) { int u, v, w; cin >> u >> v >> w; gr[u].pb( { v, w } ); gr[v].pb( { u, w } ); edge[i] = { u, v }; } while (n_shop --) { int ver; cin >> ver; have_shop[ver] = 1; } dfs(1, 1); cal_min_down(1); min_up[1] = infll; cal_min_up(1); for (int i = 0; i < LOG; ++i) f_minus[1][i] = f_plus[1][i] = infll; cal_f(1); for (int i = 1; i < n; ++i) if (depth[ edge[i].fi ] > depth[ edge[i].se ]) swap(edge[i].fi, edge[i].se); while (n_query --) { int edge_id, src; cin >> edge_id >> src; int cut_ver = edge[edge_id].se; if (descendant(src, cut_ver) == descendant(exit_ver, cut_ver) ) cout << "escaped\n"; else { ll ans = infll; int lca = find_lca(src, cut_ver); if (lca == cut_ver) { ans = min(ans, min_down[src][0]); ans = min(ans, depth_cap[src] + get_f_minus(src, depth[src] - depth[cut_ver]) ); } else if (lca == src) { ans = min(ans, min_up[src]); ans = min(ans, get_f_plus(cut_ver, depth[cut_ver] - depth[src]) - depth_cap[src]); } else { ans = min(ans, min_down[src][0]); ans = min(ans, depth_cap[src] + get_f_minus(src, depth[src] - depth[lca] - 1) ); ans = min(ans, depth_cap[src] - 2 * depth_cap[lca] + get_f_plus(cut_ver, depth[cut_ver] - depth[lca] - 1) ); ans = min(ans, depth_cap[src] - depth_cap[lca] + min_up[lca]); int par_src = find_ancestor(src, depth[src] - depth[lca] - 1), par_cut = find_ancestor(cut_ver, depth[cut_ver] - depth[lca] - 1); vector<ll> vec; vec.pb(min_down[par_src][0] + edge_ver[par_src]); vec.pb(min_down[par_cut][0] + edge_ver[par_cut]); sort(vec.begin(), vec.end() ); for (int i = 0; i < 3; ++i) { if (i > 1 || vec[i] != min_down[lca][i]) { ans = min(ans, depth_cap[src] - depth_cap[lca] + min_down[lca][i]); break ; } } } if (ans > 1LL * inf * N) cout << "oo\n"; else cout << ans << '\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...