Submission #482255

#	Time	Username	Problem	Language	Result	Execution time	Memory
482255		s_samchenko	Papričice (COCI20_papricice)	C++17	50 / 110	1097 ms	18020 KiB

papricice

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target ("avx2")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 2e5+100;

vector < vector <int> > g(N);
vector <int> sz(N), sz2(N);

void dfs(int v, int pr = -1){
	sz[v] = 1;
	for (auto to : g[v]){
		if (to == pr) continue;
		dfs(to, v);
		sz[v] += sz[to];
	}
}

void dfs2(int v, int cl, int pr = -1){
	sz2[v] = 1;
	for (auto to : g[v]){
		if (to == pr || to == cl) continue;
		dfs2(to, cl, v);
		sz2[v] += sz2[to];
	}
}

void solve(){
	int n;
	cin >> n;
	for (int i = 1; i < n; ++i){
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs(1);
	int ans = inf;
	for (int i = 2; i <= n; ++i){
		sz2.clear(); sz2.resize(n+1);
		dfs2(1, i);
		vector <int> a(3); a[0] = sz[i];
		int mx = n - sz[i];
		for (int j = 1; j <= n; ++j){
			if (!sz2[j]) continue;
			int cur = max(sz2[j], n - sz[i] - sz2[j]);
			mx = min(mx, cur);
		}
		a[1] = mx;
		a[2] = n - a[0] - a[1];
		sort(all(a));
		if (a[0]) ans = min(ans, a[2] - a[0]);
	}
	cout << ans;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while (tt--){
		solve();
		cout << '\n';
	}
}

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