oj.uz

Submission #885757

# Submission time Handle Problem Language Result Execution time Memory
885757 2023-12-10T16:03:56 Z qthang2k11 Designated Cities (JOI19_designated_cities) C++17
100 / 100
 368 ms 71928 KB 
// [+]
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Edge { // w: out, rw: in
	int y, w, rw;
	Edge() = default;
	Edge(int y, int w, int rw):
		y(y), w(w), rw(rw) {}
};

const int N = 2e5 + 5;

vector<Edge> adj[N];
int n;

ll tot = 0, ans1 = 0;

ll sum_out[N];

ll dfs(int x, int p) {
	for (const auto &elem: adj[x]) {
		int y = elem.y;
		if (y == p) continue;
		sum_out[x] += dfs(y, x) + elem.w;
	}
	return sum_out[x];
}

ll dfs1(int x, int p, ll up) {
	ll down = 0;
	for (const auto &elem: adj[x]) {
		int y = elem.y;
		if (y == p) continue;
		down += dfs1(y, x, up + sum_out[x] - sum_out[y] - elem.w + elem.rw) + elem.w;
	}
	ans1 = max(ans1, up + down);
	return down;
}

bool chosen[N];
ll ans[N];

int tin[N], tout[N], node[N], tcur = 0;
int par[N], rt;

int xtopar[N];

namespace e2 {
	const ll INF = 1e18;
	
	array<ll, 3> res = {0, 0, 0};
	
	pair<ll, int> mx_up[N];
	
	pair<ll, int> dfs1(int x, int p, ll up) {
		pair<ll, int> &fst = mx_up[x], scd, tmp, now;

		scd = tmp = {-INF, 0};
		fst = {0, x};
		
		for (const auto &elem: adj[x]) {
			int y = elem.y, w = elem.w, rw = elem.rw;
			if (y == p) continue;
			now = dfs1(y, x, up + sum_out[x] - sum_out[y] - w + rw);
			tmp = max(tmp, {now.first + sum_out[x] - sum_out[y] + w + rw, now.second});
			scd = max(scd, {mx_up[y].first + rw, mx_up[y].second});
			if (scd > fst) swap(scd, fst);
		}
		
		res = max(res, {up + fst.first + scd.first + sum_out[x], fst.second, scd.second});
		
		return tmp;
	}
	
	void dfs2(int x, int p) {
		tin[x] = ++tcur;
		node[tcur] = x;
		par[x] = p;
		for (const auto &elem: adj[x]) {
			int y = elem.y;
			if (y == p) continue;
			dfs2(y, x);
			xtopar[y] = elem.rw;
		}
		tout[x] = tcur;
	}
		
	void solve() {
		auto now = dfs1(1, 0, 0);
		res = max(res, {now.first, 1, now.second});
		
		ans[2] = tot - res[0];
		rt = res[1];
		
		dfs2(rt, 0);
				
		int cur = res[2];
		while (cur) {
			chosen[cur] = 1;
			cur = par[cur];
		}
	}
}

ll dis[N];

void dfs2(int x, int p, ll d) {
	if (chosen[x]) d = 0;
	dis[x] = d;
	
	for (const auto &elem: adj[x]) {
		int y = elem.y;
		if (y == p) continue;
		dfs2(y, x, d + elem.rw);
	}
}

struct Node {
	ll val; int x; ll lz;
	Node() { val = x = lz = 0; }
	Node(ll val, int x, ll lz = 0):
		val(val), x(x), lz(lz) {}
};

Node merge(const Node &x, const Node &y) {
	if (x.val > y.val) return Node(x.val, x.x);
	return Node(y.val, y.x);
}

struct SegmentTree {
	Node IT[N << 2];
	SegmentTree() = default;
	
	void build(int id, int l, int r) {
		if (l == r) return IT[id] = Node(dis[node[l]], node[l]), void();
		int mid = (l + r) / 2;
		build(id << 1, l, mid);
		build(id << 1 | 1, mid + 1, r);
		IT[id] = merge(IT[id << 1], IT[id << 1 | 1]);
	}
	
	inline void apply(int id, ll w) {
		IT[id].val += w;
		IT[id].lz += w;
	}
	
	inline void down(int id) {
		ll &lz = IT[id].lz;
		if (lz) {
			apply(id << 1, lz);
			apply(id << 1 | 1, lz);
			lz = 0;
		}
	}
	
	void update(int x, int y, ll w, int id, int l, int r) {
		if (l > y || r < x) return;
		if (x <= l && r <= y) 
			return apply(id, w);
		down(id);
		int mid = (l + r) / 2;
		update(x, y, w, id << 1, l, mid);
		update(x, y, w, id << 1 | 1, mid + 1, r);
		IT[id] = merge(IT[id << 1], IT[id << 1 | 1]);
	}
	
	inline void update(int x, int y, ll w) {
		update(x, y, w, 1, 1, n);
	}
	
	void update_val(int x, int id, int l, int r) {
		if (l == r) return IT[id] = Node(0, x), void();
		down(id);
		int mid = (l + r) / 2;
		if (x <= mid) update_val(x, id << 1, l, mid);
		else update_val(x, id << 1 | 1, mid + 1, r);
		IT[id] = merge(IT[id << 1], IT[id << 1 | 1]);
	}
	
	inline void update_val(int x) {
		update_val(x, 1, 1, n);
	}
	
	pair<ll, int> get() {
		return {IT[1].val, IT[1].x};
	}
} seg;

void del(int x) {
	assert(!chosen[x]);
	
	vector<int> arr;
	while (!chosen[x]) {
		chosen[x] = 1;
		arr.emplace_back(x);
		x = par[x];
	}
	
	reverse(arr.begin(), arr.end());
	
	ll pref = 0;
	for (int x: arr) {
		pref += xtopar[x];
		for (const auto &elem: adj[x]) {
			int y = elem.y;
			if (chosen[y]) continue;
			seg.update(tin[y], tout[y], -pref);
		}
		seg.update_val(tin[x]);
	}
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> n; 
	for (int i = 1; i < n; i++) {
		int x, y, w, rw;
		cin >> x >> y >> rw >> w;
		adj[x].emplace_back(y, w, rw);
		adj[y].emplace_back(x, rw, w);
		tot += w + rw;
	}
	
	ignore = dfs(1, 0);
	
	ignore = dfs1(1, 0, 0);
	ans[1] = tot - ans1;
		
	e2::solve(); // case E = 2
	
	dfs2(rt, 0, 0);
	seg.build(1, 1, n);
	
	ll val; int node;
	for (int i = 3; i <= n; i++) {
		ans[i] = ans[i - 1];		
		tie(val, node) = seg.get();
		if (val <= 0) {
			for (int j = i + 1; j <= n; j++)
				ans[j] = ans[j - 1];
			break;
		}
		ans[i] -= val;
		del(node);
	}

	int q; 	
	cin >> q;
	while (q--) {
		int x; cin >> x;
		cout << ans[x] << '\n';
	}
	
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29532 KB Output is correct
2 Correct 6 ms 29532 KB Output is correct
3 Correct 5 ms 29532 KB Output is correct
4 Correct 5 ms 29668 KB Output is correct
5 Correct 5 ms 29532 KB Output is correct
6 Correct 5 ms 29532 KB Output is correct
7 Correct 5 ms 29688 KB Output is correct
8 Correct 6 ms 29532 KB Output is correct
9 Correct 5 ms 29532 KB Output is correct
10 Correct 5 ms 29532 KB Output is correct
11 Correct 5 ms 29532 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29784 KB Output is correct
2 Correct 320 ms 44116 KB Output is correct
3 Correct 257 ms 67408 KB Output is correct
4 Correct 290 ms 44124 KB Output is correct
5 Correct 281 ms 43900 KB Output is correct
6 Correct 265 ms 47484 KB Output is correct
7 Correct 249 ms 43780 KB Output is correct
8 Correct 248 ms 68496 KB Output is correct
9 Correct 200 ms 44540 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29528 KB Output is correct
2 Correct 352 ms 44148 KB Output is correct
3 Correct 245 ms 71832 KB Output is correct
4 Correct 253 ms 44368 KB Output is correct
5 Correct 259 ms 43948 KB Output is correct
6 Correct 265 ms 48128 KB Output is correct
7 Correct 216 ms 44456 KB Output is correct
8 Correct 259 ms 59644 KB Output is correct
9 Correct 202 ms 44800 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29532 KB Output is correct
2 Correct 6 ms 29532 KB Output is correct
3 Correct 5 ms 29532 KB Output is correct
4 Correct 5 ms 29668 KB Output is correct
5 Correct 5 ms 29532 KB Output is correct
6 Correct 5 ms 29532 KB Output is correct
7 Correct 5 ms 29688 KB Output is correct
8 Correct 6 ms 29532 KB Output is correct
9 Correct 5 ms 29532 KB Output is correct
10 Correct 5 ms 29532 KB Output is correct
11 Correct 5 ms 29532 KB Output is correct
12 Correct 5 ms 29532 KB Output is correct
13 Correct 6 ms 29788 KB Output is correct
14 Correct 6 ms 29788 KB Output is correct
15 Correct 6 ms 29788 KB Output is correct
16 Correct 6 ms 29752 KB Output is correct
17 Correct 6 ms 29656 KB Output is correct
18 Correct 6 ms 29668 KB Output is correct
19 Correct 6 ms 29676 KB Output is correct
20 Correct 6 ms 29788 KB Output is correct
21 Correct 6 ms 29788 KB Output is correct
22 Correct 6 ms 29788 KB Output is correct
23 Correct 6 ms 29788 KB Output is correct
24 Correct 6 ms 29788 KB Output is correct
25 Correct 6 ms 30044 KB Output is correct
26 Correct 6 ms 29788 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29784 KB Output is correct
2 Correct 320 ms 44116 KB Output is correct
3 Correct 257 ms 67408 KB Output is correct
4 Correct 290 ms 44124 KB Output is correct
5 Correct 281 ms 43900 KB Output is correct
6 Correct 265 ms 47484 KB Output is correct
7 Correct 249 ms 43780 KB Output is correct
8 Correct 248 ms 68496 KB Output is correct
9 Correct 200 ms 44540 KB Output is correct
10 Correct 5 ms 29528 KB Output is correct
11 Correct 352 ms 44148 KB Output is correct
12 Correct 245 ms 71832 KB Output is correct
13 Correct 253 ms 44368 KB Output is correct
14 Correct 259 ms 43948 KB Output is correct
15 Correct 265 ms 48128 KB Output is correct
16 Correct 216 ms 44456 KB Output is correct
17 Correct 259 ms 59644 KB Output is correct
18 Correct 202 ms 44800 KB Output is correct
19 Correct 5 ms 29528 KB Output is correct
20 Correct 286 ms 43964 KB Output is correct
21 Correct 247 ms 71928 KB Output is correct
22 Correct 267 ms 44164 KB Output is correct
23 Correct 275 ms 44116 KB Output is correct
24 Correct 273 ms 44372 KB Output is correct
25 Correct 278 ms 44116 KB Output is correct
26 Correct 283 ms 44112 KB Output is correct
27 Correct 266 ms 43892 KB Output is correct
28 Correct 262 ms 47348 KB Output is correct
29 Correct 270 ms 44464 KB Output is correct
30 Correct 246 ms 44212 KB Output is correct
31 Correct 239 ms 43936 KB Output is correct
32 Correct 275 ms 60792 KB Output is correct
33 Correct 201 ms 44700 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29532 KB Output is correct
2 Correct 6 ms 29532 KB Output is correct
3 Correct 5 ms 29532 KB Output is correct
4 Correct 5 ms 29668 KB Output is correct
5 Correct 5 ms 29532 KB Output is correct
6 Correct 5 ms 29532 KB Output is correct
7 Correct 5 ms 29688 KB Output is correct
8 Correct 6 ms 29532 KB Output is correct
9 Correct 5 ms 29532 KB Output is correct
10 Correct 5 ms 29532 KB Output is correct
11 Correct 5 ms 29532 KB Output is correct
12 Correct 5 ms 29784 KB Output is correct
13 Correct 320 ms 44116 KB Output is correct
14 Correct 257 ms 67408 KB Output is correct
15 Correct 290 ms 44124 KB Output is correct
16 Correct 281 ms 43900 KB Output is correct
17 Correct 265 ms 47484 KB Output is correct
18 Correct 249 ms 43780 KB Output is correct
19 Correct 248 ms 68496 KB Output is correct
20 Correct 200 ms 44540 KB Output is correct
21 Correct 5 ms 29528 KB Output is correct
22 Correct 352 ms 44148 KB Output is correct
23 Correct 245 ms 71832 KB Output is correct
24 Correct 253 ms 44368 KB Output is correct
25 Correct 259 ms 43948 KB Output is correct
26 Correct 265 ms 48128 KB Output is correct
27 Correct 216 ms 44456 KB Output is correct
28 Correct 259 ms 59644 KB Output is correct
29 Correct 202 ms 44800 KB Output is correct
30 Correct 5 ms 29532 KB Output is correct
31 Correct 6 ms 29788 KB Output is correct
32 Correct 6 ms 29788 KB Output is correct
33 Correct 6 ms 29788 KB Output is correct
34 Correct 6 ms 29752 KB Output is correct
35 Correct 6 ms 29656 KB Output is correct
36 Correct 6 ms 29668 KB Output is correct
37 Correct 6 ms 29676 KB Output is correct
38 Correct 6 ms 29788 KB Output is correct
39 Correct 6 ms 29788 KB Output is correct
40 Correct 6 ms 29788 KB Output is correct
41 Correct 6 ms 29788 KB Output is correct
42 Correct 6 ms 29788 KB Output is correct
43 Correct 6 ms 30044 KB Output is correct
44 Correct 6 ms 29788 KB Output is correct
45 Correct 5 ms 29528 KB Output is correct
46 Correct 286 ms 43964 KB Output is correct
47 Correct 247 ms 71928 KB Output is correct
48 Correct 267 ms 44164 KB Output is correct
49 Correct 275 ms 44116 KB Output is correct
50 Correct 273 ms 44372 KB Output is correct
51 Correct 278 ms 44116 KB Output is correct
52 Correct 283 ms 44112 KB Output is correct
53 Correct 266 ms 43892 KB Output is correct
54 Correct 262 ms 47348 KB Output is correct
55 Correct 270 ms 44464 KB Output is correct
56 Correct 246 ms 44212 KB Output is correct
57 Correct 239 ms 43936 KB Output is correct
58 Correct 275 ms 60792 KB Output is correct
59 Correct 201 ms 44700 KB Output is correct
60 Correct 5 ms 29528 KB Output is correct
61 Correct 329 ms 45400 KB Output is correct
62 Correct 262 ms 68176 KB Output is correct
63 Correct 283 ms 45564 KB Output is correct
64 Correct 294 ms 45392 KB Output is correct
65 Correct 290 ms 45196 KB Output is correct
66 Correct 289 ms 45392 KB Output is correct
67 Correct 299 ms 45140 KB Output is correct
68 Correct 290 ms 45544 KB Output is correct
69 Correct 292 ms 48212 KB Output is correct
70 Correct 300 ms 45340 KB Output is correct
71 Correct 273 ms 45500 KB Output is correct
72 Correct 298 ms 46192 KB Output is correct
73 Correct 368 ms 59220 KB Output is correct
74 Correct 225 ms 47780 KB Output is correct