제출 #1129730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129730		12345678	Papričice (COCI20_papricice)	C++17	110 / 110	706 ms	43308 KiB

papricice

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5, kx=18;

int n, u, v, pa[nx][kx], sz[nx], in[nx], out[nx], rv[nx], t, res=1e9;
vector<int> d[nx];
multiset<int> ms;

void solve(int x, int y)
{
    //cout<<x<<' '<<y<<' '<<n-x-y<<'\n';
    res=min(res, max({x, y, n-x-y})-min({x, y, n-x-y}));
}

void dfs(int u, int p)
{
    sz[u]=1;
    in[u]=++t;
    rv[t]=u;
    pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto v:d[u]) if (v!=p) dfs(v, u), sz[u]+=sz[v];
    out[u]=t;
}

void sack(int u, int p, int del)
{
    //cout<<"here "<<u<<'\n';
    ms.erase(ms.find(sz[u]));
    pair<int, int> hv;
    for (auto v:d[u]) if (v!=p) hv=max(hv, {sz[v], v});
    for (auto v:d[u]) if (v!=hv.second&&v!=p) sack(v, u, 1);
    if (hv.second) sack(hv.second, u, 0);
    for (auto v:d[u]) if (v!=hv.second&&v!=p) for (int i=in[v]; i<=out[v]; i++) ms.erase(ms.find(sz[rv[i]]));
    /*
    cout<<"finding "<<u<<'\n';
    cout<<"ms ";
    for (auto x:ms) cout<<x<<' ';
    cout<<'\n';
    */
    if (!ms.empty()) 
    {
        solve(sz[u], *prev(ms.upper_bound((n-sz[u])/2)));
        if (ms.lower_bound((n-sz[u])/2)!=ms.end()) solve(sz[u], *ms.lower_bound((n-sz[u])/2));
    }
    v=u;
    for (int i=kx-1; i>=0; i--) if (sz[pa[v][i]]-sz[u]<=n-sz[pa[v][i]]) v=pa[v][i];
    solve(sz[u], n-sz[v]);
    v=pa[v][0];
    solve(sz[u], n-sz[v]);
    if (del) for (int i=in[u]; i<=out[u]; i++) ms.insert(sz[rv[i]]);
}

int main()
{
    //cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    dfs(1, 1);
    for (int i=1; i<=n; i++) ms.insert(sz[i]);
    sack(1, 1, 0);
    cout<<res;
}

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