Submission #564160

#	Time	Username	Problem	Language	Result	Execution time	Memory
564160		nikatamliani	Meetings 2 (JOI21_meetings2)	C++14	20 / 100	390 ms	5528 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> g[N];
int n, sub[N], ans[N], depth[N], anc[N];
void dfs(int x, int p, int root) {
    depth[x] = depth[p] + 1;
    sub[x] = 1;
    if (p == root) {
        anc[x] = x;
    } else if (x != root) {
        anc[x] = anc[p];
    }
    for (int to : g[x]) {
        if (to != p) {
            dfs(to, x, root);
            sub[x] += sub[to];
        }
    }
}
int main() {
    cin >> n;
    if (n > 5000) {
        return 0;
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int root = 1; root <= n; ++root) {
        dfs(root, 0, root);
        for (int i = 1; i <= n; ++i) {
            int v = min(sub[i], n - sub[anc[i]]);
            ans[v] = max(ans[v], depth[i]);
        }
    }
    for (int i = n; i >= 1; --i) {
        ans[i] = max(ans[i], ans[i + 1]);
    }
    for (int i = 1; i <= n; ++i) {
        if (i % 2) {
            cout << 1 << '\n';
        } else {
            cout << ans[i / 2] << '\n';
        }
    }
}

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