제출 #605008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605008		elkernos	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	3 ms	520 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    vector<int> sub(n + 1);
    function<void(int, int)> subsz = [&](int u, int p) {
        sub[u] = 1;
        for(int to : g[u]) {
            if(to == p) {
                continue;
            }
            subsz(to, u);
            sub[u] += sub[to];
        }
    };
    subsz(1, 1);
    function<int(int, int, int)> getcen = [&](int u, int p, int d) {
        for(int to : g[u]) {
            if(to == p) {
                continue;
            }
            if(sub[to] > d / 2) {
                return getcen(to, u, sub[to]);
            }
        }
        return u;
    };
    int root = getcen(1, 1, n);
    vector<vector<int>> up(20, vector<int>(n + 1));
    vector<int> dep(n + 1);
    function<void(int, int)> prep = [&](int u, int p) {
        for(int to : g[u]) {
            if(to == p) {
                continue;
            }
            dep[to] = dep[u] + 1;
            up[0][to] = u;
            sub[to] = 1;
            prep(to, u);
            sub[u] += sub[to];
        }
    };
    up[0][root] = root;
    sub[root] = 1;
    prep(root, root);
    vector<vector<int>> gg(n / 2 + 1);
    for(int i = 1; i <= n; i++) {
        if(i == root) {
            continue;
        }
        gg[sub[i]].emplace_back(i);
    }
    for(int i = 1; i < 20; i++) {
        for(int j = 1; j <= n; j++) {
            up[i][j] = up[i - 1][up[i - 1][j]];
        }
    }
    auto jump = [&](int u, int d) {
        for(int i = 0; d; i++) {
            if(d % 2) {
                u = up[i][u];
            }
            d /= 2;
        }
        return u;
    };
    auto lca = [&](int a, int b) {
        if(dep[a] > dep[b]) {
            swap(a, b);
        }
        b = jump(b, dep[b] - dep[a]);
        if(a == b) {
            return a;
        }
        for(int i = 19; i >= 0; i--) {
            if(up[i][a] != up[i][b]) {
                a = up[i][a];
                b = up[i][b];
            }
        }
        return up[0][a];
    };
    auto d = [&](int a, int b) {
        return dep[a] + dep[b] - dep[lca(a, b)];
    };
    int a = root, b = root, c = 0;
    vector<int> ans(n / 2 + 1);
    for(int i = n / 2; i >= 1; i--) {
        for(int j : gg[i]) {
            int one = d(a, j);
            int two = d(b, j);
            if(one > c) {
                b = j;
                c = one;
            }
            else if(two > c) {
                a = j;
                c = two;
            }
        }
        ans[i] = c;
    }
    for(int i = 1; i <= n; i++) {
        cout << (i % 2 ? 1 : ans[i / 2] + 1) << '\n';
    }
}

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