Submission #1095537

#TimeUsernameProblemLanguageResultExecution timeMemory
1095537vladiliusDesignated Cities (JOI19_designated_cities)C++17
30 / 100
906 ms43212 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second #define arr3 array<int, 3> const ll inf = numeric_limits<ll> :: max(); struct ST{ vector<pair<ll, int>> t; vector<ll> a, p; int n; ST(int ns){ n = ns; a.resize(n + 1); t.resize(4 * n); p.resize(4 * n); } void upd(int p, ll x){ a[p] = x; } void build(int v, int tl, int tr){ if (tl == tr){ t[v] = {a[tl], tl}; return; } int tm = (tl + tr) / 2, vv = 2 * v; build(vv, tl, tm); build(vv + 1, tm + 1, tr); t[v] = max(t[vv], t[vv + 1]); } void build(){ fill(p.begin(), p.end(), 0); build(1, 1, n); } pair<ll, int> get(){ return t[1]; } void push(int& v){ if (!p[v]) return; int vv = 2 * v; t[vv].ff += p[v]; p[vv] += p[v]; t[vv + 1].ff += p[v]; p[vv + 1] += p[v]; p[v] = 0; } void add(int v, int tl, int tr, int& l, int& r, int& x){ if (l > tr || r < tl) return; if (l <= tl && tr <= r){ t[v].ff += x; p[v] += x; return; } int tm = (tl + tr) / 2, vv = 2 * v; push(v); add(vv, tl, tm, l, r, x); add(vv + 1, tm + 1, tr, l, r, x); t[v] = max(t[vv], t[vv + 1]); } void add(int l, int r, int x){ if (l > r) return; add(1, 1, n, l, r, x); } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; vector<arr3> g[n + 1]; ll tot = 0; for (int i = 1; i < n; i++){ int a, b, c, d; cin>>a>>b>>c>>d; tot += c; tot += d; g[a].pb({b, c, d}); g[b].pb({a, d, c}); } int q; cin>>q; vector<int> qq(q + 1); for (int i = 1; i <= q; i++){ cin>>qq[i]; } if (q == 1 && qq[1] == 1){ ll S = 0; function<void(int, int)> dfs = [&](int v, int pr){ for (auto [i, w1, w2]: g[v]){ if (i == pr) continue; S += w2; dfs(i, v); } }; dfs(1, 0); ll out = inf; function<void(int, int)> solve = [&](int v, int pr){ out = min(out, tot - S); for (auto [i, w1, w2]: g[v]){ if (i == pr) continue; S += (w1 - w2); solve(i, v); S -= (w1 - w2); } }; solve(1, 0); cout<<out<<"\n"; return 0; } if (q == 1 && qq[1] == 2){ vector<ll> d(n + 1); vector<int> tin(n + 1), tout(n + 1); ll S = 0; int timer = 0; function<void(int, int)> dfs = [&](int v, int pr){ tin[v] = ++timer; for (auto [i, w1, w2]: g[v]){ if (i == pr) continue; S += w2; d[i] = d[v] + w1; dfs(i, v); } tout[v] = timer; }; dfs(1, 0); ST T(n); for (int i = 1; i <= n; i++) T.upd(i, d[i]); T.build(); ll out = inf; function<void(int, int)> solve = [&](int v, int pr){ out = min(out, tot - (S + T.get().ff)); for (auto [i, w1, w2]: g[v]){ if (i == pr) continue; S += (w1 - w2); T.add(1, n, w2); T.add(tin[i], tout[i], -(w1 + w2)); solve(i, v); S -= (w1 - w2); T.add(1, n, -w2); T.add(tin[i], tout[i], (w1 + w2)); } }; solve(1, 0); cout<<out<<"\n"; return 0; } vector<int> tin(n + 1), tout(n + 1), inv(n + 1), p(n + 1), dd(n + 1); vector<ll> d(n + 1); int timer = 0; ll S = 0; function<void(int, int)> dfs = [&](int v, int pr){ p[v] = pr; tin[v] = ++timer; for (auto [i, w1, w2]: g[v]){ if (i == pr) continue; S += w2; dd[i] = w1; d[i] = d[v] + w1; dfs(i, v); } tout[v] = timer; }; vector<ll> out(n + 1, inf); vector<bool> used(n + 1); ST T(n); for (int i = 1; i <= n; i++){ S = d[i] = dd[i] = timer = 0; dfs(i, 0); out[1] = min(out[1], tot - S); for (int j = 1; j <= n; j++){ T.upd(tin[j], d[j]); inv[tin[j]] = j; } T.build(); fill(used.begin(), used.end(), 0); used[i] = 1; for (int j = 2; j <= n; j++){ auto [x, y] = T.get(); if (!x) continue; int v = inv[y]; while (!used[v]){ T.add(tin[v], tout[v], -dd[v]); used[v] = 1; v = p[v]; } S += x; out[j] = min(out[j], tot - S); } } for (int i = 1; i <= n; i++) out[i] = min(out[i], out[i - 1]); for (int i = 1; i <= q; i++){ cout<<out[qq[i]]<<"\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...