Submission #698476

#	Time	Username	Problem	Language	Result	Execution time	Memory
698476		tamthegod	Papričice (COCI20_papricice)	C++17	110 / 110	359 ms	53668 KiB

papricice

// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n;
vector<int> adj[maxN];
int p[maxN], sz[maxN];
int tin[maxN], tout[maxN], Time = 0;
void ReadInput()
{
    cin >> n;
    for(int i=1; i<n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
}
void dfs(int u)
{
    sz[u] = 1;
    tin[u] = ++Time;
    for(int v : adj[u])
    {
        if(v == p[u]) continue;
        p[v] = u;
        dfs(v);
        sz[u] += sz[v];
    }
    tout[u] = Time;
}
multiset<int> S1, S2;
int res = oo;
void DFS(int u)
{
    S1.insert(sz[u]);
    S2.erase(S2.find(sz[u]));
    int tmp = (n + sz[u]) / 2;
    auto it = S1.lower_bound(tmp);
    if(it != S1.end())
    {
        int sz1 = sz[u], sz2 = *it - sz[u], sz3 = n - sz1 - sz2;
        res = min(res, max({abs(sz1 - sz2), abs(sz2 - sz3), abs(sz1 - sz3)}));
    }
    if(it != S1.begin())
    {
        it--;
        int sz1 = sz[u], sz2 = *it - sz[u], sz3 = n - sz1 - sz2;
        res = min(res, max({abs(sz1 - sz2), abs(sz2 - sz3), abs(sz1 - sz3)}));
    }
    tmp = (n - sz[u]) / 2;
    it = S2.upper_bound(tmp);
    if(it != S2.end() && *it >= sz[u])
    {
        int sz1 = sz[u], sz2 = *it, sz3 = n - sz1 - sz2;
        res = min(res, max({abs(sz1 - sz2), abs(sz2 - sz3), abs(sz1 - sz3)}));
    }
    if(it != S2.begin())
    {
        it--;
        if(*it >= sz[u])
        {
            int sz1 = sz[u], sz2 = *it, sz3 = n - sz1 - sz2;
            res = min(res, max({abs(sz1 - sz2), abs(sz2 - sz3), abs(sz1 - sz3)}));
        }
    }
    for(int v : adj[u])
    {
        if(v == p[u]) continue;
        DFS(v);
    }
    S1.erase(S1.find(sz[u]));
    S2.insert(sz[u]);
}
void Solve()
{
    dfs(1);
    for(int i=1; i<=n; i++)
        S2.insert(sz[i]);
    DFS(1);
    cout << res;
}
int32_t main()
{
    //freopen("sol.inp", "r", stdin);
    // freopen("sol.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

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