Submission #1286742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286742		red_souls	Papričice (COCI20_papricice)	C++17	110 / 110	136 ms	20988 KiB

papricice

#include <bits/stdc++.h>
#define ll long long
#define task "chili"
using namespace std;

const int N = 2e5 + 16, INF = 1e9;
int n, u, v;
vector <int> adj[N];

namespace sub3 {

    int sz[N], result = INF;

    void preDfs(int k, int p) {
        sz[k] = 1;
        for (auto v : adj[k]) {
            if (v == p) {
                continue;
            }
            preDfs(v, k);
            sz[k] += sz[v];
        }
    }

    int calc(int a, int b, int c) {
        return max({a, b, c}) - min({a, b, c});
    }

    vector <int> ancestor(set <int> &lst, int pos) {
        vector <int> res;
        auto it = lst.lower_bound(pos);
        if (it != lst.end()) {
            res.push_back(*it);
        }
        if (it != lst.begin()) {
            --it;
            res.push_back(*it);
        }
        return res;
    }

    set <int> anc, notAnc;

    void dfs(int k, int p) {

        for (auto x : ancestor(anc, ((n - sz[k]) >> 1) + sz[k])) {
            result = min(result, calc(n - x, x - sz[k], sz[k]));
        }
        for (auto x : ancestor(notAnc, (n - sz[k] >> 1))) {
            result = min(result, calc(n - x - sz[k], x, sz[k]));
        }

        anc.insert(sz[k]);
        for (auto v : adj[k]) {
            if (v == p) {
                continue;
            }
            dfs(v, k);
        }
        anc.erase(sz[k]);
        notAnc.insert(sz[k]);
    }

    void solve() {
        preDfs(1, 1);
        dfs(1, 1);
        cout << result;
    }
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    sub3 :: solve();

    return 0;
}

Compilation message (stderr)

papricice.cpp: In function 'int main()':
papricice.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60