Submission #565192

#	Time	Username	Problem	Language	Result	Execution time	Memory
565192		CSQ31	The Xana coup (BOI21_xanadu)	C++17	100 / 100	95 ms	23168 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+1;
vector<int>adj[MAXN];
typedef long long int ll;
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
ll dp[2][2][MAXN];
int a[MAXN];
//toggled , on/off
void print(int v){
	cout<<v<<'\n';
	cout<<"00 "<<dp[0][0][v]<<'\n';
	cout<<"01 "<<dp[0][1][v]<<'\n';
	cout<<"10 "<<dp[1][0][v]<<'\n';
	cout<<"11 "<<dp[1][1][v]<<'\n';
}
void dfs(int v,int u){
	if((int)(adj[v].size()) == 1 && v>1){
		dp[0][a[v]][v] = 0;
		dp[1][a[v]^1][v] = 1;
		//print(v);
		return;
	}
	vector<ll>d;
	ll tot = 0; //all children must be off
	for(int x:adj[v]){
		if(x==u)continue;
		dfs(x,v);	
		tot+=dp[0][0][x];
		d.push_back(dp[1][0][x] - dp[0][0][x]); 
	}
	sort(d.begin(),d.end());
	ll sum = 0;
	int m = d.size();
	for(int i=0;i<=m;i++){
		if(i)sum+=d[i-1];
		if((i%2) == a[v])dp[0][0][v] = min(dp[0][0][v],tot+sum); //toggle parity a[i] times
		else dp[0][1][v] = min(dp[0][1][v],tot+sum);
	}
	/////
	tot = 0;
	d.clear();
	//all children has to be on
	for(int x:adj[v]){
		if(x==u)continue;
		tot+=dp[0][1][x];
		d.push_back(dp[1][1][x] - dp[0][1][x]); 
	}
	sort(d.begin(),d.end());
	sum = 0;
	m = d.size();
	for(int i=0;i<=m;i++){
		if(i)sum+=d[i-1];
		if((i%2) != a[v])dp[1][0][v] = min(dp[1][0][v],tot+sum+1);
		else dp[1][1][v] = min(dp[1][1][v],tot+sum+1);
	}
	for(int i=0;i<4;i++)dp[i&1][i>>1][v] = min(dp[i&1][i>>1][v],(ll)(1e9));
	//print(v);
}
int main()
{
	owo
	int n;
	cin>>n;
	for(int i=1;i<n;i++){
		int v,u;
		cin>>v>>u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[0][0][i] = dp[0][1][i] = dp[1][0][i] = dp[1][1][i] = 1e9;
	}
	dfs(1,0);
	ll ans = min(dp[1][0][1],dp[0][0][1]);
	if(ans==1e9)cout<<"impossible"<<'\n';
	else cout<<ans<<'\n';
}

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