Submission #956305

#TimeUsernameProblemLanguageResultExecution timeMemory
956305PringDesignated Cities (JOI19_designated_cities)C++17
100 / 100
499 ms54432 KiB
#include <bits/stdc++.h> using namespace std; #ifdef MIKU string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m"; #define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x) void dout() { cout << dbrs << endl; } template <typename T, typename ...U> void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); } #else #define debug(...) 39 #endif #define int long long #define fs first #define sc second #define mp make_pair #define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++) typedef pair<int, int> pii; const int MXN = 200005; int n, q, br, eu[MXN], ev[MXN], a[MXN], b[MXN]; vector<int> eid[MXN]; int ans[MXN]; int nsz[MXN], fsz[MXN], rt; pii dp[MXN]; void GUIDE(int id, int par) { nsz[id] = 0; for (auto &e : eid[id]) { int i = eu[e] ^ ev[e] ^ id; if (i == par) continue; if (id == ev[e]) { swap(eu[e], ev[e]); swap(a[e], b[e]); } GUIDE(i, id); nsz[id] += a[e] + nsz[i]; } } void PUSH(pii &p, int x) { if (x >= p.fs) { p.sc = p.fs; p.fs = x; } else p.sc = max(p.sc, x); } void DP(int id, int par, int acc) { fsz[id] = acc; dp[id] = mp(0LL, 0LL); for (auto &e : eid[id]) { if (eu[e] != id) continue; int i = ev[e]; DP(i, id, acc - a[e] + b[e]); PUSH(dp[id], dp[i].fs + a[e]); } } int CALC_1() { return *min_element(fsz + 1, fsz + n + 1); } int CALC_2() { rt = 1; FOR(i, 2, n + 1) if (fsz[rt] - dp[rt].fs - dp[rt].sc > fsz[i] - dp[i].fs - dp[i].sc) rt = i; return fsz[rt] - dp[rt].fs - dp[rt].sc; } namespace TREE { pii son[MXN]; int acc[MXN]; multiset<int> MS; void get_info(int id, int par) { son[id] = mp(0LL, 0LL); for (auto &e : eid[id]) { if (eu[e] != id) continue; int i = ev[e]; get_info(i, id); son[id] = max(son[id], mp(a[e] + son[i].fs, e)); } } void decompose(int id, int par, int val) { debug(id, par, val); if (eid[id].size() == 1) { MS.insert(val); return; } decompose(ev[son[id].sc], id, val + a[son[id].sc]); for (auto &e : eid[id]) { if (eu[e] != id) continue; if (e == son[id].sc) continue; decompose(ev[e], id, a[e]); } } void DO(int rt) { get_info(rt, 0); for (auto &e : eid[rt]) { decompose(ev[e], rt, a[e]); } if (dp[rt].fs != 0) MS.erase(MS.find(dp[rt].fs)); if (dp[rt].sc != 0) MS.erase(MS.find(dp[rt].sc)); int ptr = 3; for (auto it = MS.rbegin(); it != MS.rend(); it++, ptr++) ans[ptr] = ans[ptr - 1] - *it; FOR(i, ptr, n + 1) ans[i] = ans[i - 1]; } } void miku() { cin >> n; FOR(i, 0, n - 1) { cin >> eu[i] >> ev[i] >> a[i] >> b[i]; eid[eu[i]].push_back(i); eid[ev[i]].push_back(i); } GUIDE(1, 0); DP(1, 0, nsz[1]); ans[1] = CALC_1(); ans[2] = CALC_2(); GUIDE(rt, 0); TREE::DO(rt); cin >> q; while (q--) { cin >> br; cout << ans[br] << '\n'; } } int32_t main() { cin.tie(0) -> sync_with_stdio(false); cin.exceptions(cin.failbit); miku(); return 0; }

Compilation message (stderr)

designated_cities.cpp: In function 'void TREE::decompose(long long int, long long int, long long int)':
designated_cities.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
designated_cities.cpp:87:9: note: in expansion of macro 'debug'
   87 |         debug(id, par, val);
      |         ^~~~~
#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...