Submission #429590

#	Time	Username	Problem	Language	Result	Execution time	Memory
429590		keta_tsimakuridze	The Xana coup (BOI21_xanadu)	C++14	100 / 100	183 ms	29240 KiB

xanadu

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7,Inf=1e8;
int t,dp[N][2][2],n,s[N];
vector<int> V[N];
vector<pair<int,int> > v,v2;
void dfs(int u,int par){
	for(int k=0;k<2;k++) {
		for(int j=0;j<2;j++) {
			dp[u][k][j] = Inf;
		}
	} 
	vector<pair<int,int> > v,v2;
	int sum = 0,sum2 = 0,p = 0, p2 = 0;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i] == par) continue;
		dfs(V[u][i],u);// cout<<u<<"--->"<<V[u][i]<<endl;
		v.push_back( {dp[V[u][i]][1][1] - dp[V[u][i]][1][0],dp[V[u][i]][1][0]});
		v2.push_back({dp[V[u][i]][0][1] - dp[V[u][i]][0][0],dp[V[u][i]][0][0]});
		sum += dp[V[u][i]][1][0]; sum2+= dp[V[u][i]][0][0];
	}
	sort(v.begin(),v.end());
	sort(v2.begin(),v2.end());
		dp[u][1-s[u]][1] = sum2 + 1;
		dp[u][s[u]][0] = sum;
	
 //cout<<u<<" "<<sum<<" "<<sum2<<" "<<v.size()<<" "<<dp[u][0][0]<<endl;
	for(int j=0;j<v.size();j++) {
		p += v[j].f;p2 += v2[j].f;
		if(j%2==1)dp[u][s[u]][0] = min(dp[u][s[u]][0],sum+ p);
		else dp[u][1^s[u]][0] = min(dp[u][1^s[u]][0],sum + p);
	//	 if(u==4) cout<<sum2<<"__"<<p2<<endl;
		if(j%2==1)dp[u][1^s[u]][1] = min(dp[u][1^s[u]][1],sum2 + p2 + 1);
		else dp[u][s[u]][1] = min(dp[u][s[u]][1],sum2 + p2 + 1);
		
	}
	//cout<<dp[u][1][1]<<endl;
	if(par && V[u].size()==1) {
		dp[u][s[u]][0] = 0;
		dp[u][1-s[u]][1] = 1;
	}
	//cout<<u<<"___"<<dp[u][1][0] << " "<<dp[u][1][1] << " "<<dp[u][0][0] <<" "<<dp[u][0][1]<<endl;
}
main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		int u,v;
		cin>>u>>v;
		V[u].push_back(v);
		V[v].push_back(u);
	} 	
	for(int i=1;i<=n;i++) cin>>s[i],s[i]=1-s[i];
	dfs(1,0);
	if(min(dp[1][1][1],dp[1][1][0]) >= Inf) cout<<"impossible";
	else cout<<min(dp[1][1][1],dp[1][1][0]) ;
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(long long int, long long int)':
xanadu.cpp:18:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
xanadu.cpp:31:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int j=0;j<v.size();j++) {
      |              ~^~~~~~~~~
xanadu.cpp: At global scope:
xanadu.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      | ^~~~

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