Submission #536217

#	Time	Username	Problem	Language	Result	Execution time	Memory
536217		sliviu	Training (IOI07_training)	C++17	100 / 100	8 ms	828 KiB

training

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, m, ans = 0, t = 0;
	cin >> n >> m;
	vector<int> tin(n + 1), tout(n + 1), p(n + 1), nr(n + 1), d(n + 1);
	vector<array<int, 10>> dpu(n + 1);
	vector<vector<int>> G(n + 1), dp(n + 1);
	vector<vector<tuple<int, int, int>>> q(n + 1);
	vector<tuple<int, int, int>> E;
	tout[0] = n + 1;
	while (m--) {
		int x, y, z;
		cin >> x >> y >> z;
		if (z == 0)
			G[x].emplace_back(y), G[y].emplace_back(x);
		ans += z;
		E.emplace_back(x, y, z);
	}
	function<void(int, int)> dfs = [&](int node, int last) {
		tin[node] = ++t;
		d[node] = d[last] + 1;
		p[node] = dpu[node][0] = last;
		int cnt = 0;
		for (auto x : G[node])
			if (x != last) {
				nr[x] = 1 << cnt++;
				dfs(x, node);
			}
		dp[node].resize(1 << cnt);
		tout[node] = t;
	};
	dfs(1, 0);
	for (int i = 1; i < 10; ++i)
		for (int j = 1; j <= n; ++j)
			dpu[j][i] = dpu[dpu[j][i - 1]][i - 1];
	auto ok = [&](int x, int y) {return tin[x] <= tin[y] && tout[x] >= tout[y]; };
	auto lca = [&](int a, int b) {
		if (d[a] > d[b])
			swap(a, b);
		if (ok(a, b))
			return a;
		for (int i = 9; ~i; --i)
			if (!ok(dpu[b][i], a))
				b = dpu[b][i];
		return dpu[b][0];
	};
	for (auto [x, y, z] : E) {
		int w = lca(x, y);
		if (z == 0 || !((d[x] + d[y] - 2 * d[w]) & 1))
			q[w].emplace_back(x, y, z);
	}
	function<void(int, int)> dfs2 = [&](int node, int last) {
		for (auto x : G[node])
			if (x != last)
				dfs2(x, node);
		for (auto [x, y, z] : q[node]) {
			int xx = 0, yy = 0, cost = z, mask = dp[node].size() - 1;
			for (; x != node; xx = nr[x], x = p[x])
				cost += dp[x][xx];
			for (; y != node; yy = nr[y], y = p[y])
				cost += dp[y][yy];
			mask ^= xx, mask ^= yy;
			for (int i = mask; i >= 0; i = (i - 1) & mask) {
				dp[node][i] = max(dp[node][i], dp[node][i | xx | yy] + cost);
				if (!i)
					break;
			}
		}
	};
	dfs2(1, 0);
	cout << ans - dp[1][0];
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9