Submission #1078543

#TimeUsernameProblemLanguageResultExecution timeMemory
1078543MighilonValley (BOI19_valley)C++17
23 / 100
115 ms39928 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "../Library/debug.h" #else #define dbg(x...) #endif typedef long long ll; typedef long double ld; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define F0R(i, a) for (int i = 0; i < (a); ++i) #define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i) #define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i) #define trav(a, x) for (auto& a : x) #define f first #define s second #define pb push_back #define sz(x) (int)(x).size() #define all(x) x.begin(), x.end() const char nl = '\n'; const int INF = 1e9; const int MOD = 1e9 + 7; void solve(){ int n, s, q, e; cin >> n >> s >> q >> e; --e; vector<vi> adj(n); vector<array<int, 3>> edge(n - 1); vector<bool> shop(n); F0R(i, n - 1){ int a, b, w; cin >> a >> b >> w; a--, b--; edge[i][0] = a ^ b; edge[i][1] = w; adj[a].pb(i); adj[b].pb(i); } F0R(i, s){ int a; cin >> a; --a; shop[a] = true; } vi depth(n), par(n); par[e] = -1; auto dfs = [&](auto self, int u, int p) -> void{ trav(id, adj[u]){ int v = edge[id][0] ^ u; if(v == p) continue; edge[id][2] = v; par[v] = id; depth[v] = depth[u] + 1; self(self, v, u); } }; dfs(dfs, e, -1); vl dist(n); auto dfs_dist = [&](auto self, int u, int p, ll d) -> void{ dbg(u, p, d) dist[u] = d; trav(id, adj[u]){ int v = edge[id][0] ^ u; if(v == p) continue; self(self, v, u, d + edge[id][1]); } }; dfs_dist(dfs_dist, e, -1, 0); vl mn(n); auto dfs_mn = [&](auto self, int u, int p) -> void{ if(shop[u]) mn[u] = dist[u]; else mn[u] = 1e18; trav(id, adj[u]){ int v = edge[id][0] ^ u; if(v == p) continue; self(self, v, u); mn[u] = min(mn[u], mn[v]); } }; dfs_mn(dfs_mn, e, -1); F0R(i, n) if(mn[i] != 1e18) mn[i] -= 2 * dist[i]; // vl cost_subtree(n, 1e18); // { // priority_queue<array<ll, 3>> pq; // F0R(i, n){ // if(shop[i]){ // pq.push({depth[i], 0, i}); // cost_subtree[i] = 0; // } // } // while(!pq.empty()){ // auto [depth_, cost, u] = pq.top(); // pq.pop(); // cost *= -1; // int id = par[u]; // if(id == -1) // continue; // int p = edge[id][0] ^ u; // if(cost_subtree[p] > cost_subtree[u] + edge[id][1]){ // cost_subtree[p] = cost_subtree[u] + edge[id][1]; // pq.push({depth[p], -cost_subtree[p], p}); // } // } // } int mxLog = 20; vector<vi> nxt(mxLog, vi(n)); F0R(i, n) if(par[i] == -1) nxt[0][i] = i; else nxt[0][i] = edge[par[i]][0] ^ i; FOR(k, 1, mxLog) F0R(i, n) nxt[k][i] = nxt[k - 1][nxt[k - 1][i]]; // if(nxt[k - 1][i] == -1) nxt[k][i] = -1; // else nxt[k][i] = nxt[k - 1][nxt[k - 1][i]]; auto jump_k = [&](int i, int k){ F0R(j, mxLog) if((k >> j) & 1){ i = nxt[j][i]; // if(i == -1) return -1; } return i; }; vector<vl> nxt_mn(mxLog, vl(n, 1e18)); dbg(par) F0R(i, n) nxt_mn[0][i] = mn[edge[(par[i] == -1 ? i : par[i])][0] ^ i]; // F0R(i, n) nxt_mn[0][i] = mn[i]; FOR(k, 1, mxLog) F0R(i, n){ nxt_mn[k][i] = min(nxt_mn[k - 1][i], nxt_mn[k - 1][nxt[k - 1][i]]); } auto jump_mn = [&](int i, int k){ ll x = mn[i]; F0R(j, mxLog) if((k >> j) & 1){ x = nxt_mn[j][i]; i = nxt[j][i]; } return x; }; // vector<vl> nxt_mindist(mxLog, vl(n)); // F0R(i, n) // if(par[i] == -1) nxt[0][i] = 1e18; // else nxt[0][i] = edge[par[i]][1]; // FOR(k, 1, mxLog) F0R(i, n) // if(nxt[k][i] == -1) nxt_mindist[k][i] = 1e18; // else nxt_mindist[k][i] = min(nxt_mindist[k - 1][nxt[k - 1][i]], nxt_mindist[k - 1][i]); // auto jump_k_cost = [&](int i, int k) -> ll{ // ll total_cost = 0; // F0R(j, mxLog) // if((k >> j) & 1){ // total_cost += nxt_dist[j][i]; // i = nxt[j][i]; // if(i == -1) // return 1e18; // } // return total_cost; // }; dbg(dist) dbg(mn) dbg(shop) dbg(nxt) dbg(nxt_mn) while(q--){ int id, x; cin >> id >> x; --id, --x; int y = edge[id][2]; dbg(x, y) int diff = depth[x] - depth[y]; dbg(diff) if(diff < 0 || (diff == 0 && x != y)){ cout << "escaped" << nl; continue; } // if(x == y){ // if(cost_subtree[x] == 1e18) // cout << "oo" << nl; // else cout << cost_subtree[x] << nl; // continue; // } int new_x = jump_k(x, diff); dbg(new_x, y) if(new_x != y){ cout << "escaped" << nl; continue; } if(shop[x]){ cout << 0 << nl; continue; } ll ans = jump_mn(x, diff); dbg(ans, x, diff) dbg(ans + dist[x]) if(ans == 1e18){ cout << "oo" << nl; } else{ cout << ans + dist[x] << nl; } // if(cost_subtree[new_x] == 1e18){ // cout << "oo" << nl; // continue; // } // ll ans = cost_subtree[new_x] + jump_k_cost(x, diff); // int lo = 0, hi = diff; // while(lo <= hi){ // int m = lo + (hi - lo) / 2; // ll aux = cost_subtree[jump_k(x, m)] + jump_k_cost(x, m); // if(aux <=) // } } } int32_t main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int TC = 1; // cin >> TC; while(TC--){ solve(); } 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...