Submission #885757

#	Time	Username	Problem	Language	Result	Execution time	Memory
885757		qthang2k11	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	368 ms	71928 KiB

designated_cities

// [+]
#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 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44