oj.uz

Submission #879762

# Submission time Handle Problem Language Result Execution time Memory
879762 2023-11-28T05:24:12 Z TAhmed33 Papričice (COCI20_papricice) C++
50 / 110
 184 ms 25640 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 25;
vector <int> adj[MAXN];
int sze[MAXN], n, in[MAXN], out[MAXN], t;
set <int> dd[MAXN];
typedef long long ll;
int mn = 1e9; const int bad = -1e9;
void dfs (int pos, int par) {
	sze[pos] = 1;
	in[pos] = ++t;
    int mx = bad;
	for (auto j : adj[pos]) {
		if (j == par) continue;
		dfs(j, pos);
		sze[pos] += sze[j];
        if (dd[pos].size() < dd[j].size()) swap(dd[pos], dd[j]);
        for (auto i : dd[j]) dd[pos].insert(i);
        dd[j].clear();
	}
    dd[pos].insert(sze[pos]);
    for (auto i : dd[pos]) {
        if (abs(2 * i - sze[pos]) < abs(2 * mx - sze[pos])) {
            mx = i;
        }
    }
    if (sze[pos] != 1 && pos != 1) mn = min(mn, max({n - sze[pos], sze[pos] - mx, mx}) - min({n - sze[pos], sze[pos] - mx, mx}));
	out[pos] = t;
}
bool check (int x, int y) {
	return in[y] < in[x] && in[x] <= out[y];
}
int main () {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, -1);
    if (n > 2000) {
        cout << mn << '\n'; return 0;
    }
	for (int i = 2; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
            if (check(i, j) || check(j, i)) continue;
			int x = n - sze[j] - sze[i];
			mn = min(mn, max({sze[i], sze[j], x}) - min({sze[i], sze[j], x}));	
		}
	}
	cout << mn << '\n';
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 13 ms 16732 KB Output is correct
7 Correct 13 ms 16956 KB Output is correct
8 Correct 13 ms 16940 KB Output is correct
9 Correct 11 ms 16732 KB Output is correct
10 Correct 13 ms 16732 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 13 ms 16732 KB Output is correct
7 Correct 13 ms 16956 KB Output is correct
8 Correct 13 ms 16940 KB Output is correct
9 Correct 11 ms 16732 KB Output is correct
10 Correct 13 ms 16732 KB Output is correct
11 Correct 158 ms 23380 KB Output is correct
12 Incorrect 184 ms 25640 KB Output isn't correct
13 Halted 0 ms 0 KB -