Submission #641950

#	Time	Username	Problem	Language	Result	Execution time	Memory
641950		skittles1412	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	3 ms	4948 KiB

meetings2

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

constexpr int maxn = 2e5 + 5;

int n, siz[maxn], depth[maxn], ans[maxn];
vector<int> graph[maxn];

void pdfs(int u, int d = 0) {
    siz[u] = 1;
    depth[u] = d;
    for (auto& v : graph[u]) {
        graph[v].erase(find(begin(graph[v]), end(graph[v]), u));
        pdfs(v, d + 1);
        siz[u] += siz[v];
    }
}

map<int, int> dfs(int u) {
    auto query = [&](const map<int, int>& cur, int x, int d) -> void {
        auto it = cur.upper_bound(x);
        if (it != cur.end()) {
            ans[x] = max(ans[x], d + it->second - 2 * depth[u]);
        }
        if (it != cur.begin()) {
            auto& [x1, d1] = *(--it);
            ans[x1] = max(ans[x1], d + d1 - 2 * depth[u]);
        }
    };
    map<int, int> cur;
    auto update = [&](int x, int d) -> void {
        auto it = cur.lower_bound(x);
        if (it != cur.end() && it->second >= d) {
            return;
        }
        while (it != cur.begin() && d >= (--it)->second) {
            it = cur.erase(it);
        }
        cur[x] = d;
    };
    for (auto& v : graph[u]) {
        auto&& cv = dfs(v);
        query(cv, n - siz[v], depth[u]);
        if (sz(cv) > sz(cur)) {
            swap(cv, cur);
        }
        for (auto& [x, d] : cv) {
            query(cur, x, d);
        }
        for (auto& [x, d] : cv) {
            update(x, d);
        }
    }
    update(siz[u], depth[u]);
    return cur;
}

void solve() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    pdfs(0);
    dfs(0);
    for (int i = n; i >= 0; i--) {
        ans[i] = max(ans[i], ans[i + 1]);
    }
    for (int i = 1; i <= n; i++) {
        if (i & 1) {
            cout << 1 << endl;
        } else {
            cout << ans[i / 2] + 1 << endl;
        }
    }
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}

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