Submission #1311693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311693		hanguyendanghuy	Papričice (COCI20_papricice)	C++20	110 / 110	146 ms	36984 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,ans,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;
}
multiset<ll> se1,se2;
void calc(ll a,ll b,ll c){
    ans=min(ans,max({a,b,c})-min({a,b,c}));
}
void tinh(ll u){
    auto it=se1.lower_bound((n+sz[u])/2);
    if(it!=se1.end()){
        ll val=*it;
        calc(n-val,val-sz[u],sz[u]);
    }
    if(it!=se1.begin()){
        it--;
        ll val=*it;
        calc(n-val,val-sz[u],sz[u]);
    }
}
void tinh1(ll u){
    auto it=se2.lower_bound((n-sz[u])/2);
    if(it!=se2.end()){
        ll val=*it;
        calc(n-val-sz[u],sz[u],val);
    }
    if(it!=se2.begin()){
        it--;
        ll val=*it;
        calc(n-val-sz[u],sz[u],val);
    }
}
void solve(ll u,ll pre){
    tinh(u);
    tinh1(u);
    se1.insert(sz[u]);
    for(ll x:adj[u]){
        if(x==pre) continue;
        solve(x,u);
    }
    se1.erase(se1.find(sz[u]));
    se2.insert(sz[u]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    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);
    ans=INF;
    solve(1,1);
    cout<<ans;
}

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