Submission #1248372

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

papricice

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

static const int MAXN = 200000;
int n;
vector<int> g[MAXN+1];
int parentArr[MAXN+1], sz[MAXN+1];
int tin[MAXN+1], tout[MAXN+1], dfsTime = 0;
int orderByTin[MAXN+1];

// 1) DFS flatten & tính subtree size
void dfs(int u, int p){
    parentArr[u] = p;
    tin[u] = ++dfsTime;
    orderByTin[dfsTime] = u;
    sz[u] = 1;
    for(int v: g[u]){
        if(v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
    tout[u] = dfsTime;
}

// 2) Segment tree lưu vector<int> đã sort
vector<int> seg[4*MAXN+4];

void build(int idx, int l, int r){
    if(l == r){
        int v = orderByTin[l];
        seg[idx] = { sz[v] };
    } else {
        int mid = (l+r)>>1;
        build(idx<<1, l, mid);
        build(idx<<1|1, mid+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ả về pair{best ≤ target, best ≥ target}, minus là -INF nếu không có, plus là +INF nếu không có.
pair<int,int> query(int idx, int l, int r, int ql, int qr, int target){
    if(ql > r || qr < l) return { -1, n+1 };
    if(ql <= l && r <= qr){
        // binary search trong seg[idx]
        auto &V = seg[idx];
        auto it_hi = lower_bound(V.begin(), V.end(), target);
        int hi = (it_hi==V.end() ? n+1 : *it_hi);
        int lo = -1;
        if(it_hi != V.begin()){
            lo = *prev(it_hi);
        }
        return { lo, hi };
    }
    int mid = (l+r)>>1;
    auto L = query(idx<<1, l, mid, ql, qr, target);
    auto R = query(idx<<1|1, mid+1, r, ql, qr, target);
    // gộp kết quả
    int lo = max(L.first, R.first);
    int hi = min(L.second, R.second);
    return { lo, hi };
}

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

    cin >> n;
    for(int i = 1,u,v; i < n; i++){
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // Chọn root = 1
    dfsTime = 0;
    dfs(1,0);

    build(1,1,n);

    int answer = n; // ban đầu đặt lớn
    // Duyệt mọi đỉnh != root (ứng với cắt cạnh (u, parent[u]))
    for(int u = 2; u <= n; u++){
        int T = sz[u];
        int X = n - T;

        // 1) cắt lần 2 trong thành phần subtree u: đoạn [tin[u], tout[u]]
        {
            int target = T/2;
            auto pr = query(1,1,n, tin[u], tout[u], target);
            for(int s: {pr.first, pr.second}){
                if(s <= 0 || s >= T) continue;
                int a = s, b = T - s, c = X;
                int mx = max({a,b,c}), mn = min({a,b,c});
                answer = min(answer, mx - mn);
            }
        }

        // 2) cắt lần 2 trong thành phần ngoài subtree u: 
        //    hai đoạn [1, tin[u]-1] và [tout[u]+1, n]
        {
            int target = X/2;
            // [1, tin[u]-1]
            if(tin[u] > 1){
                auto pr = query(1,1,n, 1, tin[u]-1, target);
                for(int s: {pr.first, pr.second}){
                    if(s <= 0 || s >= X) continue;
                    int a = s, b = X - s, c = T;
                    int mx = max({a,b,c}), mn = min({a,b,c});
                    answer = min(answer, mx - mn);
                }
            }
            // [tout[u]+1, n]
            if(tout[u] < n){
                auto pr = query(1,1,n, tout[u]+1, n, target);
                for(int s: {pr.first, pr.second}){
                    if(s <= 0 || s >= X) continue;
                    int a = s, b = X - s, c = T;
                    int mx = max({a,b,c}), mn = min({a,b,c});
                    answer = min(answer, mx - mn);
                }
            }
        }
    }

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

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