Submission #1096327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096327		vjudge1	The Xana coup (BOI21_xanadu)	C++11	0 / 100	1 ms	348 KiB

xanadu

#include<bits/stdc++.h>
#define int ll
#define lc (rt<<1)
#define rc (rt<<1)
#define mid (l+r>>1)
#define rg register
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define DEBUG printf("Debug on line %d\n", __LINE__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 50;
const int INF = 0x3f3f3f3f;

inline int read(){
	int n=0, f=1; char ch = getchar();
	for(; !isdigit(ch); ch=getchar()) if(ch == '-') f=-1;
	for(; isdigit(ch); ch=getchar()) n=n*10+ch-'0';
	return n*f;
}

int n, ans=INF;
bitset<N> a[N], s, ze;
unordered_map<bitset<N>, int> mp;

void dfs1(bitset<N> cur, int step, int i){
	if(!mp.count(cur)) mp[cur] = step;
	else mp[cur] = min(mp[cur], step);
//	cout << step << ' ' << cur << endl;
	for(; i<=(n>>1); i++){
		dfs1(cur^a[i], step+1, i+1);
	}
}

void dfs2(bitset<N> cur, int step, int i){
//	cout << 2 << ' ' << cur << endl;
	if(mp.count(cur)){
		ans = min(ans, mp[cur]+step);
//		cout << cur << endl;
//		printf("%lld %lld\n", mp[cur], step);
	}
	for(; i<=n; i++){
		dfs2(cur^a[i], step+1, i+1);
	}
}

signed main(){
	n = read();
	for(int i=1; i<n; i++){
		int u = read(), v = read();
		a[u] |= (1<<(v-1));
		a[v] |= (1<<(u-1));
	}
	
	for(int i=1; i<=n; i++){
		a[i] |= (1<<(i-1));
//		cout << a[i] << endl;
	}
	
	for(int i=0; i<n; i++){
		s |= (read() << i);
	}
	
	dfs1(s, 0, 1);
	dfs2(ze, 0, (n>>1)+1);
	
	printf("%lld\n", ans);
}

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