제출 #1248374

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

papricice

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

using ll = long long;

int n;
vector<vector<int>> g;
vector<int> sz;

// 1) DFS tính sz[u]
void dfs_sz(int u, int p) {
    sz[u] = 1;
    for (int v : g[u]) if (v != p) {
        dfs_sz(v, u);
        sz[u] += sz[v];
    }
}

// 2) Tìm một centroid, bắt đầu từ u
int find_centroid(int u, int p) {
    for (int v : g[u]) if (v != p) {
        if (sz[v] > n/2)
            return find_centroid(v, u);
    }
    return u;
}

// 3) Từ một centroid C, lấy tất cả sizes của các cây con kề C
vector<int> get_neighbor_sizes(int C) {
    vector<int> S;
    for (int v : g[C]) {
        // nếu v nằm “phía trên” C thì kích thước là n - sz[C]
        // ngược lại là sz[v]
        if (sz[v] < sz[C]) S.push_back(sz[v]);
        else            S.push_back(n - sz[C]);
    }
    return S;
}

// 4) Tính hiệu gap tốt nhất trong mảng S
int best_gap_from_sizes(vector<int>& S) {
    int m = S.size();
    if (m < 2) return INT_MAX;
    sort(S.begin(), S.end());
    int best = INT_MAX;
    // hai con trỏ
    int i = 0, j = m-1;
    // chúng ta muốn hai giá trị a=S[i], b=S[j] sao cho max(a,b,n-a-b)-min(...) nhỏ nhất
    // nhưng vì m thường rất nhỏ, đơn giản thử mọi cặp i<j
    for (int x = 0; x < m; x++) {
        for (int y = x+1; y < m; y++) {
            ll a = S[x], b = S[y], c = ll(n) - a - b;
            ll mx = max(a, max(b, c));
            ll mn = min(a, min(b, c));
            best = min(best, int(mx - mn));
        }
    }
    return best;
}

int solve_single_centroid(int C) {
    // đảm bảo sz[] đã đúng với toàn cây, và C là centroid
    auto S = get_neighbor_sizes(C);
    return best_gap_from_sizes(S);
}

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

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

    sz.assign(n+1, 0);
    dfs_sz(1, 0);
    int C1 = find_centroid(1, 0);

    // Recompute sz từ C1 để chuẩn cho phần "n - sz[C1]" nếu cần
    dfs_sz(C1, 0);
    int ans = solve_single_centroid(C1);

    // Kiểm tra có thể có 2 centroid không?
    int C2 = -1;
    for (int v : g[C1]) {
        if (sz[v] > n/2) {
            C2 = find_centroid(v, C1);
            break;
        }
    }
    if (C2 != -1 && C2 != C1) {
        // Tái dfs để sz[] đúng với root = C2
        dfs_sz(C2, 0);
        ans = min(ans, solve_single_centroid(C2));
    }

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

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