oj.uz

Submission #881066

# Submission time Handle Problem Language Result Execution time Memory
881066 2023-11-30T13:38:03 Z Cyber_Wolf Papričice (COCI20_papricice) C++17
110 / 110
 192 ms 38736 KB 
#include <bits/stdc++.h>

using namespace std;

#define lg long long 
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);

const lg N = 5e5+5;

vector<lg> adj[N], late;
lg sz[N], ans = N, n;
multiset<lg> se1, se2;

void dfs(lg src, lg par = -1)
{
	sz[src] = 1;
	for(auto it : adj[src])
	{
		if(it == par)	continue;
		dfs(it, src);
		sz[src] += sz[it];
	}
	return;
}

lg cost(lg a, lg b, lg c)
{
	return max({abs(a-b), abs(a-c), abs(b-c)});
}

void dfs2(lg src, lg par = -1)
{
	se1.insert(sz[src]);
	auto it = se1.lower_bound(n/2+sz[src]/2);
	lg z = n;
	if(it != se1.end())
	{
		z = (*it);
	}
	if(it != se1.begin())
	{
		it--;
		if(cost(sz[src], n-(*it), (*it)-sz[src]) <= cost(sz[src], n-z, z-sz[src]))
		{
			z = (*it);
		}
	}
	ans = min(ans, cost(sz[src], n-z, z-sz[src]));
	it = se2.lower_bound((n-sz[src])/2);
	z = n;
	if(it != se2.end())
	{
		z = (*it);
	}
	if(it != se2.begin())
	{
		it--;
		if(cost(sz[src], n-sz[src]-(*it), (*it)) <= cost(sz[src], n-z-sz[src], z))
		{
			z = (*it);
		}
	}
	ans = min(ans, cost(sz[src], z, n-z-sz[src]));
	for(auto it : adj[src])
	{
		if(it == par)	continue;
		while(late.size())
		{
			se2.insert(late.back());
			late.pop_back();
		}
		dfs2(it, src);
	}
	se1.erase(se1.find(sz[src]));
	late.push_back(sz[src]);
	return;
}

int main()
{
	fastio;
	cin >> n;
	for(int i = 1; i < n; i++)
	{
		lg u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1);
	dfs2(1);
	cout << ans << '\n';
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13660 KB Output is correct
2 Correct 4 ms 13904 KB Output is correct
3 Correct 3 ms 13660 KB Output is correct
4 Correct 3 ms 13660 KB Output is correct
5 Correct 4 ms 13660 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13660 KB Output is correct
2 Correct 4 ms 13904 KB Output is correct
3 Correct 3 ms 13660 KB Output is correct
4 Correct 3 ms 13660 KB Output is correct
5 Correct 4 ms 13660 KB Output is correct
6 Correct 4 ms 13916 KB Output is correct
7 Correct 5 ms 13916 KB Output is correct
8 Correct 4 ms 13848 KB Output is correct
9 Correct 5 ms 13916 KB Output is correct
10 Correct 4 ms 13916 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13660 KB Output is correct
2 Correct 4 ms 13904 KB Output is correct
3 Correct 3 ms 13660 KB Output is correct
4 Correct 3 ms 13660 KB Output is correct
5 Correct 4 ms 13660 KB Output is correct
6 Correct 4 ms 13916 KB Output is correct
7 Correct 5 ms 13916 KB Output is correct
8 Correct 4 ms 13848 KB Output is correct
9 Correct 5 ms 13916 KB Output is correct
10 Correct 4 ms 13916 KB Output is correct
11 Correct 145 ms 32852 KB Output is correct
12 Correct 160 ms 32636 KB Output is correct
13 Correct 127 ms 33620 KB Output is correct
14 Correct 144 ms 33108 KB Output is correct
15 Correct 192 ms 32764 KB Output is correct
16 Correct 126 ms 33216 KB Output is correct
17 Correct 159 ms 32848 KB Output is correct
18 Correct 185 ms 38736 KB Output is correct
19 Correct 143 ms 33124 KB Output is correct
20 Correct 156 ms 32784 KB Output is correct