Submission #1045025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045025		Beerus13	Papričice (COCI20_papricice)	C++14	110 / 110	137 ms	30292 KiB

papricice

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 5;
const int inf = 1e9;

bool minimize(int &a, int b) {
    if(a <= b) return true;
    a = b;
    return false;
}

int n, sz[N], ans = inf;
vector<int> g[N];
multiset<int> anc, oth;

vector<int> opt(int x, multiset<int> &sett) {
    auto it = sett.lower_bound(x);
    vector<int> v;
    v.push_back(*it);
    --it;
    v.push_back(*it);
    return v;
}

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

void dfs_size(int u, int p = 0) {
    sz[u] = 1;
    for(int v : g[u]) if(v != p) {
        dfs_size(v, u);
        sz[u] += sz[v];
    }
}

void dfs(int u, int p = 0) {
    for(int x : opt(n + sz[u] >> 1, anc)) {
        minimize(ans, cost(sz[u], n - x, x - sz[u]));
    }
    for(int x : opt(n - sz[u] >> 1, oth)) {
        minimize(ans, cost(sz[u], n - sz[u] - x, x));
    }
    anc.insert(sz[u]);
    for(int v : g[u]) if(v != p) dfs(v, u);
    anc.erase(anc.find(sz[u]));
    oth.insert(sz[u]);
}

void solve() {
    cin >> n;
    for(int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    anc.insert(-inf); anc.insert(inf);
    oth.insert(-inf); oth.insert(inf);
    dfs_size(1);
    dfs(1);
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

Compilation message (stderr)

papricice.cpp: In function 'void dfs(int, int)':
papricice.cpp:39:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     for(int x : opt(n + sz[u] >> 1, anc)) {
      |                     ~~^~~~~~~
papricice.cpp:42:23: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   42 |     for(int x : opt(n - sz[u] >> 1, oth)) {
      |                     ~~^~~~~~~

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