oj.uz

Submission #879791

# Submission time Handle Problem Language Result Execution time Memory
879791 2023-11-28T06:51:07 Z TAhmed33 Papričice (COCI20_papricice) C++
110 / 110
 128 ms 26140 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
const int MAXN = 2e5 + 25;
const int bad = -1e7;
inline int comb (int a, int b, int c) {
    return abs(2 * a - c) < abs(2 * b - c) ? a : b;
}
vector <int> adj[MAXN];
int sze[MAXN], n, in[MAXN], out[MAXN], t;
int mn = 1e9; 
set <int> dfs (int pos, int par) {
    sze[pos] = 1;
    in[pos] = ++t;
    int mx = bad;
    set <int> cur;
    for (auto j : adj[pos]) {
        if (j == par) continue;
        auto x = dfs(j, pos);
        sze[pos] += sze[j];
        if (cur.size() < x.size()) cur.swap(x);
        for (auto i : x) cur.insert(i);
    }
    auto tt = cur.lower_bound(sze[pos] / 2);
    if (tt != cur.end()) mx = *tt;
    if (tt != cur.begin()) {
        tt--; mx = comb(mx, *tt, sze[pos]);
    }
    cur.insert(sze[pos]);
    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;
    return cur;
}
set <int> x;
void dfs2 (int pos, int par) {
    if (pos != 1 && !x.empty()) {
        auto t = x.lower_bound((n - sze[pos]) / 2);
        int ret = bad;
        if (t != x.end()) ret = *t;
        if (t != x.begin()) {
            t--;
            ret = comb(ret, *t, n - sze[pos]);
        }
        mn = min(mn, max({sze[pos], ret, n - sze[pos] - ret}) - min({sze[pos], ret, n - sze[pos] - ret}));
    }
    for (auto j : adj[pos]) if (j != par) dfs2(j, pos);
    x.insert(sze[pos]);
}
bool check (int x, int y) {
    return in[x] <= in[y] && in[y] <= out[x];
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    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);
    dfs2(1, -1);
    cout << mn << '\n';
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7260 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 3 ms 7260 KB Output is correct
8 Correct 3 ms 7260 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 1 ms 7260 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 3 ms 7260 KB Output is correct
8 Correct 3 ms 7260 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 93 ms 14028 KB Output is correct
12 Correct 91 ms 13972 KB Output is correct
13 Correct 124 ms 14416 KB Output is correct
14 Correct 90 ms 14160 KB Output is correct
15 Correct 91 ms 13908 KB Output is correct
16 Correct 113 ms 14624 KB Output is correct
17 Correct 82 ms 14012 KB Output is correct
18 Correct 123 ms 26140 KB Output is correct
19 Correct 102 ms 16468 KB Output is correct
20 Correct 128 ms 16468 KB Output is correct