Submission #429588

#	Time	Username	Problem	Language	Result	Execution time	Memory
429588		mosiashvililuka	The Xana coup (BOI21_xanadu)	C++14	100 / 100	109 ms	18756 KiB

xanadu

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,zx,xc,dp[100009][2][2],f[100009];
vector <int> v[100009];
void dfs(int q, int w){
	int qw[2],we[2];
	int i,j,ii,jj;
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		dfs((*it),q);
	}
	
	for(i=0; i<2; i++){
		for(j=0; j<2; j++){
			/*for(ii=0; ii<=1; ii++){
				qw[ii]=we[ii]=0;
			}*/
			qw[0]=0;qw[1]=a+2;
			jj=i;
			for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
				if((*it)==w) continue;
				we[0]=min(qw[0]+dp[(*it)][0][jj],qw[1]+dp[(*it)][1][jj]);
				we[1]=min(qw[1]+dp[(*it)][0][jj],qw[0]+dp[(*it)][1][jj]);
				qw[0]=we[0];qw[1]=we[1];
			}
			dp[q][i][j]=qw[((f[q]^i)^j)]+i;
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int i,j,ii,jj;
	cin>>a;
	for(i=1; i<a; i++){
		cin>>c>>d;
		v[c].push_back(d);
		v[d].push_back(c);
	}
	for(i=1; i<=a; i++) cin>>f[i];
	dfs(1,0);
	/*for(ii=1; ii<=a; ii++){
		cout<<dp[ii][0][0]<<" "<<dp[ii][0][1]<<" "<<dp[ii][1][0]<<" "<<dp[ii][1][1]<<endl;
	}*/
	zx=min(dp[1][0][0],dp[1][1][0]);
	if(zx>a){
		cout<<"impossible";
	}else{
		cout<<zx;
	}
	return 0;
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(int, int)':
xanadu.cpp:7:10: warning: unused variable 'ii' [-Wunused-variable]
    7 |  int i,j,ii,jj;
      |          ^~
xanadu.cpp: In function 'int main()':
xanadu.cpp:32:8: warning: unused variable 'j' [-Wunused-variable]
   32 |  int i,j,ii,jj;
      |        ^
xanadu.cpp:32:10: warning: unused variable 'ii' [-Wunused-variable]
   32 |  int i,j,ii,jj;
      |          ^~
xanadu.cpp:32:13: warning: unused variable 'jj' [-Wunused-variable]
   32 |  int i,j,ii,jj;
      |             ^~

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