제출 #1248334

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

papricice

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

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

// 1) Tính sz[u] cho mỗi u bằng DFS không đệ quy
void build_tree() {
    ordsz = 0;
    int top = 0;
    stk[top++] = 1;
    parentArr[1] = 0;
    while (top) {
        int u = stk[--top];
        ord[ordsz++] = u;
        for (int v : adj[u]) {
            if (v == parentArr[u]) continue;
            parentArr[v] = u;
            children[u].push_back(v);
            stk[top++] = v;
        }
    }
    for (int i = ordsz - 1; i >= 0; --i) {
        int u = ord[i];
        sz[u] = 1;
        for (int v : children[u]) {
            sz[u] += sz[v];
        }
    }
}

ll best;

// Phần DISJOINT-CASE: lấy global list allSz, tìm cặp gần 2n/3
void solve_disjoint() {
    vector<int> allSz;
    allSz.reserve(n-1);
    for (int u = 2; u <= n; ++u) {
        allSz.push_back(sz[u]);
    }
    sort(allSz.begin(), allSz.end());
    // two-pointer + binary-search quanh mục tiêu
    for (int i = 0; i < (int)allSz.size(); ++i) {
        ll a = allSz[i];
        ll target = (2LL*n)/3 - a;
        // tìm lower_bound bên phải i
        int lo = i+1, hi = allSz.size()-1, pos = allSz.size();
        while (lo <= hi) {
            int mid = (lo+hi)/2;
            if (allSz[mid] >= target) {
                pos = mid;
                hi = mid-1;
            } else lo = mid+1;
        }
        for (int j = max(i+1, pos-2); j <= min((int)allSz.size()-1, pos+2); ++j) {
            if (j <= i) continue;
            ll b = allSz[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);
        }
    }
}

// Phần ANCESTOR-CASE: small-to-large merge multiset
set<int>* ms[MAXN+1];

void dfs_small_to_large(int u) {
    // bắt đầu: ms[u] có chứa chính sz[u]? Không, chỉ lưu các sz[f] của edges bên dưới u
    ms[u] = new set<int>();
    for (int v : children[u]) {
        dfs_small_to_large(v);
        // merge nhỏ->lớn: ensure ms[u] là lớn nhất
        if (ms[v]->size() > ms[u]->size()) 
            swap(ms[v], ms[u]);
        // gộp tất cả phần tử của ms[v] vào ms[u]
        for (int x : *ms[v]) 
            ms[u]->insert(x);
        delete ms[v];
    }
    // bây giờ chèn cả chính cây con (u->parent) vào: tức kích thước của edge parent–u
    if (u != 1) 
        ms[u]->insert(sz[u]);
    
    // nếu u có parent, thì xem xét cắt (parent–u) và một cạnh bên trong subtree(u):
    if (u != 1) {
        ll S = sz[u], other = n - S;
        // ta muốn pick a trong ms[u] sao cho a ≈ S/2 để chia S thành (a, S-a)
        auto it = ms[u]->lower_bound(S/2);
        for (int rep = 0; rep < 2; ++rep) {
            if (it == ms[u]->end()) {
                if (it == ms[u]->begin()) break;
                --it;
            }
            ll a = *it;
            ll b = S - a;
            ll c = other;
            ll mn = min(a, min(b, c));
            ll mx = max(a, max(b, c));
            best = min(best, mx - mn);
            if (it == ms[u]->begin()) break;
            --it;
        }
    }
}

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

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

    best = LLONG_MAX;
    solve_disjoint();
    dfs_small_to_large(1);

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

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