Submission #1016162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016162		vjudge1	Papričice (COCI20_papricice)	C++17	110 / 110	163 ms	22248 KiB

papricice

#include <bits/stdc++.h>

using namespace std;

const int M = 2e5 + 1;

vector<int> nei[M];
int subt[M],ans,n;
set<int> se,se1;

void calc(int u,int p=0)
{
	subt[u]=1;
	for (int i:nei[u])
		if (i!=p)
		{
			calc(i,u);
			subt[u]+=subt[i];
		}
}

void dfs(int u,int p=0)
{
	int x=subt[u]+(n-subt[u])/2;
	auto it=se.upper_bound(x);
	int val=-1;
	if (it!=se.end())
		val=*it;
	if (it!=se.begin())
	{
		it--;
		if (val==-1 || val-x>x-*it)
			val=*it;
	}
	
	if (val!=-1)
		ans=min(max(max(abs(val-subt[u]*2),abs(n-val-subt[u])),abs(n-2*val+subt[u])),ans);
	se.insert(subt[u]);
	x=(n-subt[u])/2;
	it=se1.upper_bound(x);
	val=-1;
	if (it!=se1.end())
		val=*it;
	if (it!=se1.begin())
	{
		it--;
		if (val==-1 || val-x>x-*it)
			val=*it;
	}
	if (val!=-1)
		ans=min(ans,max(abs(n-2*val-subt[u]),max(abs(n-val-2*subt[u]),abs(val-subt[u]))));
	for (int i:nei[u])
		if (i!=p)
			dfs(i,u);
	se.erase(subt[u]);
	se1.insert(subt[u]);
}

int main()
{
	cin>>n;
	ans=n;
	for (int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		nei[u].push_back(v);
		nei[v].push_back(u);
	}
	calc(1);
	dfs(1);
	cout<<ans<<endl;
	
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60