Submission #1117988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117988		Sharky	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	428 ms	64072 KiB

meetings2

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

#define int long long
const int N = 2e5 + 10;
const int LG = 18;

int n, sz[N], a, b, ans[N], dep[N], lift[N][LG];
vector<int> adj[N], node[N];

int dfs(int u, int p) {
    sz[u] = 1;
    int mx = 0, res = -1;
    for (int v : adj[u]) {
        if (v == p) continue;
        lift[v][0] = u;
        res = max(res, dfs(v, u));
        sz[u] += sz[v];
        mx = max(mx, sz[v]);
    }
    mx = max(mx, n - sz[u]);
    if (mx <= n / 2) return u;
    return res;
}

void comp(int u, int p) {
    for (int i = 1; i < LG; i++) lift[u][i] = lift[lift[u][i-1]][i-1];
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        lift[v][0] = u;
        dep[v] = dep[u] + 1;
        comp(v, u);
        sz[u] += sz[v];
    }
}

int jump(int sta, int di) {
    for (int i = LG - 1; i >= 0; i--) if (di & (1 << i)) sta = lift[sta][i];
    return sta;
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    x = jump(x, dep[x] - dep[y]);
    if (x == y) return x;
    for (int i = LG - 1; i >= 0; i--) {
        int xt = lift[x][i], yt = lift[y][i];
        if (xt != yt) x = xt, y = yt;
    }
    return lift[x][0];
}

int dist(int u, int v) {
    return dep[u] + dep[v] - dep[lca(u, v)] * 2;
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int c = dfs(1, -1);
    dfs(c, -1);
    lift[c][0] = c;
    comp(c, -1);
    for (int i = 1; i <= n; i++) node[sz[i]].push_back(i);
    for (int i = n; i >= 1; i--) {
        if (i % 2) continue;
        ans[i] = ans[i + 2];
        for (auto& x : node[i/2]) {
            ans[i] = max(ans[i], dep[x]);
            if (!a) a = b = x;
        }
        for (auto& x : node[i/2]) {
            int dax = dist(a, x);
            int dbx = dist(b, x);
            int dab = dist(a, b);
            if (dax >= dab && dax >= dbx) b = x;
            else if (dbx >= dab && dbx >= dax) a = x;
        }
        ans[i] = max(ans[i], dist(a, b));
    }
    for (int i = 1; i <= n; i++) cout << ans[i] + 1 << '\n';
}

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