제출 #1248332

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248332		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, children;
vi tin, tout, euler, sz, B;
int timer;
int ans;

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

// bests[u] sẽ chứa 1–2 ứng viên a' cho case disjoint của u
vector<vector<int>> bests;

// --- 2) Forward scan cho prefix [1..tin[u]-1], loại trừ root ---
void forward_scan(){
    multiset<int> st;
    vector<vector<int>> atTin(n+1);
    for(int u = 2; u <= n; u++)
        atTin[tin[u]].push_back(u);

    for(int i = 1; i <= n; i++){
        // xử lý disjoint-prefix cho mọi u với tin[u] == i
        for(int u: atTin[i]){
            int r = n - sz[u];
            int target = r / 2;
            if(!st.empty()){
                auto it = st.lower_bound(target);
                if(it != st.end()) bests[u].push_back(*it);
                if(it != st.begin()){
                    --it;
                    bests[u].push_back(*it);
                }
            }
        }
        // chèn B[i] = sz[euler[i]] nếu euler[i] != 1
        if(euler[i] != 1)
            st.insert(B[i]);
    }
}

// --- 3) Backward scan cho suffix [tout[u]+1..n], loại trừ root ---
void backward_scan(){
    multiset<int> st;
    vector<vector<int>> atTout(n+2);
    for(int u = 2; u <= n; u++)
        atTout[tout[u]].push_back(u);

    for(int i = n; i >= 1; i--){
        for(int u: atTout[i]){
            int r = n - sz[u];
            int target = r / 2;
            if(!st.empty()){
                auto it = st.lower_bound(target);
                if(it != st.end()) bests[u].push_back(*it);
                if(it != st.begin()){
                    --it;
                    bests[u].push_back(*it);
                }
            }
        }
        if(euler[i] != 1)
            st.insert(B[i]);
    }
}

// --- 4) DSU-on-Tree để tìm case nested và kết hợp disjoint từ bests[u] ---
set<int>* dfs_dsu(int u){
    // S chứa sz[x] cho tất cả x trong subtree(u), x != u
    auto *S = new set<int>();
    for(int v: children[u]){
        auto *Sv = dfs_dsu(v);
        if(S->size() < Sv->size()) swap(S, Sv);
        // merge Sv vào S
        for(int x: *Sv) 
            S->insert(x);
        delete Sv;
    }

    // --- case nested: tìm a trong S sao cho a ≈ sz[u]/2 ---
    if(!S->empty()){
        int s = sz[u], r = n - s;
        int target = s / 2;
        auto it = S->lower_bound(target);
        vector<int> cands;
        if(it != S->end()) cands.push_back(*it);
        if(it != S->begin()){
            --it;
            cands.push_back(*it);
        }
        for(int a: cands){
            int b = s - a;
            int mx = max({a,b,r});
            int mn = min({a,b,r});
            ans = min(ans, mx - mn);
        }
    }

    // --- case disjoint: dùng bests[u] từ forward/backward ---
    int s = sz[u];
    for(int a: bests[u]){
        int b = (n - s) - a;
        int c = s;
        int mx = max({a,b,c});
        int mn = min({a,b,c});
        ans = min(ans, mx - mn);
    }

    // thêm sz[u] vào S để các ancestor có thể dùng
    S->insert(sz[u]);
    return S;
}

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

    cin >> n;
    adj.assign(n+1, {});
    children.assign(n+1, {});
    tin.assign(n+1,0);
    tout.assign(n+1,0);
    euler.assign(n+1,0);
    sz.assign(n+1,0);
    B.assign(n+1,0);
    bests.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);
    }

    timer = 0;
    dfs1(1, 0);

    // xây B[i] = sz[euler[i]]
    for(int i = 1; i <= n; i++)
        B[i] = sz[euler[i]];

    // thu disjoint‑candidates
    forward_scan();
    backward_scan();

    ans = INF;
    // DSU‑on‑Tree tổng hợp nested & disjoint
    auto *rootSet = dfs_dsu(1);
    delete rootSet;

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

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