Submission #1189462

#TimeUsernameProblemLanguageResultExecution timeMemory
1189462onbertDesignated Cities (JOI19_designated_cities)C++20
23 / 100
2095 ms27756 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; 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]; void dfscost(int u, int f) { 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; } } int curans; pair<int,int> Emx(int u) { pair<int,int> val = {cost[u], u}; for (auto [v, c, d]:adj[u]) if (v != fa[u]) { val = max(Emx(v), val); } return val; } void Eupdate(int u, int val) { cost[u] += val; for (auto [v, c, d]:adj[u]) if (v != fa[u]) Eupdate(v, val); } void update(int u) { while (cost[u]) { 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; dfscost(cent, 0); add += up[cent]; curans = 0; vector<pair<int,int>> vec; for (auto [v, c, d]:adj[cent]) vec.push_back(Emx(v)); sort(vec.rbegin(), vec.rend()); update(vec[0].second); update(vec[1].second); ans[2] = max(curans + add, ans[2]); // cout << "TEST\n"; // cout << cent << endl; // for (int i:nodes) cout << i << " "; cout << endl; // cout << curans + add << endl; for (int i=3;i<=N;i++) { int guy = Emx(cent).second; update(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...