Submission #472436

#	Time	Username	Problem	Language	Result	Execution time	Memory
472436		mychecksedad	Papričice (COCI20_papricice)	C++17	110 / 110	306 ms	29292 KiB

papricice

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int n, ans = 3700000, a, b;
vector<vector<int>> g;
vector<int> dp;
multiset<int> s;
void dfs(int v, int p){
	dp[v] = 1;
	for(int u: g[v])
		if(u != p) dfs(u, v), dp[v] += dp[u];
}
void dfs1(int v, int p){
	auto it = s.lower_bound((n-dp[v]) / 2);
	if(it == s.begin()){
		if(it != s.end()){
			int x = *it, y = n-(dp[v]+x);
			ans = min(ans, max({abs(x - dp[v]), abs(x - y), abs(y - dp[v])}));
		}
	}else{
		if(it != s.end()){
			int x = *it, y = n-(dp[v]+x);
			ans = min(ans, max({abs(x - dp[v]), abs(x - y), abs(y - dp[v])}));
		}
		--it;
		int x = *it, y = n-(dp[v]+x);
		ans = min(ans, max({abs(x - dp[v]), abs(x - y), abs(y - dp[v])}));
	}
	for(int u: g[v]) if(u != p) dfs1(u, v);
	s.insert(dp[v]);
}
void dfs2(int v, int p){
	auto it = s.lower_bound((n-dp[v]) / 2);
	if(it == s.begin()){
		if(it != s.end()){
			int x = *it, y = n-(dp[v]+x);
			ans = min(ans, max({abs(x - dp[v]), abs(x - y), abs(y - dp[v])}));
		}
	}else{
		if(it != s.end()){
			int x = *it, y = n-(dp[v]+x);
			ans = min(ans, max({abs(x - dp[v]), abs(x - y), abs(y - dp[v])}));
		}
		--it;
		int x = *it, y = n-(dp[v]+x);
		ans = min(ans, max({abs(x - dp[v]), abs(x - y), abs(y - dp[v])}));
	}
	s.insert(n - dp[v]);
	for(int u: g[v]) if(u != p) dfs2(u, v);
	s.erase(s.find(n-dp[v]));
}
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> n;
	g.resize(n+1);
	dp.resize(n+1);
	for(int i=0; i < n-1; i++){
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs(1, 0);
	dfs1(1, 0);
	s.clear();
	dfs2(1, 0);
	cout << ans;


	return 0;
}

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