Submission #488428

#	Time	Username	Problem	Language	Result	Execution time	Memory
488428		inksamurai	Svjetlo (COCI20_svjetlo)	C++17	0 / 110	2097 ms	194424 KiB

svjetlo

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define crep(i,x,n) for(ll i=x;i<n;i++)
#define drep(i,n) for(ll 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<ll,ll>;
using vi=vector<ll>;
 
int main(){
_3HaBFkZ;
	ll 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){
		ll u,v;
		cin>>u>>v;
		u--,v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	vi contains;
	auto dfs=[&](auto self,ll v,ll 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,ll v,ll par)->void{
		ll state=a[v];
		fdp[v][state^1]=0;
		for(auto u : adj[v]){
			if(u!=par and contains[u]){
				self(self,u,v);
				vi nedp(2,1e9);
				rep(t,2){
					nedp[t]=min(nedp[t],fdp[v][t]+fdp[u][0]+4);
					nedp[t^1]=min(nedp[t^1],fdp[v][t]+fdp[u][1]+2);
				}
				fdp[v]=nedp;
			}
		}
	};
	vec(vec(vi)) gdp(n,vec(vi)(2,vi(2,1e9)));
	// vertex,color,primary_way
	auto gdfs=[&](auto self,ll v,ll par)->void{
		ll chsv=0;
		for(auto u : adj[v]){
			if(u!=par and contains[v]){
				self(self,u,v);
				chsv++;
			}
		}
		rep(t,2){
			gdp[v][t][0]=fdp[v][t];
		}
		gdp[v][1][1]=fdp[v][1];
		for(auto u : adj[v]){
			vi now(2,1e9);
			now[a[v]^1]=0;
			for(auto u1 : adj[v]){
				if(u==u1 or u1==par or !contains[u1]) continue;
				vi nedp(2,1e9);
				rep(t,2){
					nedp[t]=min(nedp[t],now[t]+gdp[u1][0][0]+4);
					nedp[t^1]=min(nedp[t^1],now[t]+gdp[u1][1][0]+2);
				}
				now=nedp;
			}
			// if(v==2) cout<<a[v]<<" ";
			now[1]+=gdp[u][1][1]+1;
			now[1]=min(now[1],now[0]+gdp[u][1][1]+3);
			gdp[v][1][1]=min(gdp[v][1][1],now[1]);
		}
		// if(v==2){
		// 	cout<<gdp[v][1][1]<<"\n";
		// }
	};
	auto solve=[&](ll v){
		contains=vi(n,0);
		dfs(dfs,v,-1);
		fdp=vec(vi)(n,vi(2,1e9));
		fdfs(fdfs,v,-1);
		gdp=vec(vec(vi))(n,vec(vi)(2,vi(2,1e9)));
		gdfs(gdfs,v,-1);
		// cout<<gdp[v][1][1]<<"\n";
		return gdp[v][1][1];
	};
	ll now,ans=1e9;
	rep(v,n){
		now=solve(v);
		ans=min(ans,now+1);
		// cout<<now<<" ";
	}
	cout<<ans<<"\n";
	// solve(1);
	// now=solve(1);
//	
	return 0;
}

Compilation message (stderr)

svjetlo.cpp: In instantiation of 'main()::<lambda(auto:23, ll, ll)> [with auto:23 = main()::<lambda(auto:23, ll, ll)>; ll = long long int]':
svjetlo.cpp:96: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