Submission #1279393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279393		luuthanhdatbienhoak66	Papričice (COCI20_papricice)	C++20	110 / 110	183 ms	20772 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
const ll N=2e5+5;
ll n,sz[N],ans=2e9;
vector<ll> adj[N];
set<ll> undone,done;
void dfs_0(ll v,ll cha)
{
    sz[v]=1;
    for(ll x:adj[v]) 
    {
        if(x!=cha)
        {
            dfs_0(x,v);
            sz[v]+=sz[x];
        }
    }
}
ll cmp(ll x,ll a)
{
    ll b=n-x-a;
    if(a<b) a^=b,b^=a,a^=b;
    if(x>a) return x-b;
    if(x<b) return a-x;
    return a-b;
}
void dfs(ll v,ll cha)
{
    auto it=done.lower_bound((n-sz[v])/2);
    if(it!=done.end()) ans=min(ans,cmp(sz[v],*it));
    if(it!=done.begin()) ans=min(ans,cmp(sz[v],*prev(it)));
    it=undone.lower_bound((n-sz[v])/2+sz[v]);
    if(it!=undone.end()) ans=min(ans,cmp(sz[v],*it-sz[v]));
    if(it!=undone.begin()) ans=min(ans,cmp(sz[v],*prev(it)-sz[v]));
    undone.insert(sz[v]);
    for(ll x:adj[v]) if(x!=cha) dfs(x,v);
    undone.erase(sz[v]);
    done.insert(sz[v]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(ll i=1,u,v; i<n; i++)
    {
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs_0(1,0);
    dfs(1,0);
    cout<<ans;
}

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