Submission #1097758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097758		vjudge1	The Xana coup (BOI21_xanadu)	C++17	100 / 100	34 ms	17812 KiB

xanadu

#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
const int N=1e5+10,inf=0x3f3f3f3f;
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;
}
bitset<N>aa,used;
int f[N][2][2],g[N][2][2];
void dfs(int p){
	bool ju=1;
	int pre=0;
	used[p]=1;
	for(int i=hd[p];i;i=nxt[i]){
		if(used[to[i]])continue;
		ju=0;
		dfs(to[i]);
		g[to[i]][0][0]=min(min(g[pre][0][0]+f[to[i]][0][0],inf),min(g[pre][0][1]+f[to[i]][1][0],inf));
		g[to[i]][0][1]=min(min(g[pre][0][1]+f[to[i]][0][0],inf),min(g[pre][0][0]+f[to[i]][1][0],inf));
		g[to[i]][1][0]=min(min(g[pre][1][0]+f[to[i]][0][1],inf),min(g[pre][1][1]+f[to[i]][1][1],inf));
		g[to[i]][1][1]=min(min(g[pre][1][1]+f[to[i]][0][1],inf),min(g[pre][1][0]+f[to[i]][1][1],inf));
		pre=to[i];
	}
	if(ju){
		f[p][0][0]=(aa[p]?inf:0);
		f[p][0][1]=(aa[p]?0:inf);
		f[p][1][0]=(aa[p]?1:inf);
		f[p][1][1]=(aa[p]?inf:1);
	}else{
		f[p][0][0]=(aa[p]?g[pre][0][1]:g[pre][0][0]);
		f[p][0][1]=(aa[p]?g[pre][0][0]:g[pre][0][1]);
		f[p][1][0]=(aa[p]?min(g[pre][1][0]+1,inf):min(g[pre][1][1]+1,inf));
		f[p][1][1]=(aa[p]?min(g[pre][1][1]+1,inf):min(g[pre][1][0]+1,inf));
	}
}
int main(){
	int n,u,v;
	scanf("%d",&n);
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	int oo;
	for(int i=1;i<=n;++i){
		scanf("%d",&oo);
		aa[i]=(oo!=0);
	}
	g[0][0][1]=inf,g[0][1][1]=inf;
	dfs(1);
	if(f[1][0][0]>=inf&&f[1][1][0]>=inf){
		printf("impossible");
	}else{
		printf("%d",min(f[1][0][0],f[1][1][0]));
	}
}

Compilation message (stderr)

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

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