Submission #1283333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283333		diep38	Papričice (COCI20_papricice)	C++20	110 / 110	201 ms	26492 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
#define int long long

#define pb push_back
#define irs insert
#define ed "\n"
#define fi first
#define se second
#define pi pair<int,int>
#define pii pair<int,pair<int,int>>
#define fis(i,a,b) for(int i=a;i<=b;++i)
#define fl(i,a,b) for(int i=a;i>=b;--i)
const int mod=1e9+7;
const int Mdem=998244353;
const int LOG=19;
const int base=31;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define gay(a) freopen(a".inp","r",stdin),freopen(a".out","w",stdout)
template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}

template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}
void add(int &a, int b) {   a += b; if (a >= mod)   a -= mod;   }
void sub(int &a, int b) {   a -= b; if (a <  0)     a += mod;   }
vector<int> adj[200005];
int sta[200005],fin[200005];
int n;
int par[200005];
int cnt=0;
int S[200005];
void dfs(int u)
{
    sta[u]=++cnt;
    for(int v:adj[u]){
        if(v==par[u]) continue;
        par[v]=u;
        dfs(v);
    }
    fin[u]=cnt;
    S[u]=fin[u]-sta[u]+1;
}
bool check(int u,int v) // ktra u co phai to ten v hay khong
{
    return (sta[u]<=sta[v] && sta[v]<=fin[u]);
}
set<int> tt,ntt;
int ans=1e9;
void dfs1(int u){
    if(u!=1) tt.irs(S[u]);
    for(int v:adj[u]){
        if(v==par[u]) continue;
        par[v]=u;
        auto lower=tt.lower_bound((n+S[v])/2);
        if(lower!=tt.end()){
            int x=*lower;
            ans=min(ans, max({S[v],x-S[v],n-x }) - min({S[v],x-S[v],n-x }) );
        }
        if(lower!=tt.begin()){
            --lower;
            int xx=*lower;
            ans=min(ans, max({S[v],xx-S[v],n-xx }) - min({S[v],xx-S[v],n-xx}) );
        }
        auto lower1=ntt.lower_bound((n-S[v])/2);
        if(lower1!=ntt.end()){
            int x1=*lower1;
            ans=min(ans, max({S[v],x1,n-x1-S[v]}) - min({S[v],x1,n-x1-S[v]}) );
        }
        if(lower1!=ntt.begin()){
            --lower1;
            int x2=*lower1;
            ans=min(ans, max({S[v],x2,n-x2-S[v]}) - min({S[v],x2,n-x2-S[v]}) );
        }
        dfs1(v);
    }
    tt.erase(S[u]);
    ntt.irs(S[u]);
}
signed main(){
    fast;
    cin>>n;
    fis(i,1,n-1)
    {
        int x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for(int i=1;i<=n;++i) sort(adj[i].begin(),adj[i].end());
    dfs(1);
    memset(par,0,sizeof par);
    dfs1(1);

    cout<<ans;
    return 0;
}

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