제출 #530311

#제출 시각아이디문제언어결과실행 시간메모리
5303114fectaDesignated Cities (JOI19_designated_cities)C++17
100 / 100
602 ms79256 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int ll #define ld long double #define pii pair<int, int> #define f first #define s second #define boost() cin.tie(0), cin.sync_with_stdio(0) struct edge { int u, f, b; }; const int MN = 200005; int n, q, u, v, w, x, cost, ans[MN], dp[MN], node[MN], pre[MN], up[MN], vis[MN], tim, in[MN], out[MN], id[MN * 2], lzy[MN * 8]; pii st[MN * 8]; vector<edge> a[MN]; void push_down(int l, int r, int idx) { if (!lzy[idx]) return; st[idx].f += lzy[idx]; if (l != r) lzy[idx * 2] += lzy[idx], lzy[idx * 2 + 1] += lzy[idx]; lzy[idx] = 0; } void build(int l, int r, int idx) { if (l == r) {st[idx] = {0, id[l]}; return;} int mid = (l + r) >> 1; build(l, mid, idx * 2), build(mid + 1, r, idx * 2 + 1); st[idx] = max(st[idx * 2], st[idx * 2 + 1]); } void upd(int l, int r, int x, int y, int val, int idx) { push_down(l, r, idx); if (r < x || l > y) return; if (r <= y && l >= x) { lzy[idx] += val; push_down(l, r, idx); return; } int mid = (l + r) >> 1; upd(l, mid, x, y, val, idx * 2), upd(mid + 1, r, x, y, val, idx * 2 + 1); st[idx] = max(st[idx * 2], st[idx * 2 + 1]); } void dfs1(int cur, int par) { for (auto nxt : a[cur]) { if (nxt.u == par) continue; cost += nxt.f; dfs1(nxt.u, cur); } } void dfs2(int cur, int par) { ans[1] = min(ans[1], cost); for (auto nxt : a[cur]) { if (nxt.u == par) continue; cost += nxt.b - nxt.f; dfs2(nxt.u, cur); cost += nxt.f - nxt.b; } } void dfs3(int cur, int par) { node[cur] = cur; for (auto nxt : a[cur]) { if (nxt.u == par) continue; cost += nxt.b - nxt.f; dfs3(nxt.u, cur); cost += nxt.f - nxt.b; int val = dp[cur] + dp[nxt.u] + nxt.f; if (cost - val < ans[2]) { ans[2] = cost - val; u = node[cur], v = node[nxt.u]; } if (dp[cur] < dp[nxt.u] + nxt.f) { dp[cur] = dp[nxt.u] + nxt.f; node[cur] = node[nxt.u]; } } } void dfs4(int cur, int par) { in[cur] = ++tim; id[tim] = cur; pre[cur] = par; for (auto nxt : a[cur]) { if (nxt.u == par) continue; up[nxt.u] = nxt.f; dfs4(nxt.u, cur); } out[cur] = ++tim; id[tim] = cur; } void solve1() { dfs1(1, 0); dfs2(1, 0); } void solve_other() { dfs3(1, 0); dfs4(u, 0); build(1, n * 2, 1); while (v != u) vis[v] = 1, v = pre[v]; vis[v] = 1; for (int i = 1; i <= n; i++) if (!vis[i]) upd(1, n * 2, in[i], out[i], up[i], 1); for (int i = 3; i <= n; i++) { ans[i] = ans[i - 1] - st[1].f; v = st[1].s; while (!vis[v]) upd(1, n * 2, in[v], out[v], -up[v], 1), vis[v] = 1, v = pre[v]; } } int32_t main() { boost(); memset(ans, 0x3f, sizeof(ans)); cin >> n; for (int i = 1; i < n; i++) { cin >> u >> v >> w >> x; a[u].push_back({v, w, x}); a[v].push_back({u, x, w}); } solve1(); solve_other(); cin >> q; while (q--) { cin >> x; printf("%lld\n", ans[x]); } 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...