oj.uz

Submission #482255

# Submission time Handle Problem Language Result Execution time Memory
482255 2021-10-23T23:43:30 Z s_samchenko Papričice (COCI20_papricice) C++17
50 / 110
 1000 ms 18020 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8156 KB Output is correct
2 Correct 5 ms 8084 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 6 ms 8060 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8156 KB Output is correct
2 Correct 5 ms 8084 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 6 ms 8060 KB Output is correct
6 Correct 67 ms 8176 KB Output is correct
7 Correct 70 ms 8232 KB Output is correct
8 Correct 55 ms 8164 KB Output is correct
9 Correct 64 ms 8236 KB Output is correct
10 Correct 81 ms 8240 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8156 KB Output is correct
2 Correct 5 ms 8084 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 6 ms 8060 KB Output is correct
6 Correct 67 ms 8176 KB Output is correct
7 Correct 70 ms 8232 KB Output is correct
8 Correct 55 ms 8164 KB Output is correct
9 Correct 64 ms 8236 KB Output is correct
10 Correct 81 ms 8240 KB Output is correct
11 Execution timed out 1097 ms 18020 KB Time limit exceeded
12 Halted 0 ms 0 KB -