Submission #1226191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226191		Double_Slash	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	1343 ms	53164 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];
vector<pint> order;
map<int, int> mx[200001];
bool seen[200001];

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

void chmax(auto &a, auto b) { a = max(a, b); }

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);
    }
    auto it = mx[root].lower_bound(sum);
    while (it != mx[root].begin() and prev(it)->second <= d) mx[root].erase(prev(it));
    if (it->second <= d) 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);
    for (auto [m, i]: order) {
        int tot = sz[i];
        seen[i] = true;
        map<int, int> cur;
        for (int j: adj[i]) {
            if (seen[j]) continue;
            tot += dfs2(j, j);
            for (auto [sum, d]: mx[j]) {
                auto it = cur.lower_bound(sum);
                if (it != cur.end()) chmax(ans[sum << 1], it->second + d);
                while (it != cur.begin() and prev(it)->second <= d) cur.erase(prev(it));
                if (it->second <= d) cur[sum] = d;
            }
        }
        cur.clear();
        reverse(all(adj[i]));
        for (int j: adj[i]) {
            if (seen[j]) continue;
            for (auto [sum, d]: mx[j]) {
                auto it = cur.lower_bound(sum);
                if (it != cur.end()) chmax(ans[sum << 1], it->second + d);
                while (it != cur.begin() and prev(it)->second <= d) cur.erase(prev(it));
                if (it->second <= d) cur[sum] = d;
            }
        }
        for (int j: adj[i]) {
            if (seen[j]) continue;
            for (auto [sum, d]: mx[j]) chmax(ans[min(sum, tot - mx[j].rbegin()->first) << 1], d);
            sz[j] += tot - mx[j].rbegin()->first;
            mx[j].clear();
        }
    }
    for (int i = n >> 1; i--;) ans[i << 1] = max(ans[i << 1], ans[(i + 1) << 1]);
    for (int i = 1; i <= n; ++i) cout << ans[i] + 1 << endl;
}

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