제출 #1248333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248333		dfhdfhdsf	Papričice (COCI20_papricice)	C++20	0 / 110	5 ms	9796 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for(int i=(a); i>=(b); --i)
#define ALL(x) (x).begin(), (x).end()
#define isz(x) int((x).size())

static const int MAXN = 200000;
int n;
vector<int> adj[MAXN+1], children[MAXN+1];
int parentArr[MAXN+1];
int sz[MAXN+1];
int stk[MAXN+1], ord[MAXN+1], ordsz;

void solve(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    FOR(i,1,n) {
        adj[i].clear();
        children[i].clear();
    }
    FOR(i,1,n-1){
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    // -- dựng parent + thứ tự post-order không đệ quy --
    ordsz = 0;
    int top = 0;
    stk[top++] = 1;
    parentArr[1] = 0;
    // first: tạo thứ tự preorder lưu vào ord
    while(top){
        int u = stk[--top];
        ord[ordsz++] = u;
        for(int v: adj[u]){
            if(v == parentArr[u]) continue;
            parentArr[v] = u;
            stk[top++] = v;
            children[u].push_back(v);
        }
    }
    // rồi duyệt ngược ord để tính sz[u]
    FORD(idx, ordsz-1, 0){
        int u = ord[idx];
        sz[u] = 1;
        for(int v: children[u]){
            sz[u] += sz[v];
        }
    }

    ll best = LLONG_MAX;
    // xét mỗi nút u
    FOR(u,1,n){
        // gom các kích thước "nhánh" quanh u
        vector<int> vals;
        vals.reserve(1 + children[u].size());
        // nhánh lên trên nếu có
        if(parentArr[u] != 0){
            vals.push_back(n - sz[u]);
        }
        // nhánh mỗi con v
        for(int v: children[u]){
            vals.push_back(sz[v]);
        }
        int m = isz(vals);
        if(m < 2) continue;
        sort(ALL(vals));
        // với mỗi i, tìm j>i sao cho vals[j] gần target = 2n/3 - vals[i]
        for(int i = 0; i < m; ++i){
            ll a = vals[i];
            ll target = (2LL*n)/3 - a;
            // tìm vị trí lower_bound trong phần [i+1..m)
            int lo = i+1, hi = m-1, pos = m;
            while(lo <= hi){
                int mid = (lo+hi)/2;
                if(vals[mid] >= target){
                    pos = mid;
                    hi = mid-1;
                } else lo = mid+1;
            }
            // kiểm tra vài ứng viên quanh pos
            for(int j = max(i+1, pos-1); j <= min(m-1, pos+1); ++j){
                if(j <= i) continue;
                ll b = vals[j];
                ll c = n - a - b;
                ll mn = min(a, min(b, c));
                ll mx = max(a, max(b, c));
                best = min(best, mx - mn);
            }
        }
    }

    cout << best << "\n";
}

int main(){
    solve();
    return 0;
}

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