Submission #488127

#	Time	Username	Problem	Language	Result	Execution time	Memory
488127		inksamurai	Svjetlo (COCI20_svjetlo)	C++17	0 / 110	506 ms	97540 KiB

svjetlo

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3HaBFkZ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;

int main(){
_3HaBFkZ;
	int n; cin>>n;
	string s; cin>>s;
	vi a; 
	for(auto ch : s) a.pb(ch-'0');
	vec(vi) adj(n);
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		u--,v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	vi contains;
	auto dfs=[&](auto self,int v,int par)->bool{
		bool pokita=!a[v];
		for(auto u : adj[v]){
			if(u!=par){
				bool now=self(self,u,v);
				pokita=pokita or now;
			}
		}
		return contains[v]=pokita;
	};
	vec(vi) fdp;
	auto fdfs=[&](auto self,int v,int par)->void{
		int chsv=0;
		for(auto u : adj[v]){
			if(u!=par and contains[u]){
				self(self,u,v);
				chsv++;
			}
		}
		int state=a[v];
		state^=((chsv+1)%2);
		int _sum=0;
		for(auto u : adj[v]){
			if(u!=par and contains[u]){
				_sum+=min(fdp[u][0]+4,fdp[u][1]+2);
			}
		}
		fdp[v][state]=_sum;
	};
	vec(vi) gdp;
	auto gdfs=[&](auto self,int v,int par)->void{
		int chsv=0;
		for(auto u : adj[v]){
			if(u!=par and contains[v]){
				self(self,u,v);
				chsv++;
			}
		}
		gdp[v][0]=fdp[v][1];
		gdp[v][1]=fdp[v][1];
		vi candies;
		for(auto u : adj[v]){
			if(u!=par and contains[v]){
				candies.pb(u);
			}
		}
		for(auto u : candies){
			int _sum=gdp[u][1]+1;
			int state=a[v];
			for(auto u1 : candies){
				if(u==u1) continue;
				_sum+=min(fdp[u][0]+3,gdp[u][0]+2);
			}
			state^=(chsv%2);
			// if(v==1) cout<<_sum<<"\n";
			if(state==0){
				gdp[v][1]=min(gdp[v][1],_sum+3);
			}else{
				gdp[v][1]=min(gdp[v][1],_sum);
			}
		}
	};
	auto solve=[&](int v){
		// solve fdp when rooted at v , you walk every subtree twice
		contains=vi(n,0);
		dfs(dfs,v,-1);
		fdp=vec(vi)(n,vi(2,1e9));
		fdfs(fdfs,v,-1);
		gdp=vec(vi)(n,vi(2,1e9));
		gdfs(gdfs,v,-1);
		// rep(u,n){
		// 	cout<<gdp[u][1]<<" ";
		// }
		return gdp[v][1];
		// cout<<gdp[v][1]<<"\n";
		// cout<<gdp[v][1]<<"\n";
	};
	int ans=solve(0)+1;
	// rep(v,n){
	// 	ans=min(ans,solve(v)+1);
	// 	cout<<solve(v)<<" ";
	// 	// solve(v);
	// }
	cout<<ans<<"\n";
//	
	return 0;
}

Compilation message (stderr)

svjetlo.cpp: In instantiation of 'main()::<lambda(auto:23, int, int)> [with auto:23 = main()::<lambda(auto:23, int, int)>]':
svjetlo.cpp:98:16:   required from here
svjetlo.cpp:41:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   41 |   return contains[v]=pokita;

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30