Submission #978375

#	Time	Username	Problem	Language	Result	Execution time	Memory
978375		alextodoran	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	211 ms	41300 KiB

meetings2

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;
const int LOG_N = 18;

int N;
vector <int> adj[N_MAX + 2];

int parent[N_MAX + 2];
int depth[N_MAX + 2];
int sub[N_MAX + 2];

void dfs (int u) {
    sub[u] = 1;
    for (int v : adj[u]) {
        if (v != parent[u]) {
            parent[v] = u;
            depth[v] = depth[u] + 1;
            dfs(v);
            sub[u] += sub[v];
        }
    }
}

int root;

int anc[LOG_N][N_MAX + 2];

void precalc () {
    for (int u = 1; u <= N; u++) {
        anc[0][u] = parent[u];
    }
    for (int k = 1; k < LOG_N; k++) {
        for (int u = 1; u <= N; u++) {
            anc[k][u] = anc[k - 1][anc[k - 1][u]];
        }
    }
}
int ancestor (int u, int len) {
    for (int k = 0; k < LOG_N; k++) {
        if ((len >> k) & 1) {
            u = anc[k][u];
        }
    }
    return u;
}
int lca (int u, int v) {
    if (depth[u] > depth[v]) {
        u = ancestor(u, depth[u] - depth[v]);
    } else if (depth[v] > depth[u]) {
        v = ancestor(v, depth[v] - depth[u]);
    }
    if (u == v) {
        return u;
    }
    for (int k = LOG_N - 1; k >= 0; k--) {
        if (anc[k][u] != anc[k][v]) {
            u = anc[k][u]; v = anc[k][v];
        }
    }
    return parent[u];
}
int dist (int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

int order[N_MAX + 2];

int answer[N_MAX + 2];

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    for (int u = 1; u <= N; u++) {
        bool centroid = (N - sub[u] <= N / 2);
        for (int v : adj[u]) {
            if (v != parent[u] && sub[v] > N / 2) {
                centroid = false;
                break;
            }
        }
        if (centroid == true) {
            root = u;
            break;
        }
    }
    parent[root] = 0;
    dfs(root);
    precalc();
    iota(order + 1, order + N + 1, 1);
    sort(order + 1, order + N + 1, [&] (const int &u, const int &v) {
        return sub[u] > sub[v];
    });
    for (int k = N / 2, i = 1, x = root, y = root, diam = 0; k >= 1; k--) {
        while (i + 1 <= N && sub[order[i + 1]] >= k) {
            int u = order[++i];
            int dist_ux = dist(u, x);
            int dist_uy = dist(u, y);
            if (dist_ux < dist_uy) {
                swap(dist_ux, dist_uy);
                swap(x, y);
            }
            if (dist_ux > diam) {
                diam = dist_ux;
                y = u;
            }
        }
        answer[k * 2] = diam;
    }
    for (int i = 1; i <= N; i++) {
        cout << ++answer[i] << "\n";
    }

    return 0;
}

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