oj.uz

Submission #536217

# Submission time Handle Problem Language Result Execution time Memory
536217 2022-03-12T15:34:58 Z sliviu Training (IOI07_training) C++17
100 / 100
 8 ms 828 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 636 KB Output is correct
2 Correct 5 ms 596 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 3 ms 448 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 596 KB Output is correct
2 Correct 5 ms 828 KB Output is correct
3 Correct 5 ms 724 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 8 ms 760 KB Output is correct
4 Correct 3 ms 420 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 724 KB Output is correct
2 Correct 8 ms 724 KB Output is correct
3 Correct 6 ms 700 KB Output is correct
4 Correct 5 ms 720 KB Output is correct