oj.uz

Submission #1082780

# Submission time Handle Problem Language Result Execution time Memory
1082780 2024-09-01T14:14:23 Z serifefedartar Papričice (COCI20_papricice) C++17
0 / 110
 5 ms 9820 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 100;

vector<vector<int>> graph;
int N, sz[MAXN];
multiset<int> top, st[MAXN];

void dfs(int node, int parent) {
    sz[node] = 1;
    for (auto u : graph[node]) {
        if (u == parent)
            continue;
        dfs(u, node);
        sz[node] += sz[u];
    }
}

int ans = 1e9;
void dfs2(int node, int parent) {
    if (top.size()) {
        auto Q = top.lower_bound((N + sz[node] + 1) / 2);
        if (Q != top.end()) {
            int x = *Q;
            ans = min(ans, max({sz[node], N - x, x - sz[node]}) - min({sz[node], N - x, x - sz[node]}));
        }
        if (Q != top.begin()) {
            int x = *prev(Q);
            ans = min(ans, max({sz[node], N - x, x - sz[node]}) - min({sz[node], N - x, x - sz[node]}));
        }
    }

    top.insert(sz[node]);
    for (auto u : graph[node]) {
        if (u == parent)
            continue;
        dfs2(u, node);
    }
    top.erase(top.find(sz[node]));
}

void dfs3(int node, int parent) {
    for (auto u : graph[node]) {
        if (u == parent)
            continue;
        dfs3(u, node);

        if (st[u].size() > st[node].size())
            swap(st[u], st[node]);

        for (auto u : st[u]) {
            auto Q = st[node].lower_bound((N - u + 1) / 2);
            if (Q != st[node].end()) {
                int x = *Q;
                ans = min(ans, max({x, u, N - x - u}) - min({x, u, N - x - u}));
            }
            if (Q != st[node].begin()) {
                int x = *prev(Q);
                ans = min(ans, max({x, u, N - x - u}) - min({x, u, N - x - u}));
            }
        }
    }
    st[node].insert(sz[node]);
}

int main() {
    fast;
    int a, b;
    cin >> N;

    graph = vector<vector<int>>(N+1, vector<int>());
    for (int i = 1; i < N; i++) {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(1, 1);
    dfs2(1, 1);
    dfs3(1, 1);

    cout << ans << "\n";
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 35.0

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

Subtask #3
0 / 60.0

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