Submission #220606

#	Time	Username	Problem	Language	Result	Execution time	Memory
220606		atoiz	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	549 ms	47484 KiB

designated_cities

/*input
15
14 5 12 7
14 12 6 5
14 10 14 16
9 14 16 12
13 7 4 15
1 3 8 1
6 7 15 13
15 4 4 6
9 1 12 6
13 1 7 6
13 4 5 15
2 6 11 19
8 4 12 7
13 11 14 5
3
3
6
7
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <numeric>

using namespace std;

const int MAXN = 200007;
const int64_t INF = 1e17;
int N, Q, A[MAXN], B[MAXN], C[MAXN], D[MAXN];
int root = 0;
int64_t ans[MAXN], up[MAXN], down[MAXN], dep[MAXN];
int furthest[MAXN];
vector<int> adj[MAXN];
vector<int64_t> vals;

void dfs_down(int u, int p)
{
	down[u] = 0;
	furthest[u] = u;
	for (int id : adj[u]) {
		int v = A[id] ^ B[id] ^ u, c = (A[id] == u ? C[id] : D[id]);
		if (v == p) continue;
		dep[v] = dep[u] + c;
		dfs_down(v, u);
		if (dep[furthest[u]] < dep[furthest[v]]) furthest[u] = furthest[v];
		down[u] += c + down[v];
	}
}

void dfs_up(int u, int p)
{
	int leaf[2] = {0, 0};

	for (int id : adj[u]) {
		int v = A[id] ^ B[id] ^ u, c = (A[id] == u ? C[id] : D[id]);
		if (v == p) continue;
		up[v] = up[u] + down[u] - down[v] + (C[id] ^ D[id] ^ c) - c;
		dfs_up(v, u);

		int cur = furthest[v];
		if (dep[cur] > dep[leaf[0]]) swap(cur, leaf[0]);
		if (dep[cur] > dep[leaf[1]]) swap(cur, leaf[1]);
	}

	if (up[u] + down[u] < ans[1]) ans[1] = up[u] + down[u];
	if (up[u] + down[u] - dep[leaf[0]] - dep[leaf[1]] + 2 * dep[u] < ans[2]) {
		ans[2] = up[u] + down[u] - dep[leaf[0]] - dep[leaf[1]] + 2 * dep[u];
		root = leaf[0];
	}
}

void dfs_calc(int u, int p, int64_t inc)
{
	vals.push_back((u == furthest[u]) * inc);
	for (int id : adj[u]) {
		int v = A[id] ^ B[id] ^ u, c = (A[id] == u ? C[id] : D[id]);
		if (v == p) continue;
		dfs_calc(v, u, c + (furthest[u] == furthest[v]) * inc);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	for (int i = 0; i < N - 1; ++i) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		adj[A[i]].push_back(i);
		adj[B[i]].push_back(i);
	}

	ans[1] = ans[2] = INF;
	vals.reserve(N);

	dfs_down(1, 0);
	dfs_up(1, 0);
	dep[root] = 0, dfs_down(root, 0);
	dfs_calc(root, 0, 0);

	sort(vals.begin(), vals.end()), reverse(vals.begin(), vals.end());
	int64_t total = accumulate(vals.begin(), vals.end(), 0ll);
	assert(ans[2] == total - vals[0]);
	for (int i = 2; i <= N; ++i) {
		ans[i] = (total -= vals[i - 2]);
	}

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

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44