Submission #756699

#	Time	Username	Problem	Language	Result	Execution time	Memory
756699		SanguineChameleon	Training (IOI07_training)	C++17	100 / 100	13 ms	4564 KiB

training

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct path {
	int u, v, w, sum, mask;
};

const int maxn = 1e3 + 20;
const int maxm = 5e3 + 20;
vector<int> adj[maxn];
int depth[maxn];
int cnt[maxn];
vector<int> ch[maxn];
pair<int, int> par[maxn];
int dp[maxn][1024];
vector<int> path_ids[maxn];
path paths[maxm];

void dfs1(int u) {
	for (auto v: adj[u]) {
		if (v != par[u].first) {
			ch[u].push_back(v);
			depth[v] = depth[u] + 1;
			par[v] = make_pair(u, cnt[u]++);
			dfs1(v);
		}
	}
}

int lca(int u, int v) {
	if (depth[u] < depth[v]) {
		swap(u, v);
	}
	while (depth[u] != depth[v]) {
		u = par[u].first;
	}
	while (u != v) {
		u = par[u].first;
		v = par[v].first;
	}
	return u;
}

void dfs2(int u) {
	for (auto v: ch[u]) {
		dfs2(v);
	}
	for (auto id: path_ids[u]) {
		int x = paths[id].u;
		int y = paths[id].v;
		paths[id].sum = paths[id].w;
		paths[id].mask = 0;
		for (int iter = 0; iter < 2; iter++) {
			if (x != u) {
				paths[id].sum += dp[x][(1 << cnt[x]) - 1];
				int p, pos;
				while ((pos = par[x].second, p = par[x].first) != u) {
					paths[id].sum += dp[p][((1 << cnt[p]) - 1) ^ (1 << pos)];
					x = p;
				}
				paths[id].mask ^= (1 << pos);
			}
			swap(x, y);
		}
	}
	for (int mask = 0; mask < (1 << cnt[u]); mask++) {
		for (int i = 0; i < cnt[u]; i++) {
			if ((mask >> i) & 1) {
				int v = ch[u][i];
				dp[u][mask] = max(dp[u][mask], dp[u][mask ^ (1 << i)] + dp[v][(1 << cnt[v]) - 1]);
			}
		}
		for (auto id: path_ids[u]) {
			int sub = paths[id].mask;
			int sum = paths[id].sum;
			if ((mask & sub) == sub) {
				dp[u][mask] = max(dp[u][mask], dp[u][mask ^ sub] + sum);
			}
		}
	}
}

void just_do_it() {
	int n, m;
	cin >> n >> m;
	int res = 0;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		paths[i].u = u;
		paths[i].v = v;
		paths[i].w = w;
		if (!w) {
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		res += w;
	}
	par[1] = make_pair(-1, -1);
	dfs1(1);
	for (int i = 1; i <= m; i++) {
		int u = paths[i].u;
		int v = paths[i].v;
		int w = paths[i].w;
		if (w && (depth[u] + depth[v]) % 2 == 0) {
			path_ids[lca(u, v)].push_back(i);
		}
	}
	dfs2(1);
	res -= dp[1][(1 << cnt[1]) - 1];
	cout << res;
}

• 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