Submission #1088302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088302		tht2005	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	195 ms	40656 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;

typedef pair<long long, int> pi;

struct edge_t {
	int to, w, w_rev;
	edge_t(int x, int y, int z) : to(x), w(y), w_rev(z) {}
};

const int N = (int)2e5 + 10;

int n, pa[N], pcost[N];
vector<edge_t> aj[N];
long long ans[N], r1[N];
pi maxDep[N];

void dfs5(int v, int p) {
	maxDep[v] = pi(0, v);
	for(const edge_t& e : aj[v]) {
		if(e.to == p)
			continue;
		pa[e.to] = v;
		pcost[e.to] = e.w;
		dfs5(e.to, v);
		pi tmp = maxDep[e.to];
		tmp.first += e.w;
		if(maxDep[v] < tmp)
			maxDep[v] = tmp;
	}
}

void solve(int r) {
	dfs5(r, -1);
	priority_queue<pi> q;
	for(const edge_t& e : aj[r]) {
		pi tmp = maxDep[e.to];
		tmp.first += e.w;
		q.push(tmp);
	}

	static bool vst[N];
	long long tot = r1[r];
	int cur = 2;

	vst[r] = 1;

	for(; cur <= n && !q.empty(); ++cur) {
		pi tmp = q.top();
		q.pop();
		tot += tmp.first;
		ans[cur] = tot;

		for(int x = tmp.second; !vst[x]; x = pa[x]) {
			vst[x] = 1;
			for(const edge_t& e : aj[x]) {
				if(e.to == pa[x] || vst[e.to])
					continue;
				pi tmp = maxDep[e.to];
				tmp.first += e.w;
				q.push(tmp);
			}
		}
	}
	for(; cur <= n; ++cur)
		ans[cur] = tot;
}

pi dfs3(int v, int p, tuple<long long, int, int>& res) {
	pi mx(r1[v], v), mx2(-1, -1);
	for(const edge_t& e : aj[v]) {
		if(e.to == p)
			continue;
		pi tmp = dfs3(e.to, v, res);
		tmp.first += e.w + e.w_rev;
		if(mx < tmp)
			mx2 = mx, mx = tmp;
		else if(mx2 < tmp)
			mx2 = tmp;
	}
	if(mx2.first != -1 && get<0> (res) < mx.first + mx2.first) {
		res = { mx.first + mx2.first, mx.second, mx2.second };
	}
	return mx;
}
pair<int, int> solve2() {
	tuple<long long, int, int> res = { -1, -1, -1 };
	dfs3(1, -1, res);
	ans[2] = get<0> (res) / 2;
	return make_pair( get<1>(res), get<2>(res) );
}

void dfs2(int v, int p, long long val) {
	for(const edge_t& e : aj[v]) {
		if(e.to == p)
			continue;
		dfs2(e.to, v, val + r1[v] - r1[e.to] - e.w_rev + e.w);
	}
	r1[v] += val;
}
void dfs1(int v, int p) {
	r1[v] = 0;
	for(const edge_t& e : aj[v]) {
		if(e.to == p)
			continue;
		dfs1(e.to, v);
		r1[v] += r1[e.to] + e.w_rev;
	}
}
void solve1() {
	dfs1(1, -1);
	dfs2(1, -1, 0);
	ans[1] = *max_element(r1 + 1, r1 + 1 + n);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	long long tot = 0;
	for(int i = 1, u, v, x, y; i < n; ++i) {
		cin >> u >> v >> x >> y;
		aj[u].emplace_back(v, x, y);
		aj[v].emplace_back(u, y, x);
		tot += x + y;
	}
	solve1();
	auto p = solve2();
	solve(p.first);
	int q;
	cin >> q;
	while(q--) {
		int i;
		cin >> i;
		cout << tot - ans[i] << '\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