Submission #1311674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311674		hanguyendanghuy	Papričice (COCI20_papricice)	C++20	0 / 110	3 ms	332 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
const ll MAXN=3e5+5,MOD=1e9+7,INF=1e18;
ll i,n,m,j,k,p,cnt,dem,de[MAXN],id[MAXN],sz[MAXN],par[MAXN],en[MAXN],nen[MAXN],parma[MAXN];
vector<ll> adj[MAXN];
void dfs(ll u,ll pre,ll parup){
    sz[u]=1;
    id[u]=++cnt;
    nen[cnt]=u;
    parma[u]=parup;
    for(auto x:adj[u]){
        if(x==pre) continue;
        if(u==1) parup=x;
        par[x]=u;
        de[x]=de[u]+1;
        dfs(x,u,parup);
        sz[u]+=sz[x];
    }
    en[u]=cnt;
}
struct mergetree{
    vector<ll> b[MAXN];
    void build(ll in,ll l,ll r){
        if(l==r){
            b[in].pb(sz[nen[l]]);
        }
        else{
            ll m=(l+r)/2;
            build(in*2,l,m);
            build(in*2+1,m+1,r);
            ll tro1=0,tro2=0;
            while(tro1<b[in*2].size()||tro2<b[in*2+1].size()){
                if(tro1==b[in*2].size()){
                    b[in].pb(b[in*2+1][tro2]);
                    tro2++;
                }
                else if(tro2==b[in*2+1].size()||b[in*2][tro1]<b[in*2+1][tro2]){
                    b[in].pb(b[in*2][tro1]);
                    tro1++;
                }
                else{
                    b[in].pb(b[in*2+1][tro2]);
                    tro2++;
                }
            }
        }
    }
    ll get(ll in,ll l,ll r,ll l1,ll r1,ll val){
        if(l>r1||r<l1) return INF;
        else if(l>=l1&&r<=r1){
            ll k=lower_bound(all(b[in]),val)-b[in].begin();
            return b[in][k];
        }
        else{
            ll m=(l+r)/2;
            return min(get(in*2,l,m,l1,r1,val),get(in*2+1,m+1,r,l1,r1,val));
        }
    }
    ll get1(ll in,ll l,ll r,ll l1,ll r1,ll val){
        if(l>r1||r<l1) return -INF;
        else if(l>=l1&&r<=r1){
            ll k=lower_bound(all(b[in]),val)-b[in].begin();
            k--;
            if(k<0) return -INF;
            return b[in][k];
        }
        else{
            ll m=(l+r)/2;
            return max(get1(in*2,l,m,l1,r1,val),get1(in*2+1,m+1,r,l1,r1,val));
        }
    }
} mergetree;
ll tinh(ll a,ll b,ll c){
    return max(abs(a-b),max(abs(b-c),abs(a-c)));
}
ll solve1(ll u){
    ll sznode=sz[u]/2;
    ll val1=mergetree.get(1,1,n,id[u],en[u],sznode),val2=mergetree.get1(1,1,n,id[u],en[u],sznode);
    return min(tinh(n-sz[i],sz[i]-val1,val1),tinh(n-sz[i],sz[i]-val2,val2));
}
ll solve2(ll u){
    ll sznode=(n-sz[u])/2;
    ll v=parma[u];
    ll val1=min(mergetree.get(1,1,n,1,id[v]-1,sznode),mergetree.get(1,1,n,en[v]+1,n,sznode)),
       val2=max(mergetree.get1(1,1,n,1,id[v]-1,sznode),mergetree.get1(1,1,n,en[v]+1,n,sznode));
    ll sz1=n-sz[u];
    return min(tinh(sz[u],sz1-val1,val1),tinh(sz[u],sz1-val2,val2));
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("test.inp","r",stdin);
//    freopen("test.out","w",stdout);
    cin>>n;
    for(i=1;i<n;i++){
        ll u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(1,1,1);
    mergetree.build(1,1,n);
    ll ans=INF;
    for(i=2;i<=n;i++){
        ans=min(ans,solve1(i));
        ans=min(ans,solve2(i));
    }
    cout<<ans;
}

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