oj.uz

Submission #366587

# Submission time Handle Problem Language Result Execution time Memory
366587 2021-02-14T16:55:56 Z VEGAnn Papričice (COCI20_papricice) C++14
110 / 110
 316 ms 28396 KB 
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
const int N = 200100;
const int oo = 2e9;
multiset<int> A, B;
multiset<int>::iterator itr;
vector<int> g[N];
int n, siz[N], ans = oo;

void calc_siz(int v, int p){
    siz[v] = 1;

    for (int u : g[v]){
        if (u == p) continue;

        calc_siz(u, v);

        siz[v] += siz[u];
    }
}

void upd(int x, int y, int z){
    ans = min(ans, max(max(abs(x - y), abs(y - z)), abs(z - x)));
}

void dfs(int v, int p){
    if (v > 0) {
        if (sz(A) > 0){
            itr = A.upper_bound((n + siz[v]) / 2);

            if (itr != A.end()){
                int cur = (*itr);

                upd(siz[v], cur - siz[v], n - cur);
            }

            if (itr != A.begin()){
                int cur = (*prev(itr));

                upd(siz[v], cur - siz[v], n - cur);
            }
        }

        if (sz(B) > 0){
            itr = B.upper_bound((n - siz[v]) / 2);

            if (itr != B.end()){
                int cur = (*itr);

                upd(siz[v], cur, n - cur - siz[v]);
            }

            if (itr != B.begin()){
                int cur = (*prev(itr));

                upd(siz[v], cur, n - cur - siz[v]);
            }
        }

        A.insert(siz[v]);
    }

    for (int u : g[v]){
        if (u == p) continue;

        dfs(u, v);
    }

    if (v > 0){
        A.erase(A.find(siz[v]));
        B.insert(siz[v]);
    }
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y; x--; y--;

        g[x].PB(y);
        g[y].PB(x);
    }

    calc_siz(0, -1);
    dfs(0, -1);

    cout << ans;

    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 5 ms 5228 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 6 ms 5240 KB Output is correct
10 Correct 5 ms 5356 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 5 ms 5228 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Correct 6 ms 5240 KB Output is correct
10 Correct 5 ms 5356 KB Output is correct
11 Correct 297 ms 24044 KB Output is correct
12 Correct 316 ms 24172 KB Output is correct
13 Correct 234 ms 24556 KB Output is correct
14 Correct 267 ms 24428 KB Output is correct
15 Correct 307 ms 24208 KB Output is correct
16 Correct 201 ms 24040 KB Output is correct
17 Correct 263 ms 24172 KB Output is correct
18 Correct 285 ms 28396 KB Output is correct
19 Correct 254 ms 24172 KB Output is correct
20 Correct 280 ms 24044 KB Output is correct