Submission #598754

#	Time	Username	Problem	Language	Result	Execution time	Memory
598754		Bobaa	Training (IOI07_training)	C++17	0 / 100	1093 ms	596 KiB

training

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

const int N = 1 << 10; 

vector<int> E[N], lca[N], dob; 
int id[N], d[N], par[N], pre[N], pst[N], wsk, dp[N][N], dp2[N][5 * N], n, m; 
vector<pair<int, pair<int, int>>> edg, edg2; 

void dfs1(int v, int p) {
	pre[v] = wsk++; 
	par[v] = p; 
	d[v] = d[p] + 1; 
	int sz = E[v].size(); 
	for (int i = 0; i < sz; i++) if (E[v][i] == p) swap(E[v][i], E[v].back()); 
	if (p != 0) E[v].pop_back(); 
	for (int i = 0; i < sz; i++) {
		id[E[v][i]] = i; 
		dfs1(E[v][i], v); 
	}
	pst[v] = wsk; 
}

void dfs2(int v) {
	for (int u : E[v]) {
		dfs2(u); 
		dp[v][1 << id[u]] = dp2[u][0]; 
	}
	for (int e : lca[v]) {
		int u = edg[e].second.first, w = edg[e].second.second; 
		while (par[w] != v) w = par[w]; 
		if (u == v) dp[v][1 << id[w]] = max(edg[e].first + dp2[w][e], dp[v][1 << id[w]]); 
		else {
			while (par[u] != v) u = par[u]; 
			dp[v][(1 << id[u]) + (1 << id[w])] = max(edg[e].first + dp2[u][e] + dp2[w][e], dp[v][(1 << id[u]) + (1 << id[w])]); 
		}
	}
	for (int i = 0; i < (1 << E[v].size()); i++) for (int j = i; ; j = (j - 1) & i) {
		dp[v][i] = max(dp[v][i], dp[v][j] + dp[v][i - j]); 
		if (j == 0) break; 
	}
	for (int e : dob) {
		if (edg[e].second.first == v && pre[edg[e].second.second] >= pst[v]) dp2[v][e] = dp[v][(1 << E[v].size()) - 1]; 
		if (edg[e].second.second == v) dp2[v][e] = dp[v][(1 << E[v].size()) - 1]; 
		if (par[edg2[e].second.first] == v ^ par[edg2[e].second.second] == v) {
			if (par[edg2[e].second.first] == v) {
				dp2[v][e] = dp[v][(1 << E[v].size()) - 1 - (1 << id[edg2[e].second.first])] + dp2[edg2[e].second.first][e]; 
				edg2[e].second.first = v; 
			}
			if (par[edg2[e].second.second] == v) {
				dp2[v][e] = dp[v][(1 << E[v].size()) - 1 - (1 << id[edg2[e].second.second])] + dp2[edg2[e].second.second][e]; 
				edg2[e].second.second = v; 
			}
		}
	}
	dp2[v][0] = dp[v][(1 << E[v].size()) - 1]; 
}

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	cin >> n >> m; 
	int sm = 0; 
	for (int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w; 
		sm += w; 
		edg.push_back({w, {u, v}}); 
		if (w == 0) {
			E[u].push_back(v); 
			E[v].push_back(u); 
		}
	}
	dfs1(1, 0); 
	sort(edg.begin(), edg.end()); 
	for (int i = n - 1; i < m; i++) {
		if (pre[edg[i].second.first] > pre[edg[i].second.second]) swap(edg[i].second.first, edg[i].second.second); 
		int u = edg[i].second.first, v = edg[i].second.second; 
		if ((d[u] & 1) != (d[v] & 1)) continue; 
		if (d[u] < d[v]) swap(u, v); 
		while (d[u] > d[v]) u = par[u]; 
		while (u != v) {
			u = par[u]; 
			v = par[v]; 
		}
		dob.push_back(i); 
		lca[u].push_back(i); 
	}
	edg2 = edg; 
	dfs2(1); 
	cout << sm - dp2[1][0]; 
}

Compilation message (stderr)

training.cpp: In function 'void dfs2(int)':
training.cpp:45:33: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   45 |   if (par[edg2[e].second.first] == v ^ par[edg2[e].second.second] == v) {
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

• 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