제출 #1127301

#제출 시각아이디문제언어결과실행 시간메모리
1127301OI_AccountDesignated Cities (JOI19_designated_cities)C++20
9 / 100
486 ms49116 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 200'000; const ll INF = 1'000'000'000'000'000'000; int n, q, a[N + 10], b[N + 10]; ll c[N + 10], d[N + 10], w[N + 10]; int mark[N + 10], x, y; ll dis[N + 10], ans[N + 10], all, sum; ll tmpAll, lazy[4 * N + 10], sumAll; vector<pair<int, int>> adj[N + 10]; vector<int> root; int tim, st[N + 10], ft[N + 10], pnt[N + 10]; pair<ll, int> seg[4 * N + 10]; pair<ll, pair<int, int>> dia; void readInput() { cin >> n; for (int i = 1; i < n; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; int u = a[i], v = b[i]; adj[u].push_back({v, i}); adj[v].push_back({u, i}); all += c[i] + d[i]; } } void dfsSt(int u = 1, int par = 0, ll wUp = 0) { st[u] = ++tim; pnt[tim] = u; dis[u] = dis[par] + wUp; for (auto [v, id]: adj[u]) if (v != par) { dfsSt(v, u, (a[id] == u? c[id]: d[id])); sumAll += (a[id] == u? d[id]: c[id]); } ft[u] = tim; } void calcDis(int u, int par = 0, ll wUp = 0) { dis[u] = dis[par] + wUp; for (auto [v, id]: adj[u]) if (v != par) calcDis(v, u, c[id] + d[id]); } int calcFar(int u) { calcDis(u); int mx = 1; for (int i = 1; i <= n; i++) if (dis[i] > dis[mx]) mx = i; return mx; } void shift(int, int, int); void update(int st, int en, ll val, int id = 1, int l = 1, int r = n + 1) { if (en <= l || r <= st) return; if (st <= l && r <= en) { seg[id].first += val; lazy[id] += val; return; } shift(id, l, r); int mid = (l + r) >> 1; update(st, en, val, id << 1, l, mid); update(st, en, val, id << 1 | 1, mid, r); seg[id] = max(seg[id << 1], seg[id << 1 | 1]); } void shift(int id, int l, int r) { if (!lazy[id]) return; int mid = (l + r) >> 1; update(l, r, lazy[id], id << 1, l, mid); update(l, r, lazy[id], id << 1 | 1, mid, r); lazy[id] = 0; } void build(int id = 1, int l = 1, int r = n + 1) { lazy[id] = 0; if (l + 1 == r) { seg[id] = {dis[pnt[l]], l}; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid, r); seg[id] = max(seg[id << 1], seg[id << 1 | 1]); } void change(int u, int par, int up, ll f) { ll x = (a[up] == par? c[up]: d[up]); ll y = (a[up] == u? c[up]: d[up]); //cout << u << ": " << st[u] << ' ' << ft[u] << endl; update(1, n + 1, y * f); update(st[u], ft[u] + 1, (- x - y) * f); sumAll = sumAll + f * (- y + x); } void dfsDia(int u = 1, int par = 0, int up = 0) { if (u != 1) change(u, par, up, 1); pair<ll, pair<int, int>> tmp = {seg[1].first + sumAll, {u, pnt[seg[1].second]}}; //cout << u << " === " << seg[1].first << ' ' << sumAll << " | " << pnt[seg[1].second] << ' ' << dis[u] << endl; dia = max(dia, tmp); for (auto [v, id]: adj[u]) if (v != par) dfsDia(v, u, id); if (u != 1) change(u, par, up, -1); } void calcDiameter() { dfsSt(); build(); dia = {-INF, {0, 0}}; dfsDia(); x = dia.second.first; y = dia.second.second; tim = 0; //cout << " -> " << x << ' ' << y << endl; } bool dfsPath(int u, int par = 0) { if (u == y) { root.push_back(u); return true; } for (auto [v, id]: adj[u]) if (v != par && dfsPath(v, u)) { root.push_back(u); sum += c[id] + d[id]; mark[id] = true; return true; } return false; } void calcSt(int u, int par = 0, ll wUp = 0) { st[u] = ++tim; pnt[tim] = u; dis[u] = dis[par] + wUp; for (auto [v, id]: adj[u]) if (v != par && !mark[id]) { calcSt(v, u, (a[id] == u? c[id]: d[id])); sum += (a[id] == u? d[id]: c[id]); } ft[u] = tim; } void checkPath() { dfsPath(x); for (auto r: root) calcSt(r); } void init() { calcDiameter(); checkPath(); } void solve2() { cin >> q; int e; cin >> e; cout << all - sum << flush; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); readInput(); init(); solve2(); 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...