oj.uz

Submission #1016151

# Submission time Handle Problem Language Result Execution time Memory
1016151 2024-07-07T12:49:36 Z vjudge1 Papričice (COCI20_papricice) C++17
0 / 110
 2 ms 5724 KB 
#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-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-x>x-*it)
			val=*it;
	}
	if (val!=-1)
		ans=min(ans,max(abs(n-2*val),max(abs(n-val-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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Incorrect 2 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Incorrect 2 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Incorrect 2 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -