oj.uz

Submission #479337

# Submission time Handle Problem Language Result Execution time Memory
479337 2021-10-11T11:20:17 Z kakayoshi Papričice (COCI20_papricice) C++14
0 / 110
 13 ms 14412 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pi;
typedef pair<ll, pair<ll, ll> > pii;
typedef vector <ll> vi;
#define forw(i,a,b) for (ll i=a;i<=(b);i++)
#define forb(i,a,b) for (ll i=a;i>=(b);i--)
#define fast {ios::sync_with_stdio(false); cin.tie(0); }
#define fi first
#define se second
#define pu push
#define puf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fr front
#define all(a) a.begin(),a.end()
const ll oo=1e18;
const ll mod=1e9+7;
const int base=31;
const int tx[4]={0,0,1,-1};
const int ty[4]={1,-1,0,0};
const ll maxN=2e5+5;
set<int> save[maxN];
vector <int> check[maxN];
int n,ans,sum[maxN];
void dfs(int u, int father)
{
    sum[u]=1;
    int res=1;
    for(int v:check[u])
    if (v!=father)
    {
        dfs(v,u);
        int top,bot,mid;
        top=n-sum[v];
        int x=(n-top)/2+((n-top)%2);
        auto it=save[v].lower_bound(x);
        if (it!=save[v].end())
        {
            bot=*it;
            mid=n-top-bot;
            if (mid!=0 && bot!=0 && top!=0)
                ans=min(ans,max(mid,max(top,bot))-min(mid,min(top,bot)));
        }
        if (it!=save[v].begin())
        {
            it--;
            bot=*it;
            mid=n-top-bot;
            if (mid!=0 && bot!=0 && top!=0)
                ans=min(ans,max(mid,max(top,bot))-min(mid,min(top,bot)));
        }
        if (it!=save[v].begin())
        {
            it--;
            bot=*it;
            mid=n-top-bot;
            if (mid!=0 && bot!=0 && top!=0)
                ans=min(ans,max(mid,max(top,bot))-min(mid,min(top,bot)));
        }
        res=max(res,sum[v]);
        sum[u]+=sum[v];
        if (save[u].size()<save[v].size()) swap(save[u],save[v]);
        save[u].insert(save[v].begin(),save[v].end());
        save[v].clear();
    }
    save[u].insert(sum[u]);
    return;
}
void solve()
{
    cin>>n;
    forw(i,1,n-1)
    {
        int u,v;
        cin>>u>>v;
        check[u].pb(v);
        check[v].pb(u);
    }
    int s=0;
    ans=1e9;
    forw(i,1,n)
    if (check[i].size()==1)
    {
        s=i;
        break;
    }
    dfs(s,0);
    cout<<ans<<endl;
}
int main()
{
    fast;
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    solve();
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14412 KB Output is correct
2 Correct 11 ms 14304 KB Output is correct
3 Incorrect 13 ms 14412 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14412 KB Output is correct
2 Correct 11 ms 14304 KB Output is correct
3 Incorrect 13 ms 14412 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14412 KB Output is correct
2 Correct 11 ms 14304 KB Output is correct
3 Incorrect 13 ms 14412 KB Output isn't correct
4 Halted 0 ms 0 KB -