Submission #445818

#	Time	Username	Problem	Language	Result	Execution time	Memory
445818		Jasiekstrz	Papričice (COCI20_papricice)	C++17	110 / 110	250 ms	38720 KiB

papricice

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
set<int> stmem[N+10];
set<int>* st[N+10];
vector<int> e[N+10];
int siz[N+10];
int f(int a,int b,int c)
{
	vector<int> tmp={a,b,c};
	sort(tmp.begin(),tmp.end());
	return tmp[2]-tmp[0];
}
int dfs(int x,int p,int n)
{
	int ans=n;
	siz[x]=1;
	st[x]=&stmem[x];
	for(auto v:e[x])
	{
		if(v==p)
			continue;
		ans=min(ans,dfs(v,x,n));
		siz[x]+=siz[v];
		if(st[x]->size()<st[v]->size())
			swap(st[x],st[v]);
		for(auto c:*st[v])
		{
			auto it=st[x]->lower_bound((n-c+1)/2);
			if(it!=st[x]->end())
				ans=min(ans,f(c,*it,n-*it-c));
			if(it!=st[x]->begin())
				ans=min(ans,f(c,*prev(it),n-*prev(it)-c));
		}
		for(auto c:*st[v])
			st[x]->insert(c);
		{set<int> ().swap(*st[v]);}
	}
	if(x!=1)
	{
		auto it=st[x]->lower_bound((siz[x]+1)/2);
		if(it!=st[x]->end())
			ans=min(ans,f(n-siz[x],*it,siz[x]-*it));
		if(it!=st[x]->begin())
			ans=min(ans,f(n-siz[x],*prev(it),siz[x]-*prev(it)));
	}
	st[x]->insert(siz[x]);
	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++)
	{
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	cout<<dfs(1,0,n)<<"\n";
	return 0;
}

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