Submission #724980

#	Time	Username	Problem	Language	Result	Execution time	Memory
724980		piOOE	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	260 ms	56816 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> adj(n);
    vector<int> parent(n), siz(n), depth(n);

    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        a -= 1, b -= 1;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    auto hld = [&](auto self, int v) -> void {
        siz[v] = 1;
        
        for (int &to : adj[v]) {
            adj[to].erase(find(adj[to].begin(), adj[to].end(), v));
            depth[to] = depth[v] + 1;
            self(self, to);
            siz[v] += siz[to];
            if (siz[to] > siz[adj[v][0]]) {
                swap(to, adj[v][0]);
            }
        }
    };

    hld(hld, 0);

    vector<map<int, int>> st(n);

    auto insert = [&](map<int, int> &mp, int x, int y) -> void {
        auto it = mp.lower_bound(x);
        if (it != mp.end() && it->second >= y) {
            return;
        }

        mp[x] = y;

        it = mp.find(x);
        while (it != mp.begin() && prev(it)->second <= y) {
            it = mp.erase(prev(it));
        }
    };

    constexpr int inf = 1e8 + 7;

    auto query = [&](map<int, int> &mp, int x) {
        auto it = mp.lower_bound(x);
        return it == mp.end() ? -inf : it->second;
    };

    vector<int> best(n + 1);

    auto dfs = [&](auto self, int v) -> void {
        if (adj[v].empty()) {
            insert(st[v], 1, depth[v]);
            return;
        }

        for (int to : adj[v]) {
            self(self, to);
        }

        int x = adj[v][0];
        int now = min(siz[x], n - siz[x]);
        int nxt = min(siz[x], n - siz[v]);

        for (int s = now; s > nxt; --s) {
            int d = query(st[x], s);
            best[min(s, n - siz[x])] = max(best[min(s, n - siz[x])], d - depth[v] + 1);
        }

        swap(st[v], st[x]);

        for (int to : adj[v]) {
            if (to == x) {
                continue;
            }
            for (int s = 1; s <= siz[to]; ++s) {
                int d = query(st[to], s);
                best[s] = max(best[s], d + query(st[v], s) - depth[v] * 2 + 1);
                best[min(s, n - siz[to])] = max(best[min(s, n - siz[to])], d - depth[v] + 1);
            }
            for (auto [a, b] : st[to]) {
                insert(st[v], a, b);
            }
            st[to].clear();
        }

        insert(st[v], siz[v], depth[v]);
    };

    dfs(dfs, 0);

    vector<int> ans(n + 1, 1);

    for (int i = 1; i <= n / 2; ++i) {
        ans[i * 2] = max(1, best[i]);
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << "\n";
    }

    return 0;
}

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