Submission #996474

#TimeUsernameProblemLanguageResultExecution timeMemory
996474otariusDesignated Cities (JOI19_designated_cities)C++17
100 / 100
296 ms83612 KiB
#include <iostream> #include <algorithm> #include <vector> #include <set> #include <cstring> #include <queue> #include <map> #include <cmath> #include <iomanip> using namespace std; #define ff first #define sc second #define pb push_back #define ll long long #define pll pair<ll, ll> #define pii pair <int, int> #define ull unsigned long long #define int long long // #define int unsigned long long const ll inf = 1e9 + 7; const ll weirdMod = 998244353; struct node { int mx, nd; } t[800040]; pii rts; bool used[200005]; vector<pair<int, pii>> G[200005]; int n, q, ans[200005], dep[200005], dp[200005], p[200005], val[200005], cst[200005], in[200005], out[200005], lazy[800040], rev[200005], mx, tim; bool comp(int a, int b) { return (val[a] + dep[a] > val[b] + dep[b]); } void prop(int v, int tl, int tr) { t[v].mx += lazy[v]; if (tl != tr) { lazy[2 * v] += lazy[v]; lazy[2 * v + 1] += lazy[v]; } lazy[v] = 0; } void build(int v, int tl, int tr) { if (tl == tr) { t[v].nd = tl; return; } int tm = (tl + tr) / 2; build(2 * v, tl, tm); build(2 * v + 1, tm + 1, tr); } void update(int v, int tl, int tr, int l, int r, int val) { if (lazy[v]) prop(v, tl, tr); if (r < tl || tr < l) return; if (l <= tl && tr <= r) { t[v].mx += val; if (tl != tr) { lazy[2 * v] += val; lazy[2 * v + 1] += val; } return; } int tm = (tl + tr) / 2; update(2 * v, tl, tm, l, min(r, tm), val); update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val); if (t[2 * v].mx > t[2 * v + 1].mx) t[v] = t[2 * v]; else t[v] = t[2 * v + 1]; } void subtract(int v) { if (used[v]) return; update(1, 1, n, in[v], out[v], -cst[v]); used[v] = 1; subtract(p[v]); } void temp_dfs(int v, int par) { for (auto u : G[v]) { if (u.ff == par) continue; val[1] += u.sc.sc; temp_dfs(u.ff, v); } } void reroot_dfs(int v, int par) { for (auto u : G[v]) { if (u.ff == par) continue; val[u.ff] = val[v] - u.sc.sc + u.sc.ff; reroot_dfs(u.ff, v); } } void pair_dfs(int v, int par) { vector<int> vec = {v}; for (auto u : G[v]) { if (u.ff == par) continue; dep[u.ff] = dep[v] + u.sc.ff + u.sc.sc; pair_dfs(u.ff, v); vec.pb({dp[u.ff]}); } sort(vec.begin(), vec.end(), comp); dp[v] = vec[0]; if (vec.size() == 1) return; int cur = val[vec[0]] + val[vec[1]] + dep[vec[0]] + dep[vec[1]] - 2 * dep[v]; if (cur > mx) { mx = cur; rts = {vec[0], vec[1]}; } } void build_dfs(int v, int par, int lst) { p[v] = par; cst[v] = lst; in[v] = ++tim; rev[in[v]] = v; dep[v] = dep[par] + lst; if (G[v].size() == 1 && v != rts.sc) update(1, 1, n, in[v], in[v], dep[v]); for (auto u : G[v]) { if (u.ff == par) continue; build_dfs(u.ff, v, u.sc.ff); } out[v] = tim; } void solve() { cin >> n; int sum = 0; for (int i = 1; i < n; i++) { int a, b, x, y; cin >> a >> b >> x >> y; G[a].pb({b, {x, y}}); G[b].pb({a, {y, x}}); sum += x + y; } temp_dfs(1, 0); reroot_dfs(1, 0); pair_dfs(1, 0); ans[2] = mx / 2; for (int i = 1; i <= n; i++) ans[1] = max(ans[1], val[i]); build(1, 1, n); build_dfs(rts.sc, 0, 0); used[rts.sc] = 1; subtract(rts.ff); for (int i = 3; i <= n; i++) { ans[i] = ans[i - 1] + t[1].mx; subtract(rev[t[1].nd]); } int q; cin >> q; while (q--) { int x; cin >> x; cout << sum - ans[x] << '\n'; } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; // cin >> t; while (t--) { solve(); cout << '\n'; } return 0; }
#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...