oj.uz

Submission #1016157

# Submission time Handle Problem Language Result Execution time Memory
1016157 2024-07-07T12:54:05 Z vjudge1 Papričice (COCI20_papricice) C++17
0 / 110
 2 ms 4956 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, sz[N], ans = 1e9;
vector<int> g[N];

void pre_dfs(int v, int p = -1){
    sz[v] = 1;
    for (int u : g[v]){
        if (u == p) continue;
        pre_dfs(u, v);
        sz[v] += sz[u];
    }
}

set<int> anc, non_anc;

void dfs(int v, int p = -1){
    auto lb = anc.lower_bound((n - sz[v]) / 2);
    if (lb != anc.end()){
        int mx = max({sz[v], (*lb) - sz[v], n - (*lb)});
        int mn = min({sz[v], (*lb) - sz[v], n - (*lb)});
        ans = min(ans, mx - mn);
    }
    if (lb != anc.begin()){
        lb--;
        int mx = max({sz[v], (*lb) - sz[v], n - (*lb)});
        int mn = min({sz[v], (*lb) - sz[v], n - (*lb)});
        ans = min(ans, mx - mn);
    }

    lb = anc.lower_bound((n - sz[v]) / 2 + 1);
    if (lb != anc.end()){
        int mx = max({sz[v], (*lb) - sz[v], n - (*lb)});
        int mn = min({sz[v], (*lb) - sz[v], n - (*lb)});
        ans = min(ans, mx - mn);
    }
    if (lb != anc.begin()){
        lb--;
        int mx = max({sz[v], (*lb) - sz[v], n - (*lb)});
        int mn = min({sz[v], (*lb) - sz[v], n - (*lb)});
        ans = min(ans, mx - mn);
    }

    auto it = non_anc.lower_bound((n - sz[v]) / 2);
    if (it != non_anc.end()){
        int mx = max({sz[v], (*it) - sz[v], n - (*it)});
        int mn = min({sz[v], (*it) - sz[v], n - (*it)});
        ans = min(ans, mx - mn);
    }
    if (it != non_anc.begin()){
        it--;
        int mx = max({sz[v], (*it) - sz[v], n - (*it)});
        int mn = min({sz[v], (*it) - sz[v], n - (*it)});
        ans = min(ans, mx - mn);
    }

    it = non_anc.lower_bound((n - sz[v]) / 2 + 1);
    if (it != non_anc.end()){
        int mx = max({sz[v], (*it) - sz[v], n - (*it)});
        int mn = min({sz[v], (*it) - sz[v], n - (*it)});
        ans = min(ans, mx - mn);
    }
    if (it != non_anc.begin()){
        it--;
        int mx = max({sz[v], (*it) - sz[v], n - (*it)});
        int mn = min({sz[v], (*it) - sz[v], n - (*it)});
        ans = min(ans, mx - mn);
    }

    anc.insert(sz[v]);
    for (int u : g[v]){
        if (u == p) continue;
        dfs(u, v);
    }
    anc.erase(sz[v]);
    non_anc.insert(sz[v]);
}

int main(){
    cin >> n;
    for (int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;
        
        g[u].push_back(v);
        g[v].push_back(u);
    }

    pre_dfs(1);
    dfs(1);

    cout << ans << endl;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Incorrect 2 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Incorrect 2 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Incorrect 2 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -