Submission #1128497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128497		Alihan_8	The Xana coup (BOI21_xanadu)	C++20	0 / 100	1095 ms	6104 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

signed main(){
	int n; cin >> n;
	
	vector <vector<int>> adj(n);
	
	for ( int i = 1; i < n; i++ ){
		int u, v; cin >> u >> v;
		
		--u, --v;
		
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	i64 x = 0;
	
	for ( int i = 1; i <= n; i++ ){
		int b; cin >> b;
		
		x = x * 2 + b;
	}
	
	int k = n / 2;
	
	map <i64,int> mp; mp[0] = 0;
	
	for ( int mask = 0; mask < (1 << k); mask++ ){
		i64 y = 0;
		
		for ( int i = 0; i < k; i++ ){
			if ( mask >> i & 1 ){
				y ^= 1LL << i;
				
				for ( auto &v: adj[i] ) y ^= 1LL << v;
			}
		}
		
		int s = __builtin_popcount(mask);
		
		if ( !mp.count(y) || mp[y] > s ) mp[y] = s;
	}
	
	int opt = n + 1;
	
	for ( int mask = 0; mask < (1 << (n - k)); mask++ ){
		i64 y = 0;
		
		for ( int i = 0; i + k < n; i++ ){
			if ( mask >> i & 1 ){
				y ^= 1LL << (i + k);
				
				for ( auto &v: adj[i + k] ) y ^= 1LL << v;
			}
		}
		
		int s = __builtin_popcount(mask);
		
		if ( mp.count(y ^ x) ) opt = min(opt, mp[y ^ x] + s);
	}
	
	if ( opt == n + 1 ) return cout << "impossible\n", 0;
	
	cout << opt << '\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40
• Subtask 5: 0 / 30