제출 #932300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
932300		Pannda	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	153 ms	59568 KiB

meetings2

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

struct Tree {
    static int getCentroid(int n, vector<vector<int>> &adj) {
        vector<int> siz(n);
        auto dfs = [&](auto self, int u, int p) -> void {
            siz[u] = 1;
            for (int v : adj[u]) {
                if (v == p) continue;
                self(self, v, u);
                siz[u] += siz[v];
            }
        };
        dfs(dfs, 0, -1);
        auto cen = [&](auto self, int u, int p) -> int {
            for (int v : adj[u]) {
                if (v == p) continue;
                if (siz[v] > n / 2) return self(self, v, u);
            }
            return u;
        };
        return cen(cen, 0, -1);
    }

    vector<int> siz, parent, depth, head;
    Tree(int n, vector<vector<int>> &adj, int root = 0) : siz(n), parent(n), depth(n), head(n) {
        auto dfs = [&](auto self, int u, int p) -> void {
            siz[u] = 1;
            parent[u] = p;
            depth[u] = p == -1 ? 0 : depth[p] + 1;
            for (int v : adj[u]) {
                if (v == p) continue;
                self(self, v, u);
                siz[u] += siz[v];
            }
        };
        dfs(dfs, root, -1);
        auto decompose = [&](auto self, int u, int h) -> void {
            head[u] = h;
            int heavy = -1;
            for (int v : adj[u]) {
                if (v == parent[u]) continue;
                if (heavy == -1 || siz[v] > siz[heavy]) heavy = v;
            }
            if (heavy != -1) self(self, heavy, h);
            for (int v : adj[u]) {
                if (v == parent[u] || v == heavy) continue;
                self(self, v, v);
            }
        };
        decompose(decompose, root, root);
    }

    int getLca(int u, int v) {
        for (; head[u] != head[v]; v = parent[head[v]]) if (depth[head[u]] > depth[head[v]]) swap(u, v);
        if (depth[u] > depth[v]) swap(u, v);
        return u;
    }

    int getDistance(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[getLca(u, v)];
    }

    int getSize(int u) {
        return siz[u];
    }
};

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

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

    vector<int> key = [&]() {
        Tree tree(n, adj, Tree::getCentroid(n, adj));
        vector<int> order(n);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int u, int v) {
            return tree.getSize(u) > tree.getSize(v);
        });
        int d = 0;
        int v0 = order[0], v1 = order[0];
        vector<int> key(n / 2 + 1, 0);
        for (int i = 1; i < n; i++) {
            int u = order[i];
            int v = tree.getDistance(u, v0) > tree.getDistance(u, v1) ? v0 : v1;
            int new_d = tree.getDistance(u, v);
            if (new_d > d) {
                d = new_d;
                v0 = u;
                v1 = v;
            }
            key[tree.getSize(u)] = max(key[tree.getSize(u)], d);
        }
        for (int k = n / 2 - 1; k >= 1; k--) {
            key[k] = max(key[k], key[k + 1]);
        }
        return key;
    }();

    for (int k = 1; k <= n; k++) {
        (k & 1) ? cout << 1 << '\n' : cout << key[k / 2] + 1 << '\n';
    }
}

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