oj.uz

Submission #497764

# Submission time Handle Problem Language Result Execution time Memory
497764 2021-12-23T18:28:21 Z AlperenT Papričice (COCI20_papricice) C++17
110 / 110
 245 ms 28332 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5, INF = 1e9 + 5;

int n, a, b, cnt[N], ans = INF;

multiset<int> anc, oth;

vector<int> tree[N];

void dfs(int v, int p = 0){
    cnt[v] = 1;

    for(auto e : tree[v]){
        if(e != p){
            dfs(e, v);
            cnt[v] += cnt[e];
        }
    }
}

void getans(int x){
    int y, z;

    if(!anc.empty()){
        auto it = anc.lower_bound((n + x) / 2);

        if(it != anc.end()){
            y = *it - x, z = n - *it;

            ans = min(ans, max({x, y, z}) - min({x, y, z}));
        }

        if(it != anc.begin()){
            it = prev(it);

            y = *it - x, z = n - *it;

            ans = min(ans, max({x, y, z}) - min({x, y, z}));
        }
    }

    if(!oth.empty()){
        auto it = oth.lower_bound((n - x) / 2);

        if(it != oth.end()){
            y = *it, z = n - x - y;

            ans = min(ans, max({x, y, z}) - min({x, y, z}));
        }

        if(it != oth.begin()){
            it = prev(it);

            y = *it, z = n - x - y;

            ans = min(ans, max({x, y, z}) - min({x, y, z}));
        }
    }
}

void solve(int v, int p = 0){
    getans(cnt[v]);

    anc.insert(cnt[v]);

    for(auto e : tree[v]){
        if(e != p) solve(e, v);
    }

    anc.erase(anc.find(cnt[v]));
    oth.insert(cnt[v]);
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n;

    for(int i = 0; i < n - 1; i++){
        cin >> a >> b;

        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    dfs(1);

    solve(1);

    cout << ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 4940 KB Output is correct
5 Correct 2 ms 4972 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 4940 KB Output is correct
5 Correct 2 ms 4972 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 4 ms 5152 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 3 ms 5196 KB Output is correct
10 Correct 4 ms 5196 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 4940 KB Output is correct
5 Correct 2 ms 4972 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 4 ms 5152 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 3 ms 5196 KB Output is correct
10 Correct 4 ms 5196 KB Output is correct
11 Correct 231 ms 23976 KB Output is correct
12 Correct 229 ms 23960 KB Output is correct
13 Correct 192 ms 24484 KB Output is correct
14 Correct 188 ms 24136 KB Output is correct
15 Correct 245 ms 23924 KB Output is correct
16 Correct 152 ms 23892 KB Output is correct
17 Correct 239 ms 24136 KB Output is correct
18 Correct 234 ms 28332 KB Output is correct
19 Correct 231 ms 24064 KB Output is correct
20 Correct 204 ms 23992 KB Output is correct