Submission #1124132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124132		RSAMSD	The Xana coup (BOI21_xanadu)	C++20	100 / 100	48 ms	16968 KiB

xanadu

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
int t = 0;
int const f =1e5 + 10;
long long mod = 1e9 + 7;//998244353;
long long dp[f];
long long dp1[f];
long long dp2[f];
long long dp3[f];
// long long par1[f];
// long long par2[f];
long long a[f];
// long long adj[f];
// long long mmn =0;
// long long C[4];
// pair<long long, long long> dd[f];
// long long prefix[f];
vector<int>g[f];
vector<pair<long long,long long>>gr;
struct node {
	long long val = 0;
	long long lazy = 0;
	long long prefix =0;
	long long suffix =0;
	long long all =0;
};
// struct trpel {
	// long long v, u, bank = 0;
// };
node segtree[f *4];
bool B[f];
void redany() {
	ifstream fin;
	ofstream fout;
	fin.open("std.in");
	fout.open("std.out");
}
long long powmod(long long a, long long p, long long modd) {
	long long ans = 1;
	while (p > 0) {
		if (p % 2 == 1) {
			ans *= a;
			ans %= modd;
			p--;
		}
		if (p == 0)break;
		a *= a;
		a %= modd;
		p /= 2;
	}
	return ans;
}
void dolazy(int v){
	long long k = segtree[v].lazy;
	segtree[v].lazy = 0;
	segtree[2*v].lazy+=k;
	segtree[2*v+1].lazy +=k;
	segtree[2*v].val+=k;
	segtree[2*v+1].val+=k;
}
void upd(int v, int tl, int tr, int l ,int r, int val){
	if(tr<l||tl>r)return;
	if(tr<=r&&tl>=l){
		segtree[v].val+=val;
		segtree[v].lazy+=val;
		return;
	}
	dolazy(v);
	int mid = (tl+tr)/2;
	upd(2*v,tl,mid,l,r,val);
	upd(2*v+1,mid+1,tr,l,r,val);
	segtree[v].val = max(segtree[2*v].val,segtree[2*v+1].val);
}
long long q(int v, int tl , int tr,int l , int x){
	if(tr<l||segtree[v].val<x)return 1e18;
	if(tr==tl)return tr;
	int mid  = (tr+tl)/2;
	dolazy(v);
	if(tl>=l&&segtree[v].val>=x){
		if(segtree[v*2].val>=x){
			return q(2*v,tl,mid,l,x);
		}
		return q(2*v+1,mid+1,tr,l,x);
	}
	return min(q(2*v,tl,mid,l,x),q(2*v+1,mid+1,tr,l,x));
}
void dfs(int v, int parv){
	for(int u:g[v]){
		if(u==parv)continue;
		dfs(u,v);
	}
	if(g[v].size()==1&&parv!=0){
		if(B[v]){
			dp2[v] = 1e18;
			dp1[v] = 1e18;
			dp[v] = 1;
			dp3[v] = 0;
		}
		else{
			dp[v] = dp3[v] = 1e18;
			dp1[v] = 1;
			dp2[v] =0;
		}
		//cout<<v<<" : "<<dp[v]<<" "<<dp1[v]<<" "<<dp2[v]<<" "<<dp3[v]<<'\n';
		return;
	}
	long long a =0, b=0;
	// dp me yes off
	//dp1 me yes on 
	// dp2 me no off
	// dp3 me no on
	bool c=0;
	dp[v] = 1;
	for(int u:g[v]){
		if(u==parv)continue;
		if(min(dp1[u],dp3[u])==1e18){
			c=1;
			//cout<<v<<'\n';
			dp[v] = 1e18;break;
		}
		dp[v]+=min(dp1[u],dp3[u]);
		if(dp1[u]<dp3[u]){
			a++;
		}
		else{
			b++;
		}
	}
	if((a+1+B[v])%2==1&&!c){
		a = b =1e18;
		for(int u:g[v]){
			if(u==parv)continue;
			if(dp1[u]<dp3[u]){
				if(dp3[u]!=1e18){
					a = min(a,dp3[u]-dp1[u]);
				}
			}
			else{
				if(dp1[u]!=1e18){
					a = min(a,dp1[u]-dp3[u]);
				}
			}
		}
		if(a==1e18){
			dp[v] = 1e18;
		}
		else{
			dp[v]+=a;
		}
	}
	dp1[v] =1;
	a =0;
	c=0;
	for(int u:g[v]){
		if(u==parv)continue;
		if(min(dp1[u],dp3[u])==1e18){
			c=1;
			dp1[v] = 1e18;break;
		}
		dp1[v]+=min(dp1[u],dp3[u]);
		if(dp1[u]<dp3[u]){
			a++;
		}
		else{
			b++;
		}
	}
	if((a+1+B[v])%2==0&&!c){
		a = b =1e18;
		for(int u:g[v]){
			if(u==parv)continue;
			if(dp1[u]<dp3[u]){
				if(dp3[u]!=1e18){
					a = min(a,dp3[u]-dp1[u]);
				}
			}
			else{
				if(dp1[u]!=1e18){
					a = min(a,dp1[u]-dp3[u]);
				}
			}
		}
		if(a==1e18){
			dp1[v] = 1e18;
		}
		else{
			dp1[v]+=a;
		}
	}
	dp2[v] =0;
	a=0;
	c=0;
	for(int u:g[v]){
		if(u==parv)continue;
		if(min(dp[u],dp2[u])==1e18){
			c=1;
			dp2[v] = 1e18;break;
		}
		dp2[v]+=min(dp[u],dp2[u]);
		if(dp[u]<dp2[u]){
			a++;
		}
		else{
			b++;
		}
	}
	if((a+B[v])%2==1&&!c){
		a = b =1e18;
		for(int u:g[v]){
			if(u==parv)continue;
			if(dp[u]<dp2[u]){
				if(dp2[u]!=1e18){
					a = min(a,dp2[u]-dp[u]);
				}
			}
			else{
				if(dp[u]!=1e18){
					a = min(a,dp[u]-dp2[u]);
				}
			}
		}
		if(a==1e18){
			dp2[v] = 1e18;
		}
		else{
			dp2[v]+=a;
		}
	}
	dp3[v] = 0;
	a=0;
	c=0;
	for(int u:g[v]){
		if(u==parv)continue;
		if(min(dp[u],dp2[u])==1e18){
			c=1;
			dp3[v] = 1e18;break;
		}
		dp3[v]+=min(dp[u],dp2[u]);
		if(dp[u]<dp2[u]){
			a++;
		}
		else{
			b++;
		}
	}
	if((a+B[v])%2==0&&!c){
		a = b =1e18;
		for(int u:g[v]){
			if(u==parv)continue;
			if(dp[u]<dp2[u]){
				if(dp2[u]!=1e18){
					a = min(a,dp2[u]-dp[u]);
				}
			}
			else{
				if(dp[u]!=1e18){
					a = min(a,dp[u]-dp2[u]);
				}
			}
		}
		if(a==1e18){
			dp3[v] = 1e18;
		}
		else{
			dp3[v]+=a;
		}
	}
	//cout<<v<<" : "<<dp[v]<<" "<<dp1[v]<<" "<<dp2[v]<<" "<<dp3[v]<<'\n';
}
long long tw = powmod(2, mod - 2, mod);
int main() {
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	t = 1;
	//cin >> t;
	for (int hhh = 1;hhh <= t;hhh++) {
		long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 1, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
		string s1;
		string s3;
		char s2;
		long double dec = 0;
		bool c = 1;
		bool allrows =0;
		bool allculms =0;
		pair<long long,long long> aa;
		priority_queue<pair<long long, long long>> qq;
		multiset<long long> mul;
		multiset<long long> mul2;
		set<long long>st;
		queue<long long> pp;
		map<long long, long long> conv;
		map<long long,long long> convback;
		vector<long long> vec;
		cin >>n;
		for(int i =0;i<n-1;i++){
			cin>>r>>l;
			g[r].push_back(l);
			g[l].push_back(r);
		}
		for(int i =1;i<=n;i++){
			cin>>B[i];
		}
		dfs(1,0);
		if(min(dp[1],dp2[1])==1e18)
			cout<<"impossible";
		else cout<<min(dp[1],dp2[1]);
		// m = 1e12;
		// cout<<m%mod;
	}
}
//kir

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