Submission #2544847

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define ri rd<int>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; --i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++i)
const int maxN = 1e5 + 7;
const int maxS = (1 << 15) + 3;

template<class T> T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; return f ? x : -x;
}

int n, m;
int a[maxN];
bool ok[maxS];
int f[maxS];

int main() {

	m = n = ri();
	For (i, 1, n) {
		int x = ri() + 1, y = ri() + 1, d = ri();
		a[x] ^= d;
		a[y] ^= d;
	}

	sort(a+1, a+n+1, greater<int>());
	int res = 0, mask = 0;
	for (; n > 0 && a[n] == 0; --n) ++res;
	while (n > 0) {
		for (; n >= 2 && a[n] == a[n-1]; n -= 2) ++res;
		if (n >= 1) mask |= 1 << (a[n--] - 1);
	}

	for (int s = mask; s; (--s) &= mask) {
		int tp = 0;
		rep (i, 1, 15) if (s >> (i-1) & 1) tp ^= i;
		ok[s] = tp == 0;
	}
	ok[0] = true;
	rep (s, 1, mask) if ((mask & s) == s && ok[s]){
		for (int t = s; t; (--t) &= s) if (ok[t] && ok[s^t]) {
			f[s] = max(f[s], f[s ^ t] + 1);
		}
	}
	res += f[mask];
	printf("%d\n", m - res);

	return 0;
}

Submission Info

Judge Result