Submission #1096321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096321		vjudge1	The Xana coup (BOI21_xanadu)	C++14	100 / 100	41 ms	24672 KiB

xanadu

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cstdlib>
#define int long long
using namespace std;
const int N=114514;
const int inf=0x3f3f3f3f;
int n,m,s,l,v[N<<1],first[N],nxt[N<<1],fa[N],tpedge,op[N],f[N][2][2];
vector<int>son[N];
void add(int a,int b)
{
	tpedge++;
	v[tpedge]=b;
	nxt[tpedge]=first[a];
	first[a]=tpedge;
}
void pre(int x)
{
	int i;
	for(i=first[x];i;i=nxt[i])
	{
		int y=v[i];
		if(y==fa[x])
			continue;
		fa[y]=x;
		son[x].push_back(y);
		pre(y);
	}
}
/*
i   id
0/1 not do / do
0/1 val= 0 / 1
*/
inline void solve(int x)
{
	int i;
	if(son[x].empty())
	{
		f[x][0][op[x]]=0;
		f[x][1][op[x]^1]=1;
		f[x][0][op[x]^1]=inf;
		f[x][1][op[x]]=inf;
		return ;
	}
	for(auto y:son[x])
		solve(y);
	int mi[2];
//	for(i=0;i<=1;i++)
//	{
//		mi[op[x]^i]=0;
//		mi[op[x]^i^1]=inf;
		mi[0]=0;
		mi[1]=inf;
		for(auto y:son[x])
		{
			int a=f[y][0][0],b=f[y][1][0];
			int u=mi[0],v=mi[1];
			mi[0]=min(u+a,v+b);
			mi[1]=min(v+a,u+b);
			//f[0/1][0];
		}
		f[x][0][0]=mi[op[x]];
		f[x][0][1]=mi[op[x]^1];
//	}

//	for(i=0;i<=1;i++)
//	{
		mi[0]=0;
		mi[1]=inf;
		for(auto y:son[x])
		{
			int a=f[y][0][1],b=f[y][1][1];
			int u=mi[0],v=mi[1];
			mi[0]=min(u+a,v+b);
			mi[1]=min(v+a,u+b);
		}
		f[x][1][0]=mi[op[x]^1]+1;
		f[x][1][1]=mi[op[x]]+1;
//	}
//	cout<<x<<" "<<f[x][0][0]<<" "<<f[x][0][1]<<" "<<f[x][1][0]<<" "<<f[x][1][1]<<endl;
}
signed main()
{
//	freopen("qwq.in","r",stdin);
//	freopen("ans.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&op[i]);
	}
	pre(1);
	solve(1);
	int ans=min(f[1][0][0],f[1][1][0]);
	if(ans>=inf)
		puts("impossible");
	else
		printf("%lld",min(f[1][0][0],f[1][1][0]));
}

Compilation message (stderr)

xanadu.cpp: In function 'void solve(long long int)':
xanadu.cpp:39:6: warning: unused variable 'i' [-Wunused-variable]
   39 |  int i;
      |      ^
xanadu.cpp: In function 'int main()':
xanadu.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%lld",&n);
      |  ~~~~~^~~~~~~~~~~
xanadu.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
xanadu.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf("%lld",&op[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

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