Submission #1225650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225650		Double_Slash	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	5 ms	9800 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;

int n, sz[200001], ans[200001];
vector<int> adj[200001], mx[200001];
vector<pint> order;
bool seen[200001];

int dfs(int i, int p = 0) {
    int m = 0;
    for (int j: adj[i]) {
        if (j != p) m |= dfs(j, i);
    }
    order.emplace_back(-__builtin_ctz(++m), i);
    return m;
}

int dfs2(int i, int root, int d = 1, int p = 0) {
    int sum = sz[i];
    for (int j: adj[i]) {
        if (j == p or seen[j]) continue;
        sum += dfs2(j, root, d + 1, i);
    }
    if (sum >= mx[root].size()) mx[root].resize(sum + 1);
    mx[root][sum] = max(mx[root][sum], d);
    return sum;
}

int main() {
    cin >> n;
    for (int i = n; --i;) {
        int a, b;
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    dfs(1);
    sort(all(order));
    fill(sz + 1, sz + 1 + n, 1);
    auto chmax = [] (auto &a, auto b) { a = max(a, b); };
    for (auto [m, i]: order) {
        int tot = seen[i] = true;
        vector<int> cur{0};
        for (int j: adj[i]) {
            if (seen[j]) continue;
            tot += dfs2(j, j);
            for (int k = mx[j].size(); --k;) chmax(mx[j][k - 1], mx[j][k]);
            for (int k = min(cur.size(), mx[j].size()); --k;) chmax(ans[k << 1], cur[k] + mx[j][k]);
            if (mx[j].size() > cur.size()) cur.resize(mx[j].size());
            for (int k = mx[j].size(); --k;) chmax(cur[k], mx[j][k]);
        }
        for (int j: adj[i]) {
            if (seen[j]) continue;
            for (int k = mx[j].size(); --k;) chmax(ans[min(k, tot - ((int) mx[j].size() - 1)) << 1], mx[j][k]);
            sz[j] += tot - (mx[j].size() - 1);
            mx[j].clear();
        }
    }
    for (int i = 1; i <= n; ++i) cout << ans[i] + 1 << endl;
}

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