제출 #1248337

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

papricice

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

const int MAXN = 200000 + 5;

int n;
vector<int> g[MAXN];
int sub[MAXN], heavy[MAXN], parent_[MAXN];
int tin[MAXN], tout[MAXN], euler_[MAXN], timer_ = 0;

long long answer = LLONG_MAX;

/* --------- 1st DFS : size, heavy child, euler order --------- */
void dfs_sz(int u, int p = 0)
{
    parent_[u] = p;
    sub[u] = 1;
    int mx = 0;
    tin[u] = ++timer_;
    euler_[timer_] = u;

    for (int v : g[u])
        if (v != p)
        {
            dfs_sz(v, u);
            sub[u] += sub[v];
            if (sub[v] > mx) mx = sub[v], heavy[u] = v;
        }
    tout[u] = timer_;
}

/* multiset chứa kích thước các cây con hiện tại                */
/* cnt[x] – số lần x xuất hiện (hỗ trợ remove nhanh)             */
multiset<int> S;
vector<int> bucket[MAXN];   // bucket[id] = list size trong subtree id

void add_subtree(int u)
{
    // đi qua euler để lấy toàn bộ cạnh khác gốc trong cây con u
    for (int t = tin[u]; t <= tout[u]; ++t)
    {
        int v = euler_[t];
        if (v == 1) continue;                 // đỉnh gốc không có cạnh đi lên
        S.insert(sub[v]);
        bucket[u].push_back(sub[v]);
    }
}
void remove_subtree(int u)
{
    for (int x : bucket[u]) S.erase(S.find(x));
}

/* tìm giá trị trong multiset S gần nhất với target */
inline void try_update(long long A, long long B, long long t)
{
    long long x,y,z, diff;
    /* 2 công thức */
    /* 1. nested  : t , A-t , B */
    x = t; y = A - t; z = B;
    diff = max({x,y,z}) - min({x,y,z});
    answer = min(answer, diff);

    /* 2. disjoint: A , t , B-t (chỉ hợp lệ khi B>t , nhưng
       nếu B==t hoặc B<t chênh lệch càng lớn → không thể nhỏ hơn
       lời giải hiện tại nên không cần ràng buộc)          */
    x = A; y = t; z = B - t;
    if (z>0) {
        diff = max({x,y,z}) - min({x,y,z});
        answer = min(answer, diff);
    }
}

void query(multiset<int> &M, long long target,
           long long A, long long B)
{
    if (M.empty()) return;
    auto it = M.lower_bound((int)target);
    if (it != M.end())   try_update(A,B,*it);
    if (it != M.begin()) try_update(A,B,*prev(it));
}

/* --------- 2nd DFS : DSU on tree ----------------------------- */
void dfs_dsu(int u, bool keep)
{
    /* process light children first */
    for (int v : g[u])
        if (v != parent_[u] && v != heavy[u])
            dfs_dsu(v, false);

    /* heavy child with keep = true */
    if (heavy[u]) dfs_dsu(heavy[u], true);

    /* add every light child’s subtree into S */
    for (int v : g[u])
        if (v != parent_[u] && v != heavy[u])
        {
            add_subtree(v);
        }

    /* add current node’s own edge (if not root) */
    if (u != 1) {
        S.insert(sub[u]);
    }

    /* ------------  TÍNH KẾT QUẢ  ---------------- */
    if (u != 1)                // chỉ các cạnh khác rễ mới cắt được
    {
        long long A = sub[u];
        long long B = n - A;

        /* 1. cạnh thứ hai bên TRONG cây con u  */
        // mọi kích thước trong subtree u ngoại trừ sub[u] chính là
        //   bucket[u] + mọi bucket[light child] + bucket[heavy child] (đã ở S)
        // để có "inside", ta chỉ cần nhìn vào S rồi xoá phần Outside
        // --> dùng riêng multiset insideSub (đã được build ở bước add) :
        multiset<int> inside;
        for (int v : g[u])
            if (v != parent_[u])
                inside.insert(sub[v]);      // cạnh ngay dưới u
        if (!inside.empty())
        {
            long long tgt = A / 2;
            query(inside, tgt, A, B);
        }

        /* 2. cạnh thứ hai nằm bên NGOÀI cây con u
              => chính là multiset S sau khi ta đã add toàn bộ subtree u
                 ngoại trừ sub[u] đã ở trong S.
        */
        long long tgt2 = B / 2;
        multiset<int> outside = S;
        // loại bỏ toàn bộ subtree u (đã add ở thân hàm) để lại phần ngoài
        remove_subtree(u);
        if (u != 1) outside.erase(outside.find(sub[u]));
        query(outside, tgt2, A, B);
        add_subtree(u);                 // khôi phục
    }

    /* ---------------------------------------------------------- */
    if (!keep)
    {
        remove_subtree(u);
        if (u != 1) S.erase(S.find(sub[u]));
    }
}

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

    if (!(cin >> n)) return 0;
    for (int i = 1; i < n; ++i)
    {
        int x,y; cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs_sz(1);

    add_subtree(1);   // đưa toàn bộ cạnh vào multiset S
    dfs_dsu(1, true);

    cout << answer << '\n';
    return 0;
}

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