Submission #1016162

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1016162	2024-07-07T12:59:27 Z	vjudge1	Papričice (COCI20_papricice)	C++17	110 / 110	163 ms	22248 KB

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.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	5720 KB	Output is correct
2	Correct	2 ms	5724 KB	Output is correct
3	Correct	2 ms	5724 KB	Output is correct
4	Correct	2 ms	4956 KB	Output is correct
5	Correct	2 ms	4956 KB	Output is correct

Subtask #2

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	5720 KB	Output is correct
2	Correct	2 ms	5724 KB	Output is correct
3	Correct	2 ms	5724 KB	Output is correct
4	Correct	2 ms	4956 KB	Output is correct
5	Correct	2 ms	4956 KB	Output is correct
6	Correct	3 ms	5724 KB	Output is correct
7	Correct	3 ms	5212 KB	Output is correct
8	Correct	3 ms	5804 KB	Output is correct
9	Correct	3 ms	5724 KB	Output is correct
10	Correct	3 ms	5724 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	5720 KB	Output is correct
2	Correct	2 ms	5724 KB	Output is correct
3	Correct	2 ms	5724 KB	Output is correct
4	Correct	2 ms	4956 KB	Output is correct
5	Correct	2 ms	4956 KB	Output is correct
6	Correct	3 ms	5724 KB	Output is correct
7	Correct	3 ms	5212 KB	Output is correct
8	Correct	3 ms	5804 KB	Output is correct
9	Correct	3 ms	5724 KB	Output is correct
10	Correct	3 ms	5724 KB	Output is correct
11	Correct	150 ms	14728 KB	Output is correct
12	Correct	159 ms	14420 KB	Output is correct
13	Correct	115 ms	14932 KB	Output is correct
14	Correct	119 ms	14928 KB	Output is correct
15	Correct	144 ms	14592 KB	Output is correct
16	Correct	103 ms	14404 KB	Output is correct
17	Correct	133 ms	14572 KB	Output is correct
18	Correct	163 ms	22248 KB	Output is correct
19	Correct	135 ms	14820 KB	Output is correct
20	Correct	141 ms	14452 KB	Output is correct