oj.uz

Submission #484925

# Submission time Handle Problem Language Result Execution time Memory
484925 2021-11-05T18:06:20 Z Kirill22 Papričice (COCI20_papricice) C++17
110 / 110
 271 ms 30072 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int) (x).size()

const int N = 200000;
int n, ans = (int) 1e9;
vector<int> g[N];
int cnt[N];
multiset<int> a, b;

void get_sz(int v, int pr) {
    cnt[v] = 1;
    for (auto x : g[v]) {
        if (x != pr) {
            get_sz(x, v);
            cnt[v] += cnt[x];
        }
    }
}

void solve(int v, int pr = -1) {
    {
        int X = n - cnt[v];
        auto it = b.lower_bound(X / 2);
        if (it != b.end()) {
            ans = min(ans, max({cnt[v], *it, X - *it}) - min({cnt[v], *it, X - *it}));
        }
        if (it != b.begin()) {
            it--;
            ans = min(ans, max({cnt[v], *it, X - *it}) - min({cnt[v], *it, X - *it}));
        }
    }
    {
        int X = n + cnt[v];
        auto it = a.lower_bound(X / 2);
        if (it != a.end()) {
            ans = min(ans, max({cnt[v], *it - cnt[v], n - *it}) - min({cnt[v], *it - cnt[v], n - *it}));
        }
        if (it != a.begin()) {
            it--;
            ans = min(ans, max({cnt[v], *it - cnt[v], n - *it}) - min({cnt[v], *it - cnt[v], n - *it}));
        }
    }
    a.insert(cnt[v]);
    for (auto x : g[v]) {
        if (x != pr) {
            solve(x, v);
        }
    }
    a.erase(a.find(cnt[v]));
    b.insert(cnt[v]);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    get_sz(0, -1);
    solve(0, -1);
    cout << ans;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 5012 KB Output is correct
5 Correct 2 ms 5012 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 4 ms 5156 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 5 ms 5152 KB Output is correct
10 Correct 5 ms 5196 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 5012 KB Output is correct
5 Correct 2 ms 5012 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 4 ms 5156 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 5 ms 5152 KB Output is correct
10 Correct 5 ms 5196 KB Output is correct
11 Correct 208 ms 25776 KB Output is correct
12 Correct 229 ms 25784 KB Output is correct
13 Correct 198 ms 26436 KB Output is correct
14 Correct 177 ms 26108 KB Output is correct
15 Correct 253 ms 25668 KB Output is correct
16 Correct 150 ms 25508 KB Output is correct
17 Correct 186 ms 25796 KB Output is correct
18 Correct 205 ms 30072 KB Output is correct
19 Correct 271 ms 26116 KB Output is correct
20 Correct 198 ms 25716 KB Output is correct