Submission #410589

#	Time	Username	Problem	Language	Result	Execution time	Memory
410589		dongliu0426	Training (IOI07_training)	C++17	0 / 100	9 ms	2124 KiB

training

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define f first
#define s second

const int N = 1005;
const int D = 10;

int n, m, dd[N], up[N][D], dp[N][1 << D], st[N], en[N], ti = 0;

vector<int> adj[N];
vector<array<int, 3>> nontree;
vector<array<int, 4>> todo;

void dfs(int i, int k) {
	up[i][0] = k, st[i] = ++ti;
	for (int ii = 1; ii < D; ++ii)
		up[i][ii] = up[up[i][ii - 1]][ii - 1];
	for (int j : adj[i])
		if (j != k)
			dd[j] = dd[i] + 1, dfs(j, i);
	en[i] = ++ti;
}

int jump(int i, int d) {
	for (int ii = 0; ii < D; ++ii)
		if (d & (1 << ii))
			i = up[i][ii];
	return i;
}

int lca(int i, int j) {
	if (dd[i] < dd[j]) swap(i, j);
	i = jump(i, dd[i] - dd[j]);
	for (int ii = D - 1; ii >= 0; --ii)
		if (up[i][ii] != up[j][ii])
			i = up[i][ii], j = up[j][ii];
	return (i != j ? up[i][0] : i);
}

int dist(int i, int j) {
	return dd[i] + dd[j] - 2 * dd[lca(i, j)];
}

bool anc(int a, int b) {
	return st[a] <= st[b] && en[a] >= en[b];
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	int ans = 0;
	for (int i = 0, a, b, c; i < m; ++i) {
		cin >> a >> b >> c;
		if (c == 0) // tree
			adj[a].pb(b), adj[b].pb(a);
		else
			ans += c, nontree.pb({a, b, c});
	}
	dfs(1, 0);
	for (const array<int, 3> &x : nontree) {
		int p = lca(x[0], x[1]);
		if (!(dist(x[0], x[1]) & 1))
			todo.pb({p, x[0], x[1], x[2]});
	}
	sort(all(todo), [&](const auto& i, const auto& j) {
		return en[i[0]] < en[j[0]]; 
	});
	for(array<int, 4> x : todo) {
		int sum = x[3], p21 = 0, p22 = 0;
		// cout << x[0] << '\n';
		while (x[1] != x[0]) {
			sum += dp[x[1]][p21];
			int p = up[x[1]][0]; p21 = -1;
			for (int i = 0; i < sz(adj[p]); ++i)
				if (anc(p, x[1]))
					p21 = 1 << i;
			assert(p21 != -1);
			x[1] = p;
		}
		while (x[2] != x[0]) {
			sum += dp[x[2]][p22];
			int p = up[x[2]][0]; p22 = -1;
			for (int i = 0; i < sz(adj[p]); ++i)
				if (anc(p, x[2]))
					p22 = 1 << i;
			assert(p22 != -1);
			x[2] = p;
		}
		for (int i = 0; i < 1 << sz(adj[x[0]]); ++i)
			if (!(i & p21 || i & p22)){
				// cout << "ckmax(" << sum + dp[x[0]][i | p21 | p22] << endl;
				dp[x[0]][i] = max(dp[x[0]][i], sum + dp[x[0]][i | p21 | p22]);
			}
	}
	int maxadd = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j < 1 << sz(adj[i]); ++j)
			maxadd = max(maxadd, dp[i][j]);
	ans -= maxadd;
	cout << ans << '\n';
}

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