Submission #479553

#	Time	Username	Problem	Language	Result	Execution time	Memory
479553		kakayoshi	Papričice (COCI20_papricice)	C++14	110 / 110	217 ms	21444 KiB

papricice

#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;
int n,sum[maxN],ans;
set<int> a,b;
vector <int> check[maxN];
int build(int u, int father) // build subtree
{
    sum[u]=1;
    for(int v:check[u])
    if (v!=father)
        sum[u]+=build(v,u);
    return sum[u];
}
void dfs(int u, int father)
{
    // set A: save current ancestors of u
    // set B: save others
    // case 1: v is an ancestor of u
    // => | (sum[v] - sum[u]) - (n-sum[v]) |  : is as small as possible
    // => | sum[v] - (n+sum[u])/2 |
    int x=(n+sum[u])/2;
    auto it=a.lower_bound(x);
    if (it!=a.end())
        ans=min(ans,max(sum[u],max(n-(*it),(*it)-sum[u]))-min(sum[u],min(n-(*it),(*it)-sum[u])));
    if (it!=a.begin())
    {
        it--;
        ans=min(ans,max(sum[u],max(n-(*it),(*it)-sum[u]))-min(sum[u],min(n-(*it),(*it)-sum[u])));
    }
    // case 2: v is not an ancestor of u
    // => | (n- sum[u] - sum[v]) - sum[v] |
    // => | (n-sum[u])/2 - sum[v] |
    x=(n-sum[u])/2;
    it=b.lower_bound(x);
    if (it!=b.end())
        ans=min(ans,max(sum[u],max(n-(*it)-sum[u],(*it)))-min(sum[u],min(n-(*it)-sum[u],(*it))));
    if (it!=b.begin())
    {
        it--;
        ans=min(ans,max(sum[u],max(n-(*it)-sum[u],(*it)))-min(sum[u],min(n-(*it)-sum[u],(*it))));
    }
    a.insert(sum[u]);
    for(int v:check[u])
    if (v!=father)
        dfs(v,u);
    a.erase(sum[u]);
    b.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;
    forw(i,1,n)
    if (check[i].size()==1)
    {
        s=i;
        break;
    }
    ans=1e9;
    build(s,0);
    //cout<<"finish"<<endl;
    dfs(s,0);
    cout<<ans;
}
int main()
{
    fast;
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    solve();
    return 0;
}

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