Submission #1294721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294721		vivkostov	Meetings 2 (JOI21_meetings2)	C++20	4 / 100	6 ms	1100 KiB

meetings2

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

int n;
const int MAXN = 200005;
vector<int> v[MAXN];
int used[MAXN]; // used for BFS distances (1-based)
int a[MAXN], b[MAXN];
int lead, bot;
int psub[MAXN]; // sizes of hanging subtrees per diameter node
int ind[MAXN];
vector<int> dp[MAXN];
int otg[MAXN];
int mid1, mid2;

void speed() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

void bfs(int beg) {
    for (int i = 1; i <= n; ++i) used[i] = 0;
    queue<int> q;
    used[beg] = 1;
    q.push(beg);
    while (!q.empty()) {
        int w = q.front(); q.pop();
        for (int nb : v[w]) {
            if (!used[nb]) {
                used[nb] = used[w] + 1;
                q.push(nb);
            }
        }
    }
}

void clea(int beg, int par) {
    used[beg] = 0;
    for (int nb : v[beg]) {
        if (nb == par) continue;
        clea(nb, beg);
    }
}

void prec() {
    int to = bot, nex = 0, par = 0;
    while (to != lead) {
        for (int nb : v[to]) {
            if (nb == par) continue;
            if (used[nb] != used[to] - 1) {
                clea(nb, to);
            } else nex = nb;
        }
        par = to;
        to = nex;
    }
}

void calc_subsizes(int beg, int leadnode, int par) {
    psub[leadnode]++;
    for (int nb : v[beg]) {
        if (!used[nb] && nb != par) calc_subsizes(nb, leadnode, beg);
    }
}

int check_count(int mi) {
    int br = 0;
    for (int i = 1; i <= n; ++i) {
        if (used[i] && used[i] <= mi) br += psub[i];
    }
    return br;
}

void find_mid() {
    int L = 1, R = used[bot], mi;
    while (L <= R) {
        mi = (L + R) / 2;
        if (check_count(mi) >= (n + 1) / 2) R = mi - 1;
        else L = mi + 1;
    }
    // compute safe values for check(L) and check(L-1)
    int cL = check_count(L);
    int cLm1 = (L - 1 >= 0 ? check_count(L - 1) : 0);

    int dist1, dist2;
    if (min(cL, n - cL) >= min(cLm1, n - cLm1)) {
        dist1 = L;
        dist2 = L + 1;
    } else {
        dist1 = L - 1;
        dist2 = L;
    }
    // find nodes with used == dist1 / dist2 (if any)
    mid1 = -1; mid2 = -1;
    for (int i = 1; i <= n; ++i) {
        if (used[i] == dist1 && mid1 == -1) mid1 = i;
        if (used[i] == dist2 && mid2 == -1) mid2 = i;
    }
    // if not found (edge cases), fall back to endpoints near center of diameter
    if (mid1 == -1) mid1 = lead;
    if (mid2 == -1) mid2 = bot;
}

void get_dp(int beg, int par, int level) {
    ind[beg] = beg;
    // gather children excluding parent
    vector<int> children;
    for (int nb : v[beg]) if (nb != par) children.push_back(nb);

    if (children.empty()) {
        // real leaf
        dp[beg].clear();
        dp[beg].push_back(level);
        ind[beg] = beg;
        return;
    }

    // process children
    for (int child : children) {
        get_dp(child, beg, level + 1);
        // pick the child with largest dp vector as representative
        if (dp[ind[beg]].size() < dp[ind[child]].size()) {
            ind[beg] = ind[child];
        }
    }

    // Now merge other children into dp[ind[beg]] (small-to-large)
    int sum = 1;
    for (int child : children) {
        if (ind[child] == ind[beg]) continue;
        int sz = (int)dp[ind[child]].size();
        sum += sz;
        // dp[ind[beg]] should be >= dp[ind[child]] in size because we chose largest as ind[beg]
        for (int j = 0; j < sz; ++j) {
            if (j < (int)dp[ind[beg]].size()) {
                otg[j] = max(otg[j], dp[ind[beg]][j] + dp[ind[child]][j] - level * 2 + 1);
                dp[ind[beg]][j] = max(dp[ind[beg]][j], dp[ind[child]][j]);
            }
        }
    }
    // extend dp[ind[beg]] by 'sum' copies of level (as original logic intended)
    for (int i = 1; i <= sum; ++i) dp[ind[beg]].push_back(level);
}

int main() {
    speed();
    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) {
        v[i].clear();
        used[i] = 0;
        psub[i] = 0;
        ind[i] = 0;
        dp[i].clear();
        otg[i] = 0;
    }
    for (int i = 1; i < n; ++i) {
        cin >> a[i] >> b[i];
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }

    // find diameter endpoints
    bfs(1);
    int ma = 0;
    for (int i = 1; i <= n; ++i) {
        if (used[i] > ma) { ma = used[i]; lead = i; }
    }
    bfs(lead);
    ma = 0;
    for (int i = 1; i <= n; ++i) {
        if (used[i] > ma) { ma = used[i]; bot = i; }
    }

    // prune non-diameter subtrees (used[] marks diameter nodes with distances)
    prec();

    // compute subtree sizes hanging from each diameter node
    for (int i = 1; i <= n; ++i) {
        if (used[i]) {
            // use i as root of its hanging subtree, accumulate count into psub[i]
            calc_subsizes(i, i, 0);
        }
    }

    // choose mid nodes on diameter
    find_mid();

    // clear dp/otg again to be safe (they were zeroed initially)
    for (int i = 1; i <= n; ++i) {
        dp[i].clear();
        ind[i] = 0;
    }
    // compute dp from both midpoints
    // If mid1 == mid2, call once
    if (mid1 == mid2) {
        get_dp(mid1, 0, 1);
    } else {
        get_dp(mid1, mid2, 1);
        get_dp(mid2, mid1, 1);
    }

    // fill default for otg (fallback 1 where no better found)
    for (int i = 0; i <= n; ++i) if (!otg[i]) otg[i] = 1;

    // prepare representative indices for mid1/mid2
    int rep1 = ind[mid1];
    int rep2 = ind[mid2];

    // output answers: one per line
    for (int k = 1; k <= n; ++k) {
        if (k % 2 == 1) {
            cout << 1 << '\n';
        } else {
            int idx = k / 2 - 1;
            int s1 = (rep1 ? (int)dp[rep1].size() : 0);
            int s2 = (rep2 ? (int)dp[rep2].size() : 0);
            int ans;
            if (idx >= 0 && min(s1, s2) > idx) {
                ans = max(dp[rep1][idx] + dp[rep2][idx], otg[idx]);
            } else {
                // take whichever has the idx (if any) else use otg
                int val1 = (idx >= 0 && s1 > idx ? dp[rep1][idx] : 0);
                int val2 = (idx >= 0 && s2 > idx ? dp[rep2][idx] : 0);
                ans = max(otg[idx], max(val1, val2));
            }
            cout << ans << '\n';
        }
    }

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80