Submission #564196

#	Time	Username	Problem	Language	Result	Execution time	Memory
564196		nikatamliani	Meetings 2 (JOI21_meetings2)	C++14	0 / 100	3 ms	5008 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> g[N];
int n, sub[N], done[N], f[N], ans[N];
int maxi;
int upper;
void add(int x, int y) {
    // x = upper - x + 1;
    // assert(x > 0);
    // while (x <= upper) {
    //     f[x] = max(f[x], y);
    //     x += x & -x;
    // }
    f[x] = max(f[x], y);
}
int get(int x) {
    // int ans = -N;
    // x = upper - x + 1;
    // while (x > 0) {
    //     ans = max(ans, f[x]);
    //     x -= x & -x;
    // }
    // return ans;
    int ans = -1e9;
    for (int i = x; i <= upper; ++i) {
        ans = max(ans, f[i]);
    }
    return ans;
}
int find_centroid(int x, int p, int sz) {
    for (int to : g[x]) {
        if (!done[to] && to != p && sub[to] > sz / 2) {
            return find_centroid(to, x, sz);
        }
    }
    return x;
}
void calc(int x, int p) {
    sub[x] = 1;
    for (int to : g[x]) {
        if (!done[to] && p != to) {
            calc(to, x);
            sub[x] += sub[to];
        }
    }
}
void insert(int x, int p, int pos, int depth = 1) {
    for (int to : g[x]) {
        if (to != p && !done[to]) {
            insert(to, x, pos, depth + 1);
        }
    }
    if (pos == 1) {
        add(sub[x], depth);
    } else {
        ans[sub[x]] = max(ans[sub[x]], depth + get(sub[x]) + 1);
    }
}
void decomp(int x, int p, int sz) {
    calc(x, p);
    int c = find_centroid(x, -1, sz);
    upper = sz;
    calc(c, p);
    for (int i = 1; i <= sz; ++i) {
        f[i] = -1e9;
    }
    add(sub[c], 0);
    for (int to : g[c]) {
        if (done[to]) continue;
        insert(to, c, 0); 
        insert(to, c, 1);
    }
    for (int i = 1; i <= sz; ++i) {
        f[i] = -1e9;
    }
    add(sub[c], 0);
    reverse(g[c].begin(), g[c].end());
    for (int to : g[c]) {
        if (done[to]) continue;
        insert(to, c, 0);
        insert(to, c, 1);
    }
    for (int i = 1; i <= sz; ++i) {
        f[i] = -1e9;
    }
    done[c] = 1;
    for (int to : g[c]) {
        if (!done[to]) {
            decomp(to, c, sub[to]);
        }
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    decomp(1, 0, n);
    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 == 0) {
            cout << ans[i / 2] << '\n';
        } else {
            cout << "1\n";
        }
    }
}

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