Submission #410770

#	Time	Username	Problem	Language	Result	Execution time	Memory
410770		dongliu0426	Training (IOI07_training)	C++17	0 / 100	5 ms	460 KiB

training

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define f first
#define s second

const int N = 1000;
const int M = 10;

struct Road {
	int a, b, c, lca;
};

int n, m, deg[N], d[N], st[N], en[N], ti = 0, dp[N][M];
vector<int> adj[N];
pi pa[N];
vector<Road> roads;

void dfs(int i, int k) {
	st[i] = ++ti;
	for (int j : adj[i])
		if (j != k) {
			pa[j] = {i, 1 << deg[i]++};
			d[j] = d[i] ^ 1;
			dfs(j, i);
		}
	en[i] = ++ti;
}

bool anc(int i, int j) {
	return st[i] <= st[j] && en[i] >= en[j];
}

int lca(int i, int j) {
	while (!anc(i, j))
		i = pa[i].f;
	return i;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	
	cin >> n >> m;
	roads.rsz(m);
	int ans = 0;
	for (Road& x : roads) {
		cin >> x.a >> x.b >> x.c, --x.a, --x.b;
		ans += x.c;
		if (x.c == 0) {
			adj[x.a].pb(x.b);
			adj[x.b].pb(x.a);
		}
	}
	dfs(0, 0);
	for (Road& x : roads)
		x.lca = lca(x.a, x.b);
	sort(roads.begin(), roads.end(), [&](const Road &i, const Road &j) {
		return en[i.lca] < en[j.lca];
	});
	for (const Road& x : roads) {
		if (d[x.a] != d[x.b] || !x.c)
			continue;
		pi A, B; int sum = x.c;
		for (A = {x.a, 0}; A.f != x.lca; A = pa[A.f])
			sum += dp[A.f][A.s];
		for (B = {x.b, 0}; B.f != x.lca; B = pa[B.f])
			sum += dp[B.f][B.s];
		for (int i = (1 << deg[x.lca]) - 1; i >= 0; --i)
			if (!(i & A.s) && !(i & B.s))
				dp[x.lca][i] = max(dp[x.lca][i], dp[x.lca][i | A.s | B.s] + sum);
	}
	int maxrem = 0;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < 1 << deg[i]; ++j)
			maxrem = max(maxrem, dp[i][j]);
	ans -= maxrem;
	cout << ans << '\n';
}

• 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