Submission #525528

#	Time	Username	Problem	Language	Result	Execution time	Memory
525528		MOUF_MAHMALAT	Papričice (COCI20_papricice)	C++14	0 / 110	1 ms	460 KiB

papricice

#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define F first
#define S second
using namespace std;
typedef int ll;
ll n,x,y,dp[20][200009],sz[200009],ans=1e9;
vector<vector<ll> >v;
multiset<ll>s;
void dfs(ll d,ll p)
{
    dp[0][d]=p;
    sz[d]=1;
    for(auto&z:v[d])
        if(z!=p)
        {
            dfs(z,d);
            sz[d]+=sz[z];
        }
    s.insert(sz[d]);
}
void go(ll d,ll p)
{
    auto u=s.find(sz[d]);
    s.erase(u);
    for(auto&z:v[d])
        if(z!=p)
        {
            go(z,d);
        }
    if(d==1)
        return;
    ll o=n-sz[d];
    o+=(o&1);
    o/=2;
    auto uu=s.lower_bound(o);
    if(uu!=s.end())
    {
        x=max({sz[d],*uu,n-sz[d]-*uu});
        y=min({sz[d],*uu,n-sz[d]-*uu});
        ans=min(ans,x-y);
    }
    if(uu!=s.begin())
    {
        uu--;
        x=max({sz[d],*uu,n-sz[d]-*uu});
        y=min({sz[d],*uu,n-sz[d]-*uu});
        ans=min(ans,x-y);
    }
    ll pp=d;
    for(ll j=19; j>=0; j--)
        if(sz[dp[j][pp]]-sz[d]<o)
            pp=dp[j][pp];
    if(pp!=d)
    {
        x=max({sz[d],sz[pp]-sz[d],n-sz[p]});
        y=min({sz[d],sz[pp]-sz[d],n-sz[p]});
        ans=min(ans,x-y);
    }
    if(pp!=1)
    {
        pp=dp[0][pp];
        x=max({sz[d],sz[pp]-sz[d],n-sz[p]});
        y=min({sz[d],sz[pp]-sz[d],n-sz[p]});
        ans=min(ans,x-y);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    v.resize(n+1);
    for(ll i=1; i<n; i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,1);
    for(ll j=1; j<20; j++)
        for(ll i=1; i<=n; i++)
            dp[j][i]=dp[j-1][dp[j-1][i]];
    go(1,1);
    cout<<ans;
    return 0;
}

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