Submission #749476

#	Time	Username	Problem	Language	Result	Execution time	Memory
749476		anhduc2701	Papričice (COCI20_papricice)	C++17	50 / 110	495 ms	35276 KiB

papricice

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e9;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int eu[maxn];
int tin[maxn];
int tout[maxn];
vector<int> G[maxn];
int sz[maxn];
int l1 = 0;
int n;
vector<int> c[maxn];
int ans = 1e9;
void calc(int a, int b, int c)
{
    ans = min(ans, max({a, b, c}) - min({a, b, c}));
}
int calc1(int a, int b, int c)
{
    return max({a, b, c}) - min({a, b, c});
}
void dfs(int u, int pa)
{
    eu[++l1] = u;
    tin[u] = l1;
    sz[u] = 1;
    for (auto v : G[u])
    {
        if (v == pa)
            continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
    tout[u] = l1;
}
multiset<int> st;
void dfs1(int u, int pa)
{
    if (pa != -1)
    {
        st.erase(st.find(sz[pa]));
        st.insert(n - sz[u]);
        auto v = st.lower_bound((n - sz[u]) / 2);
        if (v != st.end())
        {
            calc(sz[u], (*v), n - sz[u] - (*v));
        }
        auto k = st.lower_bound(sz[u]);
        if (v != st.begin())
        {
            v--;
            if (v != st.end())
            {
                if ((*v) >= sz[u] && v != k)
                {
                    calc(sz[u], (*v), n - sz[u] - (*v));
                }
            }
        }
        v = st.upper_bound((n - sz[u]) / 2);
        if (v != st.end())
        {
            calc(sz[u], (*v), n - sz[u] - (*v));
        }
        if (v != st.begin())
        {
            v--;
            if ((*v) >= sz[u] && v != k)
            {
                calc(sz[u], (*v), n - sz[u] - (*v));
            }
        }
        auto v1 = st.lower_bound(n - sz[u] * 2);
        if (v1 != st.end())
        {
            calc((*v1), sz[u], n - (*v1) - sz[u]);
        }
        // inside
        auto v2 = st.lower_bound(sz[u] / 2);
        k = st.lower_bound(n - sz[u]);
        if (v2 != st.end() && (*v2) >= n - sz[u] && k != v2)
        {
            calc(*v2, n - sz[u], sz[u] - (*v2));
        }
        if (v2 != st.begin())
        {
            v2--;
            if ((*v2) >= n - sz[u] && k != v2)
            {
                calc(*v2, n - sz[u], sz[u] - (*v2));
            }
        }
    }

    for (auto v : G[u])
    {
        if (v == pa)
            continue;
        dfs1(v, u);
    }
    if (pa != -1)
    {
        st.insert(sz[pa]);
        st.erase(st.find(n - sz[u]));
    }
}
void solve()
{
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    dfs(1, -1);
    for (int i = 1; i <= n; i++)
    {
        st.insert(sz[i]);
    }
    dfs1(1, -1);

    cout << ans << "\n";
}
signed main()
{
    solve();
}

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