Submission #1082781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082781		serifefedartar	Papričice (COCI20_papricice)	C++17	110 / 110	298 ms	87888 KiB

papricice

#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 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60