답안 #488421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
488421 2021-11-18T20:34:03 Z inksamurai Svjetlo (COCI20_svjetlo) C++17
0 / 110
2000 ms 191852 KB
#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 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,int v,int par)->void{
		int 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=[&](int 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];
	};
	int 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

svjetlo.cpp: In instantiation of 'main()::<lambda(auto:23, int, int)> [with auto:23 = main()::<lambda(auto:23, int, 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;
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2095 ms 191852 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2098 ms 160276 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -