Submission #1189353

#TimeUsernameProblemLanguageResultExecution timeMemory
1189353onbertDesignated Cities (JOI19_designated_cities)C++20
16 / 100
171 ms59408 KiB
#include <bits/stdc++.h> using namespace std; #define int long long struct edge { int v, c, d; }; const int maxn = 2e5 + 5; int n; vector<edge> adj[maxn]; int ans[maxn]; pair<int,int> mxup[maxn]; int cur = 0; void dfs0(int u, int f) { mxup[u] = {0, u}; for (auto [v, c, d]:adj[u]) if (v != f) { dfs0(v, u); pair<int,int> val = mxup[v]; val.first += c; mxup[u] = max(val, mxup[u]); cur += d; } } pair<int,int> firsttwo; void dfs1(int u, int f, pair<int,int> mxdown) { ans[1] = max(cur, ans[1]); int curans2 = cur + max(mxdown, mxup[u]).first; // cout << u << " " << max(mxdown, mxup[u]).second << " " << cur << " " << max(mxdown, mxup[u]).first << " " << curans2 << endl; // cout << mxup[u].first << " " << mxup[u].second << endl; if (curans2 > ans[2]) { ans[2] = curans2; firsttwo = {u, max(mxdown, mxup[u]).second}; } vector<pair<int,int>> vec; for (auto[ v, c, d]:adj[u]) if (v != f) { pair<int,int> val = mxup[v]; val.first += c; vec.push_back(val); } sort(vec.rbegin(), vec.rend()); for (auto [v, c, d]:adj[u]) if (v != f) { cur -= d, cur += c; pair<int,int> nxt = mxdown; if (adj[u].size() > 1) { if (vec[0].second != mxup[v].second) nxt = max(vec[0], nxt); else nxt = max(vec[1], nxt); } nxt.first += d; dfs1(v, u, nxt); cur += d, cur -= c; } } 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; } dfs0(1, 0); dfs1(1, 0, {0, -1}); 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...