Submission #522390

#	Time	Username	Problem	Language	Result	Execution time	Memory
522390		N1NT3NDO	Papričice (COCI20_papricice)	C++14	110 / 110	785 ms	24384 KiB

papricice

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define sd second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("-Ofast")
//#pragma GCC target("avx2")
typedef long long ll;

//using namespace __gnu_pbds;
using namespace std;

//typedef tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = (int)2e5 + 500;
int n, sz[N], ans = 1e9, used[N];
vector<int> g[N];
set<int> out, in;
vector<int> vec;

void sizes(int v, int p)
{
    sz[v] = 1;
    for(auto u : g[v])
    {
        if (u == p || used[u]) continue;
        sizes(u, v);
        sz[v] += sz[u];
    }
}

int centoid(int v, int p, int siz)
{
    for(auto u : g[v])
    {
        if (u == p || used[u] || sz[u] < siz / 2) continue;
        return centoid(u, v, siz);
    }
    return v;
}

void dfs(int v, int p)
{
    vec.pb(sz[v]);
    if (sz(in) > 0)
    {
        auto it = in.lower_bound((n + sz[v]) / 2);
        if (it != in.end())
        {
            int cur = *it;
            ans = min(ans, max({sz[v], cur - sz[v], n - cur}) - min({sz[v], cur - sz[v], n - cur}));
        }

        if (it != in.begin())
        {
            it--;
            int cur = *it;
            ans = min(ans, max({sz[v], cur - sz[v], n - cur}) - min({sz[v], cur - sz[v], n - cur}));
        }
    }

    in.insert(sz[v]);

    if (sz(out) > 0)
    {
        auto it = out.lower_bound((n - sz[v]) / 2);
        if (it != out.end())
        {
            int cur = *it;
            ans = min(ans, max({sz[v], cur, n - cur - sz[v]}) - min({sz[v], cur, n - cur - sz[v]}));
        }

        if (it != out.begin())
        {
            it--;
            int cur = *it;
            ans = min(ans, max({sz[v], cur, n - cur - sz[v]}) - min({sz[v], cur, n - cur - sz[v]}));
        }
    }

    for(auto u : g[v])
    {
        if (u == p || used[u]) continue;
        dfs(u, v);
    }
}

void solve(int v)
{
    sizes(v, v);
    v = centoid(v, v, sz[v]);
    sizes(v, v);
    out.clear();
    //out.insert(sz[v]);
    for(auto u : g[v])
    {
        if (used[u]) continue;
        vec.clear();
        in.clear();
        in.insert(sz[v]);
        dfs(u, v);
        for(auto val : vec)
          out.insert(val);
    }

    used[v] = 1;
    for(auto u : g[v])
        if (!used[u])
          solve(u);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    solve(1);

    cout << ans;
}

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