oj.uz

Submission #885754

# Submission time Handle Problem Language Result Execution time Memory
885754 2023-12-10T16:01:17 Z qthang2k11 Designated Cities (JOI19_designated_cities) C++17
16 / 100
 281 ms 78168 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];
	}
	
	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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29528 KB Output is correct
2 Correct 5 ms 29532 KB Output is correct
3 Correct 5 ms 29540 KB Output is correct
4 Correct 5 ms 29532 KB Output is correct
5 Correct 5 ms 29724 KB Output is correct
6 Correct 5 ms 29532 KB Output is correct
7 Correct 5 ms 29532 KB Output is correct
8 Incorrect 5 ms 29532 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29532 KB Output is correct
2 Correct 269 ms 47608 KB Output is correct
3 Correct 223 ms 73812 KB Output is correct
4 Correct 154 ms 48984 KB Output is correct
5 Correct 281 ms 50356 KB Output is correct
6 Correct 251 ms 53844 KB Output is correct
7 Correct 237 ms 50284 KB Output is correct
8 Correct 238 ms 74652 KB Output is correct
9 Correct 257 ms 50940 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 192 ms 47612 KB Output is correct
3 Correct 281 ms 78168 KB Output is correct
4 Correct 163 ms 48980 KB Output is correct
5 Correct 254 ms 50228 KB Output is correct
6 Correct 257 ms 54604 KB Output is correct
7 Correct 255 ms 50424 KB Output is correct
8 Correct 269 ms 66064 KB Output is correct
9 Correct 235 ms 50428 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29528 KB Output is correct
2 Correct 5 ms 29532 KB Output is correct
3 Correct 5 ms 29540 KB Output is correct
4 Correct 5 ms 29532 KB Output is correct
5 Correct 5 ms 29724 KB Output is correct
6 Correct 5 ms 29532 KB Output is correct
7 Correct 5 ms 29532 KB Output is correct
8 Incorrect 5 ms 29532 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29532 KB Output is correct
2 Correct 269 ms 47608 KB Output is correct
3 Correct 223 ms 73812 KB Output is correct
4 Correct 154 ms 48984 KB Output is correct
5 Correct 281 ms 50356 KB Output is correct
6 Correct 251 ms 53844 KB Output is correct
7 Correct 237 ms 50284 KB Output is correct
8 Correct 238 ms 74652 KB Output is correct
9 Correct 257 ms 50940 KB Output is correct
10 Correct 5 ms 29528 KB Output is correct
11 Correct 192 ms 47612 KB Output is correct
12 Correct 281 ms 78168 KB Output is correct
13 Correct 163 ms 48980 KB Output is correct
14 Correct 254 ms 50228 KB Output is correct
15 Correct 257 ms 54604 KB Output is correct
16 Correct 255 ms 50424 KB Output is correct
17 Correct 269 ms 66064 KB Output is correct
18 Correct 235 ms 50428 KB Output is correct
19 Correct 5 ms 29528 KB Output is correct
20 Incorrect 222 ms 50544 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29528 KB Output is correct
2 Correct 5 ms 29532 KB Output is correct
3 Correct 5 ms 29540 KB Output is correct
4 Correct 5 ms 29532 KB Output is correct
5 Correct 5 ms 29724 KB Output is correct
6 Correct 5 ms 29532 KB Output is correct
7 Correct 5 ms 29532 KB Output is correct
8 Incorrect 5 ms 29532 KB Output isn't correct
9 Halted 0 ms 0 KB -