oj.uz

Submission #1082781

# Submission time Handle Problem Language Result Execution time Memory
1082781 2024-09-01T14:15:34 Z serifefedartar Papričice (COCI20_papricice) C++17
110 / 110
 298 ms 87888 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) / 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}));
            }
        }

        for (auto u : st[u])
            st[node].insert(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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Correct 4 ms 9816 KB Output is correct
3 Correct 4 ms 9860 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9724 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Correct 4 ms 9816 KB Output is correct
3 Correct 4 ms 9860 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9724 KB Output is correct
6 Correct 5 ms 10332 KB Output is correct
7 Correct 6 ms 10280 KB Output is correct
8 Correct 5 ms 10332 KB Output is correct
9 Correct 5 ms 10332 KB Output is correct
10 Correct 6 ms 10292 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Correct 4 ms 9816 KB Output is correct
3 Correct 4 ms 9860 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9724 KB Output is correct
6 Correct 5 ms 10332 KB Output is correct
7 Correct 6 ms 10280 KB Output is correct
8 Correct 5 ms 10332 KB Output is correct
9 Correct 5 ms 10332 KB Output is correct
10 Correct 6 ms 10292 KB Output is correct
11 Correct 298 ms 79576 KB Output is correct
12 Correct 268 ms 79092 KB Output is correct
13 Correct 238 ms 73040 KB Output is correct
14 Correct 261 ms 80984 KB Output is correct
15 Correct 279 ms 82772 KB Output is correct
16 Correct 171 ms 50128 KB Output is correct
17 Correct 255 ms 75600 KB Output is correct
18 Correct 177 ms 51548 KB Output is correct
19 Correct 279 ms 87888 KB Output is correct
20 Correct 275 ms 75096 KB Output is correct