oj.uz

Submission #446284

# Submission time Handle Problem Language Result Execution time Memory
446284 2021-07-21T13:08:58 Z Jasiekstrz Svjetlo (COCI20_svjetlo) C++17
110 / 110
 1680 ms 232756 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 59084 KB Output is correct
2 Correct 31 ms 59084 KB Output is correct
3 Correct 31 ms 59020 KB Output is correct
4 Correct 31 ms 59072 KB Output is correct
5 Correct 31 ms 58980 KB Output is correct
6 Correct 31 ms 59084 KB Output is correct
7 Correct 31 ms 58964 KB Output is correct
8 Correct 31 ms 59120 KB Output is correct
9 Correct 30 ms 59028 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 166948 KB Output is correct
2 Correct 1105 ms 225548 KB Output is correct
3 Correct 1093 ms 232756 KB Output is correct
4 Correct 1008 ms 197164 KB Output is correct
5 Correct 1182 ms 217408 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 155176 KB Output is correct
2 Correct 1168 ms 183620 KB Output is correct
3 Correct 1076 ms 188772 KB Output is correct
4 Correct 874 ms 168108 KB Output is correct
5 Correct 978 ms 178204 KB Output is correct
6 Correct 977 ms 167100 KB Output is correct
7 Correct 1680 ms 182584 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 59084 KB Output is correct
2 Correct 31 ms 59084 KB Output is correct
3 Correct 31 ms 59020 KB Output is correct
4 Correct 31 ms 59072 KB Output is correct
5 Correct 31 ms 58980 KB Output is correct
6 Correct 31 ms 59084 KB Output is correct
7 Correct 31 ms 58964 KB Output is correct
8 Correct 31 ms 59120 KB Output is correct
9 Correct 30 ms 59028 KB Output is correct
10 Correct 786 ms 166948 KB Output is correct
11 Correct 1105 ms 225548 KB Output is correct
12 Correct 1093 ms 232756 KB Output is correct
13 Correct 1008 ms 197164 KB Output is correct
14 Correct 1182 ms 217408 KB Output is correct
15 Correct 920 ms 155176 KB Output is correct
16 Correct 1168 ms 183620 KB Output is correct
17 Correct 1076 ms 188772 KB Output is correct
18 Correct 874 ms 168108 KB Output is correct
19 Correct 978 ms 178204 KB Output is correct
20 Correct 977 ms 167100 KB Output is correct
21 Correct 1680 ms 182584 KB Output is correct
22 Correct 992 ms 167372 KB Output is correct
23 Correct 978 ms 163412 KB Output is correct
24 Correct 866 ms 147020 KB Output is correct
25 Correct 924 ms 166316 KB Output is correct
26 Correct 996 ms 181136 KB Output is correct
27 Correct 915 ms 165624 KB Output is correct
28 Correct 669 ms 136388 KB Output is correct
29 Correct 1020 ms 177092 KB Output is correct
30 Correct 1368 ms 168628 KB Output is correct