Submission #1189476

#TimeUsernameProblemLanguageResultExecution timeMemory
1189476onbertDesignated Cities (JOI19_designated_cities)C++20
100 / 100
1721 ms63428 KiB
#include <bits/stdc++.h> using namespace std; #define int long long struct edge { int v, c, d; bool operator == (const edge &b) const { return (v == b.v && c == b.c && d == b.d); } }; const int maxn = 2e5 + 5, maxN = 8e5 + 5; int n; vector<edge> adj[maxn]; int ans[maxn]; int curans1 = 0, add1 = 0; void dfs1(int u, int f) { ans[1] = max(curans1, ans[1]); for (auto [v, c, d]:adj[u]) if (v != f) { add1 += d; curans1 -= d, curans1 += c; dfs1(v, u); curans1 += d, curans1 -= c; } } int N, cent; int sz[maxn]; vector<int> nodes; void init(int u, int f) { N++; nodes.push_back(u); for (auto [v, c, d]:adj[u]) if (v != f) init(v, u); } void find_cent(int u, int f) { sz[u] = 1; bool can = true; for (auto [v, c, d]:adj[u]) if (v != f) { find_cent(v, u); sz[u] += sz[v]; if (sz[v] > N/2) can = false; } if (N - sz[u] > N/2) can = false; if (can) cent = u; } int cost[maxn], up[maxn], fa[maxn], dir[maxn]; int euler[maxn], lim[maxn], rl[maxn], cnt; void dfscost(int u, int f) { cnt++; euler[u] = cnt; rl[cnt] = u; up[u] = 0; for (auto [v, c, d]:adj[u]) if (v != f) { fa[v] = u, dir[v] = c; cost[v] = cost[u] + c; dfscost(v, u); up[u] += up[v] + d; } lim[u] = cnt; } pair<int,int> seg[maxN]; int lazy[maxN]; void build(int id, int l, int r) { lazy[id] = 0; if (l == r) { seg[id] = {cost[rl[l]], rl[l]}; return; } int mid = (l+r)/2; build(id*2, l, mid); build(id*2+1, mid+1, r); seg[id] = max(seg[id*2], seg[id*2+1]); } void push(int id) { seg[id].first += lazy[id]; if (id*2 < maxN) lazy[id*2] += lazy[id]; if (id*2+1 < maxN) lazy[id*2+1] += lazy[id]; lazy[id] = 0; } void update(int id, int l, int r, int findl, int findr, int val) { push(id); if (r < findl || findr < l) return; if (findl <= l && r <= findr) { lazy[id] += val; push(id); return; } int mid = (l+r)/2; update(id*2, l, mid, findl, findr, val); update(id*2+1, mid+1, r, findl, findr, val); seg[id] = max(seg[id*2], seg[id*2+1]); } pair<int,int> qry(int id, int l, int r, int findl, int findr) { push(id); if (r < findl || findr < l) return {0, 0}; if (findl <= l && r <= findr) return seg[id]; int mid = (l+r)/2; return max(qry(id*2, l, mid, findl, findr), qry(id*2+1, mid+1, r, findl, findr)); } int curans; pair<int,int> Emx(int u) { return qry(1, 1, N, euler[u], lim[u]); } void Eupdate(int u, int val) { update(1, 1, N, euler[u], lim[u], val); } void take(int u) { while (cost[u]) { cost[u] = 0; Eupdate(u, -dir[u]); curans += dir[u]; u = fa[u]; } } void solve(int start, int add) { N = 0; nodes.clear(); init(start, 0); // cout << "start " << start << endl; find_cent(start, 0); // cout << N << " " << endl; // for (int i:nodes) cout << i << " "; cout << endl; if (N == 2) ans[2] = max(adj[nodes[0]][0].c + adj[nodes[0]][0].d + add, ans[2]); if (N <= 2) return; // cout << cent << endl; cost[cent] = 0; cnt = 0; dfscost(cent, 0); add += up[cent]; curans = 0; build(1, 1, N); // for (int i=1;i<=N;i++) cout << euler[i] << " "; cout << endl; // for (int i=1;i<=N;i++) cout << rl[i] << " "; cout << endl; // cout << N << " " << cnt << endl; vector<pair<int,int>> vec; for (auto [v, c, d]:adj[cent]) vec.push_back(Emx(v)); sort(vec.rbegin(), vec.rend()); take(vec[0].second); take(vec[1].second); ans[2] = max(curans + add, ans[2]); for (int i=3;i<=N;i++) { int guy = Emx(cent).second; take(guy); ans[i] = max(curans + add, ans[i]); } int thiscent = cent; for (auto [v, c, d]:adj[thiscent]) { edge del = {thiscent, d, c}; adj[v].erase(find(adj[v].begin(), adj[v].end(), del)); // cout << "nxt: " << thiscent << " " << v << endl; solve(v, add - up[v] - d + c); // cout << "done: " << cent << " " << v << endl; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; int all = 0; for (int i=1;i<=n-1;i++) { int u, v, c, d; cin >> u >> v >> c >> d; adj[u].push_back({v, c, d}); adj[v].push_back({u, d, c}); all += c + d; } dfs1(1, 0); ans[1] += add1; solve(1, 0); int q; cin >> q; while (q--) { int x; cin >> x; cout << all - ans[x] << "\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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...