Submission #525069

#	Time	Username	Problem	Language	Result	Execution time	Memory
525069		MOUF_MAHMALAT	Papričice (COCI20_papricice)	C++14	50 / 110	84 ms	25460 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,o,sz[2009],f[2009],lg[4009],ans=1e9;
vector<vector<ll> >v;
pair<ll,ll>p[13][4009];
void dfs(ll d,ll pp,ll h)
{
    p[0][o]= {h,d};
    f[d]=o++;
    sz[d]=1;
    for(auto&z:v[d])
        if(z!=pp)
        {
            dfs(z,d,h+1);
            p[0][o++]= {h,d};
            sz[d]+=sz[z];
        }
}
ll lca(ll i,ll j)
{
    i=f[i],j=f[j];
    if(i>j)
        swap(i,j);
    ll k=lg[j-i+1];
    return min(p[k][i],p[k][j-(1<<k)+1]).S;
}
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,0,0);
    for(ll i=2; i<=o; i++)
        lg[i]=lg[i>>1]+1;
    for(ll j=1; j<13; j++)
        for(ll i=0; i+(1<<j)<=o; i++)
            p[j][i]=min(p[j-1][i],p[j-1][i+(1<<(j-1))]);
    for(ll i=1; i<n; i++)
        for(ll j=i+1; j<=n; j++)
        {
            x=lca(i,j);
            if(x!=i&&x!=j)
            {
                ll a=max({sz[i],sz[j],n-sz[i]-sz[j]});
                ll b=min({sz[i],sz[j],n-sz[i]-sz[j]});
                ans=min(ans,a-b);
            }
            else
            {
                if(x==i)
                    y=j;
                else
                    y=i;
                ll a=max({sz[y],sz[x]-sz[y],n-sz[x]});
                ll b=min({sz[y],sz[x]-sz[y],n-sz[x]});
                ans=min(ans,a-b);
            }
        }
    cout<<ans;
    return 0;
}

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