Submission #896112

#	Time	Username	Problem	Language	Result	Execution time	Memory
896112		juliany2	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	4 ms	12376 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 2e5 + 7;
int n;
vector<int> adj[N], s[N];
bool col[N];
int sz[N], dist[N], bst;
int ans[N];

void dfs(int v = 1, int p = 0) {
    sz[v] = 1;
    for (int u : adj[v]) {
        if (u != p) {
            dfs(u, v);
            sz[v] += sz[u];
        }
    }

    s[sz[v]].push_back(v);
}

void calc(int v = 1, int p = 0) {
    if (col[v]) {
        dist[v] = max(dist[v], 0);
        bst = max(bst, dist[v] + 1);
    }

    for (int u : adj[v]) {
        if (u != p) {
            dist[u] = max(dist[u], dist[v] + 1);
            calc(u, v);
        }
    }
}

int upd(int s) {
    col[s] = 1;
    memset(dist, -1, sizeof(dist));

    int ret = 0;

    queue<int> q;
    q.push(s);
    dist[s] = 0;

    while (q.size()) {
        int v = q.front();
        q.pop();

        if (col[v])
            ret = max(ret, dist[v] + 1);

        for (int u : adj[v]) {
            if (dist[u] < 0) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }

    return ret;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    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);
    }

    dfs();

    for (int i = n; i >= 1; i--) {
        if (i % 2)
            ans[i] = 1;
        else {
            for (int x : s[i / 2])
                ans[i] = max(ans[i], upd(x));
            for (int x : s[n - i / 2])
                ans[i] = max(ans[i], upd(x));

            fill(dist + 1, dist + n + 1, (int) -1e9);
            bst = 0;
            calc();

            ans[i] = max(ans[i], bst + 1);
        }
    }

    for (int i = 1; i <= n; i++)
        cout << ans[i] << '\n';

    return 0;
}

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