Submission #398177

#	Time	Username	Problem	Language	Result	Execution time	Memory
398177		4fecta	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	2091 ms	30312 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 200005;

int n, u, v, ans[MN], dep[MN], sz[MN], vis[MN], bit[MN], rsz; //deepest dep with this size
vector<int> a[MN], upds;

void upd(int x, int val) {
    for (int i = x; i < MN; i += i & -i) bit[i] = max(bit[i], val);
    upds.push_back(x);
}

int qry(int x) {
    int ret = 0;
    for (int i = x; i > 0; i -= i & -i) ret = max(ret, bit[i]);
    return ret;
}

void rev(int x) {
    for (int i = x; i < MN; i += i & -i) bit[i] = 0;
}

void reset() {
    //memset(bit, 0, sizeof(bit));
    while (upds.size()) rev(upds.back()), upds.pop_back();
}

int get_size(int cur, int pre) {
    sz[cur] = 1;
    for (int nxt : a[cur]) {
        if (vis[nxt] || nxt == pre) continue;
        sz[cur] += get_size(nxt, cur);
    }
    return sz[cur];
}

int get_cent(int cur, int pre, int siz) {
    for (int nxt : a[cur]) {
        if (vis[nxt] || nxt == pre) continue;
        if (sz[nxt] * 2 > siz) return get_cent(nxt, cur, siz);
    }
    return cur;
}

void dfs(int cur, int pre, int d) {
    dep[cur] = d;
    int md = qry(n - sz[cur] + 1);
    if (md) {
        //if (sz[cur] == 3) printf("%d %d %d\n", cur, sz[cur], d + md + 1);
        ans[sz[cur] * 2] = max(ans[sz[cur] * 2], d + md + 1);
    }
    ans[min(rsz, sz[cur]) * 2] = max(ans[min(rsz, sz[cur]) * 2], d + 1);
    for (int nxt : a[cur]) {
        if (vis[nxt] || nxt == pre) continue;
        dfs(nxt, cur, d + 1);
    }
}

void dfs(int cur, int pre) {
    //printf("upd: %d %d %d\n", cur, sz[cur], dep[cur]);
    upd(n - sz[cur] + 1, dep[cur]);
    for (int nxt : a[cur]) {
        if (vis[nxt] || nxt == pre) continue;
        dfs(nxt, cur);
    }
}

void dfs1(int cur, int pre) {
    sz[cur] = 1;
    for (int nxt : a[cur]) {
        if (nxt == pre) continue;
        dfs1(nxt, cur);
        sz[cur] += sz[nxt];
    }
}

void solve(int cur) {
    cur = get_cent(cur, cur, get_size(cur, cur));
    get_size(cur, cur);
    //printf("cur: %lld\n", cur);
    reset();
    for (int nxt : a[cur]) {
        if (vis[nxt]) continue;
        rsz = n - sz[nxt];
        dfs(nxt, cur, 1);
        dfs(nxt, cur);
    }
    reverse(a[cur].begin(), a[cur].end());
    reset();
    for (int nxt : a[cur]) {
        if (vis[nxt]) continue;
        rsz = n - sz[nxt];
        dfs(nxt, cur, 1);
        dfs(nxt, cur);
    }
    vis[cur] = 1;
    for (int nxt : a[cur]) {
        if (vis[nxt]) continue;
        solve(nxt);
    }
}

int32_t main() {
    boost();

    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    solve(1);
    dfs1(1, 0);
    for (int i = 2; i <= n; i++) {
        int csz = min(sz[i], n - sz[i]);
        ans[csz * 2] = max(ans[csz * 2], 2ll);
    }
    for (int i = n; i > 0; i--) ans[i] = max({1ll, ans[i + 1], ans[i]});
    for (int i = 1; i <= n; i++) printf("%lld\n", i % 2 ? 1 : ans[i]);

    return 0;
}

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