Submission #1096322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096322		vjudge1	The Xana coup (BOI21_xanadu)	C++17	0 / 100	1065 ms	4440 KiB

xanadu

#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
const int N=1e5+10;
bitset<N>rec;
int cnt,hd[N],to[N<<1],nxt[N<<1];
void add(int u,int v){
	++cnt;
	to[cnt]=v;
	nxt[cnt]=hd[u];
	hd[u]=cnt;
}
int tt,n;bool ju;
bitset<N>used;
void dfs(int fl){
	if(fl>tt){
		ju=1;
		for(int i=1;i<=n;++i){
			if(rec[i]==1){
				ju=0;
				break;
			}
		}
		return;
	}
	if(ju)return;
	++fl;
	for(int i=1;i<=n;++i){
		if(used[i])continue;
		used[i]=1;
		for(int j=hd[i];j;j=nxt[j]){
			rec[to[j]]=!rec[to[j]];
		}
		dfs(fl);
		used[i]=0;
		for(int j=hd[i];j;j=nxt[j]){
			rec[to[j]]=!rec[to[j]];
		}
	}
}
int main(){
	int u,v,o;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)add(i,i);
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&o);
		rec[i]=(o!=0);
	}
	for(int i=1;i<=n;++i){
		tt=i;
		dfs(1);
		if(ju){
			printf("%d",i);
			return 0;
		}
	}
	printf("impossible");
}

Compilation message (stderr)

xanadu.cpp: In function 'int main()':
xanadu.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
xanadu.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~
xanadu.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d",&o);
      |   ~~~~~^~~~~~~~~

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