oj.uz

Submission #1016149

# Submission time Handle Problem Language Result Execution time Memory
1016149 2024-07-07T12:49:18 Z vjudge1 Papričice (COCI20_papricice) C++17
0 / 110
 4 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 = non_anc.lower_bound((n - sz[v]) / 2);
    if (lb != non_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 != non_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);
    }

    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 4 ms 4956 KB Output is correct
2 Incorrect 3 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 4 ms 4956 KB Output is correct
2 Incorrect 3 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 4 ms 4956 KB Output is correct
2 Incorrect 3 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -