oj.uz

Submission #881063

# Submission time Handle Problem Language Result Execution time Memory
881063 2023-11-30T13:34:02 Z Cyber_Wolf Papričice (COCI20_papricice) C++17
110 / 110
 288 ms 41296 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);
	late.clear();
	se2.clear();
	se1.clear();
	for(int i = 1; i <= n; i++)	reverse(adj[i].begin(), adj[i].end());
	dfs2(1);
	cout << ans << '\n';
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13656 KB Output is correct
2 Correct 3 ms 13660 KB Output is correct
3 Correct 3 ms 13660 KB Output is correct
4 Correct 3 ms 13660 KB Output is correct
5 Correct 3 ms 13660 KB Output is correct
6 Correct 4 ms 13916 KB Output is correct
7 Correct 4 ms 13916 KB Output is correct
8 Correct 4 ms 13904 KB Output is correct
9 Correct 4 ms 13916 KB Output is correct
10 Correct 5 ms 13916 KB Output is correct
11 Correct 267 ms 35424 KB Output is correct
12 Correct 288 ms 35328 KB Output is correct
13 Correct 195 ms 35968 KB Output is correct
14 Correct 238 ms 35912 KB Output is correct
15 Correct 268 ms 35156 KB Output is correct
16 Correct 166 ms 35004 KB Output is correct
17 Correct 260 ms 35424 KB Output is correct
18 Correct 277 ms 41296 KB Output is correct
19 Correct 241 ms 36188 KB Output is correct
20 Correct 280 ms 35364 KB Output is correct