Submission #376246

#TimeUsernameProblemLanguageResultExecution timeMemory
376246Kevin_Zhang_TWDesignated Cities (JOI19_designated_cities)C++17
23 / 100
2085 ms26988 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb emplace_back #define AI(i) begin(i), end(i) template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); } template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); } #ifdef KEV #define DE(args...) kout("[ " + string(#args) + " ] = ", args) void kout() { cerr << endl; } template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); } template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; } #else #define DE(...) 0 #define debug(...) 0 #endif const int MAX_N = 200010; const ll inf = 1ll << 59; int n, q; ll dprt[MAX_N], dpson[MAX_N], res[MAX_N], allsum; ll goup[MAX_N]; vector<pair<int,int>> edge[MAX_N]; ll dfs1(int x, int lst = -1) { ll uplen = 0; for (auto [u, w] : edge[x]) if (u != lst) dpson[x] += dfs1(u, x); else uplen = w; return dpson[x] + uplen; } void dfs2(int x, int lst = -1, ll upson = 0) { if (lst == -1) dprt[x] = dpson[x]; dprt[x] += upson; for (auto [u, w] : edge[x]) if (u == lst) dprt[x] -= w; for (auto [u, w] : edge[x]) if (u != lst) dfs2(u, x, dprt[x] + w); } pair<int,int> best[MAX_N]; ll bstsum[MAX_N]; pair<ll,ll> mxlen[MAX_N]; void dfs3(int x, int lst = -1) { mxlen[x] = {0, x}; for (auto [u, w] : edge[x]) if (u != lst) { dfs3(u, x); if (chmax(bstsum[x], bstsum[u])) best[x] = best[u]; mxlen[u].first += w; if (chmax(bstsum[x], mxlen[x].first + mxlen[u].first + dprt[x])) best[x] = {mxlen[x].second, mxlen[u].second}; chmax(mxlen[x], mxlen[u]); } } int pa[MAX_N], paint[MAX_N]; ll gain[MAX_N]; void dfs4(int x, int lst = -1) { if (paint[x]) gain[x] = 0; pa[x] = lst; for (auto [u, w] : edge[x]) if (u != lst) { gain[u] = gain[x] + w; dfs4(u, x); } } int rt; void takeout(int x) { while (x != -1) { paint[x] = true; x = pa[x]; } dfs4(rt); } void solve() { dfs3(1); res[2] = bstsum[1]; rt = best[1].first; dfs4(rt); takeout(best[1].second); for (int i = 3;i <= n;++i) { ll ad = 0, id = rt; for (int j = 1;j <= n;++j) if (chmax(ad, gain[j])) id = j; res[i] = res[i-1] + ad; takeout(id); } } int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> n; for (int a, b, c, d, i = 1;i < n;++i) { cin >> a >> b >> c >> d; edge[a].pb(b, c); edge[b].pb(a, d); allsum += c + d; } dfs1(1); dfs2(1); res[1] = *max_element(dprt+1, dprt+1+n); solve(); cin >> q; for (int i = 0, v;i < q;++i) { cin >> v; cout << allsum - res[v] << '\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...