제출 #1248330

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248330		dfhdfhdsf	Papričice (COCI20_papricice)	C++20	15 / 110	2 ms	836 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;
vector<vi> st; // segment tree: mỗi node giữ vector đã sort

// DFS tính tin/tout và 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){
        dfs(v, u);
        sz[u] += sz[v];
    }
    tout[u] = timer;
}

// Xây segment-tree trên mảng A[i] = sz[euler[i]]
void build(int node, int l, int r){
    if(l == r){
        st[node] = vi(1, sz[euler[l]]);
    } else {
        int m = (l + r) >> 1;
        build(node<<1, l, m);
        build(node<<1|1, m+1, r);
        st[node].resize(st[node<<1].size() + st[node<<1|1].size());
        merge(st[node<<1].begin(), st[node<<1].end(),
              st[node<<1|1].begin(), st[node<<1|1].end(),
              st[node].begin());
    }
}

// Tìm predecessor = max{x ≤ target} trong đoạn [L,R], hoặc -INF nếu không có
int queryPred(int node, int l, int r, int L, int R, int target){
    if(R < l || r < L) return -INF;
    if(L <= l && r <= R){
        auto &v = st[node];
        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(node<<1,   l,   m, L, R, target),
      queryPred(node<<1|1, m+1, r, L, R, target)
    );
}

// Tìm successor = min{x ≥ target} trong đoạn [L,R], hoặc +INF nếu không có
int querySucc(int node, int l, int r, int L, int R, int target){
    if(R < l || r < L) return +INF;
    if(L <= l && r <= R){
        auto &v = st[node];
        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(node<<1,   l,   m, L, R, target),
      querySucc(node<<1|1, m+1, r, L, R, target)
    );
}

// Truy vấn trong [L,R] cả pred & succ gần target
void queryClosest(int L, int R, int target, vector<int>& out){
    if(L > R) return;
    int p = queryPred(1,1,n,L,R,target);
    int s = querySucc(1,1,n,L,R,target);
    if(p != -INF) out.push_back(p);
    if(s != +INF) out.push_back(s);
}

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

    cin >> n;
    adj.assign(n+1, {});
    for(int i=0;i<n-1;i++){
        int x,y;
        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);

    // khởi tạo segment-tree
    st.assign(4*(n+2), vi());
    build(1,1,n);

    int answer = n; // khởi gán lớn
    // duyệt từng u làm vị trí cắt thứ nhất
    for(int u = 1; u <= n; u++){
        int su = sz[u];
        int R = n - su;
        // ----- CASE A: nested (cắt thứ hai trong subtree của u) -----
        if(tin[u]+1 <= tout[u]){
            vector<int> cands;
            int target = su / 2;
            queryClosest(tin[u]+1, tout[u], target, cands);
            for(int sv : cands){
                int a = sv;
                int b = su - sv;
                int c = R;
                int mx = max({a,b,c});
                int mn = min({a,b,c});
                answer = min(answer, mx - mn);
            }
        }
        // ----- CASE B: disjoint (cắt thứ hai ngoài subtree) -----
        if(R > 0){
            vector<int> cands;
            int target = R / 2;
            // hai khoảng [1, tin[u]-1] và [tout[u]+1, n]
            if(1 <= tin[u]-1)
                queryClosest(1, tin[u]-1, target, cands);
            if(tout[u]+1 <= n)
                queryClosest(tout[u]+1, n, target, cands);
            for(int sv : cands){
                int a = su;
                int b = sv;
                int c = R - sv;
                int mx = max({a,b,c});
                int 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