Submission #507839

#	Time	Username	Problem	Language	Result	Execution time	Memory
507839		8e7	Training (IOI07_training)	C++17	100 / 100	34 ms	27484 KiB

training

//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 1005
#define maxc 10
#define maxm 5005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn], pnt[maxn], path[maxn];
pii ed[maxm], chi[maxm];
int w[maxm], pa[maxn], dep[maxn];
void dfs(int n, int par, int d) {
	dep[n] = d;
	pa[n] = par;
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n, d + 1);
		}
	}	
}
int ans = 0;
int tot, dp[maxn][maxm], id[maxn], best[maxn];
void solve(int n, int par) {
	int d = 0, sum = 0;
	for (int v:adj[n]) {
		if (v != par) {
			solve(v, n);
			sum += best[v];
			id[v] = d++;
		}
	}
	for (int i:pnt[n]) chi[i] = {0, 0};
	for (int v:adj[n]) {
		for (int j:path[v]) {
			if (!chi[j].ff) chi[j].ff = v;	
			else chi[j].ss = v;
		}
	}
	vector<int> bit(1<<d, sum);
	for (int i:pnt[n]) {
		auto [u, v] = chi[i];
		int se = 0, val = 0;
		if (u) se += 1<<id[u], val += dp[u][i] - best[u];
		if (v) se += 1<<id[v], val += dp[v][i] - best[v];
		//debug(i, chi[i].ff, chi[i].ss, se,val);
		for (int j = 0;j < (1<<d);j++) {
			if ((j & se) == 0) {
				bit[j | se] = max(bit[j | se], bit[j] + w[i] + val);
			}	
		}	
	}
	for (int i = 1;i < (1<<d);i++) {
		for (int j = 0;j < d;j++) {
			if (i & (1<<j)) bit[i] = max(bit[i], bit[i ^ (1<<j)]);
		}
	}
	ans = max(ans, bit[(1<<d) - 1]);
	best[n] = bit[(1<<d) - 1];
	for (int i = 1;i <= tot;i++) dp[n][i] = best[n];
	for (int v:adj[n]) {
		if (v == par) continue;
		for (int i:path[v]) {
			dp[n][i] = bit[(1<<d) - 1 - (1<<id[v])] - best[v] + dp[v][i];
		}
	}
	//debug(n, best[n]);
	//pary(bit.begin(), bit.end());
	//debug(n, dp[n][7]);
}	
int main() {
	io
	int n, m;
	cin >> n >> m;
	tot = m;
	int tc = 0;
	for (int i = 1;i <= m;i++) {
		int u, v;
		cin >> u >> v >> w[i];
		tc += w[i];
		if (w[i] == 0) {
			adj[u].push_back(v);
			adj[v].push_back(u);	
		} else {
			ed[i] = {u, v};
		}
	}
	dfs(1, 0, 0);
	int even = 0;
	for (int i = 1;i <= m;i++) {
		if (w[i]) {
			auto [u, v] = ed[i];
			if (dep[u] < dep[v]) swap(u, v);
			int len = 0;
			while (dep[u] > dep[v]) len++, path[u].push_back(i), u = pa[u];
			while (u != v) {
				path[u].push_back(i), path[v].push_back(i);
				len += 2;
				u = pa[u], v = pa[v];
			}
			if (len % 2 == 0) pnt[u].push_back(i);	
			else even += w[i], tc -= w[i];
		}
	}
	/*
	for (int i = 1;i <= n;i++) {
		debug("path", i);
		pary(path[i].begin(), path[i].end());
		debug("pnt");
		pary(pnt[i].begin(), pnt[i].end());
	}
	*/
	solve(1, 0);
	//debug(tc, even, ans);
	cout << tc - ans + even << endl;
}
/*
9 12
1 2 0
1 3 0
3 4 0
3 5 0
5 6 0
5 7 0
5 8 0
8 9 0
7 8 3
6 8 5
2 6 4
4 9 6

7 10
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
1 5 3
2 6 5
3 5 2
5 7 7
*/

• 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