Submission #1096320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096320		vjudge1	The Xana coup (BOI21_xanadu)	C++17	20 / 100	1062 ms	67924 KiB

xanadu

//#include<iostream>
//using namespace std;
//const int N=1e5+5;
//int n,ans=N*2,cnt;
//int a[N],head[N];
//struct node{
//	int to,next;
//}edge[N*2];
//void add(int u,int v){
//	edge[++cnt].to=v;
//	edge[cnt].next=head[u];
//	head[u]=cnt;
//}
//bool check(){
//	for(int i=1;i<=n;i++) if(a[i]) return false;
//	return true;
//}
//void dfs(int u,int sum){
//	if(check()) ans=min(ans,sum);
//	if(u>n) return;
//	for(int i=head[u];i;i=edge[i].next){
//		int v=edge[i].to;
//		a[v]=1-a[v];
//	}
//	a[u]=1-a[u];
//	dfs(u+1,sum+1);
//	for(int i=head[u];i;i=edge[i].next){
//		int v=edge[i].to;
//		a[v]=1-a[v];
//	}
//	a[u]=1-a[u];
//	dfs(u+1,sum);
//}
//int main(){
//	scanf("%d",&n);
//	for(int i=1;i<n;i++){
//		int u,v;
//		scanf("%d%d",&u,&v);
//		add(u,v);
//		add(v,u);
//	}
//	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
//	dfs(1,0);
//	if(ans==N*2) printf("impossible");
//	else printf("%d",ans);
//	return 0;
//}


#include<iostream>
#include<map>
#include<cstring>
using namespace std;
const int N=1e5+5;
int n,ans=N*2,cnt,mid;
int a[N],head[N],ch[N];
map<long long,int> mp;
struct node{
	int to,next;
}edge[N*2];
void add(int u,int v){
	edge[++cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
void dfs1(int u,int sum){
	if(u==mid+1){
		long long res=0;
		for(int i=1;i<=n;i++){
			res=(res<<1)+ch[i];
		}
		if(mp.count(res) ) mp[res]=min(mp[res],sum);
		else mp[res]=sum;
		return;
	}
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		ch[v]^=1;
	}
	ch[u]^=1;
	dfs1(u+1,sum+1);
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		ch[v]^=1;
	}
	ch[u]^=1;
	dfs1(u+1,sum);
}
void dfs2(int u,int sum){
	if(sum>ans) return;
	if(u==n+1){
		long long res=0;
		for(int i=1;i<=n;i++){
			res=(res<<1)+ch[i]^a[i];
		}
		if(mp.count(res) ) ans=min(ans,sum+mp[res]);
		return;
	}
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		ch[v]^=1;
	}
	ch[u]^=1;
	dfs2(u+1,sum+1);
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		ch[v]^=1;
	}
	ch[u]^=1;
	dfs2(u+1,sum);
}
int main(){
	scanf("%d",&n);
	mid=n/2;
	for(int i=1;i<n;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	dfs1(1,0);
	memset(ch,0,sizeof(ch));
	dfs2(mid+1,0);
	if(ans==N*2) printf("impossible");
	else printf("%d",ans);
	return 0;
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs2(int, int)':
xanadu.cpp:94:16: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   94 |    res=(res<<1)+ch[i]^a[i];
      |        ~~~~~~~~^~~~~~
xanadu.cpp: In function 'int main()':
xanadu.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
xanadu.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~
xanadu.cpp:121:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |  for(int i=1;i<=n;++i) scanf("%d",&a[i]);
      |                        ~~~~~^~~~~~~~~~~~

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