oj.uz

Submission #756699

# Submission time Handle Problem Language Result Execution time Memory
756699 2023-06-12T05:38:49 Z SanguineChameleon Training (IOI07_training) C++17
100 / 100
 13 ms 4564 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 2 ms 944 KB Output is correct
3 Correct 5 ms 1604 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2132 KB Output is correct
2 Correct 9 ms 1492 KB Output is correct
3 Correct 4 ms 1520 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 848 KB Output is correct
2 Correct 3 ms 1616 KB Output is correct
3 Correct 13 ms 4564 KB Output is correct
4 Correct 4 ms 1748 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2132 KB Output is correct
2 Correct 13 ms 4564 KB Output is correct
3 Correct 7 ms 1748 KB Output is correct
4 Correct 8 ms 1492 KB Output is correct