Submission #1248329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248329		dfhdfhdsf	Papričice (COCI20_papricice)	C++20	15 / 110	2 ms	840 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int INF = 1e9;

int n;
vector<vi> adj;
vi tin, tout, sz, euler;
int timer;

// segment-tree
vector<vi> seg;

// DFS1: Euler tour + tính sz[u]
void dfs(int u, int p){
    tin[u] = ++timer;
    euler[timer] = u;
    sz[u] = 1;
    for(int v: adj[u]){
        if(v==p) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
    tout[u] = timer;
}

// build on A[i] = sz[ euler[i] ]
void build(int idx, int l, int r){
    if(l==r){
        seg[idx] = vi{ sz[euler[l]] };
    } else {
        int m=(l+r)>>1;
        build(idx<<1, l, m);
        build(idx<<1|1, m+1, r);
        auto &L=seg[idx<<1], &R=seg[idx<<1|1];
        seg[idx].resize(L.size()+R.size());
        merge(L.begin(),L.end(), R.begin(),R.end(), seg[idx].begin());
    }
}

// trên node idx[l..r], tìm predecessor ≤target
int queryPred(int idx,int l,int r,int L,int R,int target){
    if(R<l||r<L) return -INF;
    if(L<=l&&r<=R){
        auto &v=seg[idx];
        auto it=upper_bound(v.begin(), v.end(), target);
        if(it==v.begin()) return -INF;
        --it;
        return *it;
    }
    int m=(l+r)>>1;
    return max(
        queryPred(idx<<1,l,m,L,R,target),
        queryPred(idx<<1|1,m+1,r,L,R,target)
    );
}

// tìm successor ≥target
int querySucc(int idx,int l,int r,int L,int R,int target){
    if(R<l||r<L) return +INF;
    if(L<=l&&r<=R){
        auto &v=seg[idx];
        auto it=lower_bound(v.begin(), v.end(), target);
        if(it==v.end()) return +INF;
        return *it;
    }
    int m=(l+r)>>1;
    return min(
        querySucc(idx<<1,l,m,L,R,target),
        querySucc(idx<<1|1,m+1,r,L,R,target)
    );
}

// gom cả pred/succ ra vector
void queryClosest(int L, int R, int target, vector<int> &out){
    if(L>R) return;
    int p = queryPred(1,1,n,L,R,target);
    if(p>0) out.push_back(p);
    int s = querySucc(1,1,n,L,R,target);
    if(s<INF) out.push_back(s);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n;
    adj.assign(n+1,{});
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    tin.assign(n+1,0);
    tout.assign(n+1,0);
    sz.assign(n+1,0);
    euler.assign(n+1,0);
    timer=0;
    dfs(1,0);

    seg.assign(4*(n+1),{});
    build(1,1,n);

    int ans = n;
    // xét mỗi u=2..n (cắt cạnh cha–u)
    for(int u=2;u<=n;u++){
        int s = sz[u];
        int r = n - s;

        // --- nested: trong subtree u ---
        if(tin[u]+1 <= tout[u]){
            vector<int> cand;
            int tgt = s/2;
            queryClosest(tin[u]+1, tout[u], tgt, cand);
            for(int a: cand){
                int b = s - a;
                int mx = max({a,b,r});
                int mn = min({a,b,r});
                ans = min(ans, mx - mn);
            }
        }

        // --- disjoint: ngoài subtree u ---
        if(r>0){
            vector<int> cand;
            int tgt = r/2;
            // prefix [1..tin[u]-1]
            queryClosest(1, tin[u]-1, tgt, cand);
            // suffix [tout[u]+1..n]
            queryClosest(tout[u]+1, n, tgt, cand);
            for(int a: cand){
                int b = r - a;
                int mx = max({a,b,s});
                int mn = min({a,b,s});
                ans = min(ans, mx - mn);
            }
        }
    }

    cout<<ans<<"\n";
    return 0;
}

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