Submission #446284

#	Time	Username	Problem	Language	Result	Execution time	Memory
446284		Jasiekstrz	Svjetlo (COCI20_svjetlo)	C++17	110 / 110	1680 ms	232756 KiB

svjetlo

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=5e5;
const int INF=1e9+7;
vector<int> e[N+10];
bool t[N+10];
int sum[N+10];
pair<int,bool> dp0[N+10];
int dp1[N+10][2];
int all[N+10];
int deg[N+10];
multiset<int> mn[N+10][2];
bool is_all(int x)
{
	return all[x]==deg[x] && t[x];
}
void dfs1(int x,int p)
{
	deg[x]=0;
	for(auto v:e[x])
	{
		if(v!=p)
		{
			deg[x]++;
			dfs1(v,x);
		}
	}

	all[x]=0;
	sum[x]=0;
	dp0[x]={0,0};
	for(auto v:e[x])
	{
		if(v==p)
			continue;
		if(!is_all(v))
		{
			sum[x]+=dp0[v].se;
			dp0[x].fi+=dp0[v].fi;
			sum[x]++;
		}
		else
			all[x]++;
	}
	sum[x]++;
	if(sum[x]%2==t[x])
	{
		dp0[x].se=1;
		sum[x]++;
	}
	dp0[x].fi+=sum[x];

	mn[x][0].clear();
	mn[x][1].clear();
	mn[x][0].insert(0);
	mn[x][1].insert(INF);
	for(auto v:e[x])
	{
		if(v==p)
			continue;
		if(!is_all(v))
		{
			mn[x][0].insert(dp1[v][!dp0[v].se]-2*dp0[v].se-dp0[v].fi);
			mn[x][1].insert(dp1[v][dp0[v].se]-dp0[v].fi);
		}
	}
	dp1[x][dp0[x].se]=dp0[x].fi+*mn[x][0].begin();
	dp1[x][!dp0[x].se]=dp0[x].fi+*mn[x][1].begin()-2*dp0[x].se;
	return;
}
void reroot(int nw,int old)
{
	// update old root
	deg[old]--;
	if(!is_all(nw))
	{
		dp0[old].fi-=dp0[nw].se+dp0[nw].fi+1;
		sum[old]-=dp0[nw].se+1;
		mn[old][0].erase(mn[old][0].find(dp1[nw][!dp0[nw].se]-2*dp0[nw].se-dp0[nw].fi));
		mn[old][1].erase(mn[old][1].find(dp1[nw][dp0[nw].se]-dp0[nw].fi));
	}
	else
		all[old]--;
	if(sum[old]%2==t[old])
	{
		dp0[old].fi-=dp0[old].se;
		sum[old]-=dp0[old].se;
		dp0[old].se=!dp0[old].se;
		dp0[old].fi+=dp0[old].se;
		sum[old]+=dp0[old].se;
	}
	dp1[old][dp0[old].se]=dp0[old].fi+*mn[old][0].begin();
	dp1[old][!dp0[old].se]=dp0[old].fi+*mn[old][1].begin()-2*dp0[old].se;

	// update new root
	deg[nw]++;
	if(!is_all(old))
	{
		dp0[nw].fi+=dp0[old].se+dp0[old].fi+1;
		sum[nw]+=dp0[old].se+1;
		mn[nw][0].insert(dp1[old][!dp0[old].se]-2*dp0[old].se-dp0[old].fi);
		mn[nw][1].insert(dp1[old][dp0[old].se]-dp0[old].fi);
	}
	else
		all[nw]++;
	if(sum[nw]%2==t[nw])
	{
		dp0[nw].fi-=dp0[nw].se;
		sum[nw]-=dp0[nw].se;
		dp0[nw].se=!dp0[nw].se;
		dp0[nw].fi+=dp0[nw].se;
		sum[nw]+=dp0[nw].se;
	}
	dp1[nw][dp0[nw].se]=dp0[nw].fi+*mn[nw][0].begin();
	dp1[nw][!dp0[nw].se]=dp0[nw].fi+*mn[nw][1].begin()-2*dp0[nw].se;
	return;
}
int dfs2(int x,int p)
{
	int ans=dp1[x][0];
	for(auto v:e[x])
	{
		if(v!=p)
		{
			reroot(v,x);
			ans=min(ans,dfs2(v,x));
			reroot(x,v);
		}
	}
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c;
		t[i]=(c=='1');
	}
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}

	dfs1(1,0);
	cout<<dfs2(1,0)<<"\n";
	return 0;
}

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