Submission #543030

#	Time	Username	Problem	Language	Result	Execution time	Memory
543030		sidon	Training (IOI07_training)	C++17	100 / 100	60 ms	4556 KiB

training

#include <bits/stdc++.h>
using namespace std;
#define maxim(X, Y) (X = max(X, Y))

const int MXN = 1e3, Z = 5e3;

int N, M, A[Z], B[Z], C[Z], p[MXN], d[MXN];
int cd[Z];
vector<int> g[MXN], h[MXN];

void init(int u) {
	for(const int &v : g[u]) {
		for(int &w : g[v]) if(u == w) swap(w, g[v].back());
		g[v].pop_back();
		p[v] = u;
		d[v] = d[u] + 1;
		init(v);
	}
}

int lca(int u, int v) {
	for(; u != v; d[u] > d[v] ? u = p[u] : v = p[v]);
	return u;
}

int getIdx(int u, int v) {
	for(int i = 0; 1; ++i) if(g[u][i] == v) return i;
}

const int NB = 1023;
int dp[MXN][1<<10];

void dfs(int u) {
	for(const int &v : g[u]) if(v != p[u]) dfs(v);
	for(const int &i : h[u]) {
		int cur {};
		for(int v : {A[i], B[i]}) if(u != v) {
			cur += dp[v][NB];
			int w = v; v = p[v];
			for(; u != v; w = v, v = p[v])
				cur += dp[v][NB^(1<<getIdx(v, w))];
			cd[i] ^= 1<<getIdx(u, w);
		}
		maxim(dp[u][cd[i]], cur + C[i]);
	}

	for(int i = 1; i <= NB; ++i) {
		for(int j = 0; j < 10; ++j) if(i & (1<<j))
			maxim(dp[u][i], dp[u][i ^ (1<<j)] + (j < int(size(g[u])) ? dp[g[u][j]][NB] : 0));

		for(const int &j : h[u]) if((i & cd[j]) == cd[j])
			maxim(dp[u][i], dp[u][i ^ cd[j]] + dp[u][cd[j]]);
	}
}

int main() {
	cin >> N >> M;
	for(int i = 0; i < M; ++i) {
		cin >> A[i] >> B[i] >> C[i];
		--A[i], --B[i];
		if(!C[i]) {
			g[A[i]].push_back(B[i]);
			g[B[i]].push_back(A[i]);
		}
	}
	init(0);

	for(int i = 0; i < M; ++i) if(C[i]) {
		if(!((d[A[i]] ^ d[B[i]]) & 1))
			h[lca(A[i], B[i])].push_back(i);
	}

	dfs(0);

	cout << accumulate(C, C + M, 0) - dp[0][NB];
}

• 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