제출 #1323921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1323921		sporknives	The Xana coup (BOI21_xanadu)	C++20	5 / 100	1096 ms	5644 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;

vector<vector<int>> adj;
vector<bool> state;

signed main() {
	int n; cin>>n;
	
	adj.resize(n);
	state.resize(n);
	
	for(int i=0;i<n-1;i++) {
		int u,v; cin>>u>>v; u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=0;i<n;i++) {
		int x; cin>>x;
		if(x==1)state[i]=true;
		else state[i]=false;
	}
	
	int ans=INT_MAX;
	for(int i=0;i<(1<<n);i++) {
		vector<bool> s = state;
		int cnt=0;
		for(int j=0;j<n;j++) {
			if(i&(1<<j)) {
				s[j]=!s[j];
				for(int x: adj[j]) s[x]=!s[x];
				cnt++;
			}
		}
		
		bool all_off=true;
		for(bool x:s){
			if(x)all_off=false;
		}
		
		if(all_off) ans=min(ans,cnt);
	}
	if(ans==INT_MAX)cout<<"impossible";
	else cout<<ans;
    return 0;
}

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