제출 #1248331

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

papricice

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define ALL(x) (x).begin(), (x).end()
const int MAXN = 200000;
int n;
vector<int> children[MAXN+5];
int sz[MAXN+5];
int best_diff;

// DFS 1: tính sz[u]
void dfs_sz(int u){
    sz[u] = 1;
    for(int v : children[u]){
        dfs_sz(v);
        sz[u] += sz[v];
    }
}

// DFS 2: DSU on Tree, trả về con trỏ đến set của subtree u
set<pair<int,int>>* dfs_dsu(int u){
    // tạo set mới và chèn chính u
    auto *S = new set<pair<int,int>>();
    S->insert(make_pair(sz[u], u));

    // với mỗi con v, merge vào S
    for(int v : children[u]){
        auto *Sv = dfs_dsu(v);
        // luôn gắn tập nhỏ vào tập lớn
        if(S->size() < Sv->size()) swap(S, Sv);
        // merge Sv vào S
        for(auto &p : *Sv){
            S->insert(p);
        }
        delete Sv;
    }

    // sau khi có S chứa mọi (sz[x], x) trong subtree u
    // tìm candidate gần target = sz[u]/2
    int target = sz[u] / 2;
    auto it = S->lower_bound(make_pair(target, -1));
    // kiểm tra it
    vector<set<pair<int,int>>::iterator> cands;
    if(it != S->end()) cands.push_back(it);
    if(it != S->begin()){
        auto it2 = it; --it2;
        cands.push_back(it2);
    }
    // đánh giá từng ứng viên
    for(auto itc : cands){
        int sv = itc->first;
        // phần thứ hai nếu cắt tại (u - itc->second)
        int a = sv;
        int b = sz[u] - sv;
        int c = n - sz[u];
        int mx = max(a, max(b,c));
        int mn = min(a, min(b,c));
        best_diff = min(best_diff, mx - mn);
    }

    return S;
}

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

    cin >> n;
    // đọc vào dạng cây có hướng từ 1 làm gốc
    // giả sử input cho cạnh x-y, ta sẽ thêm y vào children[x] và ngược lại,
    // nhưng cần root cây tại 1; ta chạy thêm một BFS/DFS để xác định parent→child.
    vector<vector<int>> adj(n+1);
    FOR(i,1,n-1){
        int x,y; 
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    // build children[] rooted tại 1
    vector<int> stk; stk.reserve(n);
    vector<bool> seen(n+1,false);
    stk.push_back(1);
    seen[1] = true;
    for(int idx=0; idx < (int)stk.size(); ++idx){
        int u = stk[idx];
        for(int v : adj[u]){
            if(!seen[v]){
                seen[v] = true;
                children[u].push_back(v);
                stk.push_back(v);
            }
        }
    }

    // tính kích thước
    dfs_sz(1);

    // khởi best_diff lớn
    best_diff = n;

    // DSU on tree + tìm best cut thứ 2 cho mỗi u
    auto *unused = dfs_dsu(1);
    delete unused;

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

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