Submission #410791

#	Time	Username	Problem	Language	Result	Execution time	Memory
410791		dongliu0426	Training (IOI07_training)	C++17	100 / 100	19 ms	4428 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][1 << 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] = mp(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) {
	if (d[i] > d[j])
		swap(i, 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 (x.c && (d[x.a] & 1) != (d[x.b] & 1))
			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 = 0; i < 1 << deg[x.lca]; ++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);
	}
	cout << (ans -= dp[0][0]) << '\n';
}

• 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