oj.uz

Submission #525069

# Submission time Handle Problem Language Result Execution time Memory
525069 2022-02-10T15:44:18 Z MOUF_MAHMALAT Papričice (COCI20_papricice) C++14
50 / 110
 84 ms 25460 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 324 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 29 ms 716 KB Output is correct
7 Correct 34 ms 824 KB Output is correct
8 Correct 33 ms 716 KB Output is correct
9 Correct 25 ms 816 KB Output is correct
10 Correct 40 ms 824 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 29 ms 716 KB Output is correct
7 Correct 34 ms 824 KB Output is correct
8 Correct 33 ms 716 KB Output is correct
9 Correct 25 ms 816 KB Output is correct
10 Correct 40 ms 824 KB Output is correct
11 Runtime error 84 ms 25460 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -