Submission #642180

#	Time	Username	Problem	Language	Result	Execution time	Memory
642180		skittles1412	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	1534 ms	44704 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 mp make_pair
#define long int64_t
#define sz(x) int(std::size(x))

constexpr int maxn = 2e5 + 5;

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

void pdfs(int u, int p = -1) {
    siz[u] = 1;
    for (auto& v : graph[u]) {
        if (v != p) {
            pdfs(v, u);
            siz[u] += siz[v];
            siz1[u].push_back(siz[v]);
        } else {
            siz1[u].push_back(-1);
        }
    }
    if (p != -1) {
        *find(begin(siz1[u]), end(siz1[u]), -1) = n - siz[u];
    }
}

void go(int u) {
    struct DepthDfs {
        void dfs(int u, int p = -1, int d = 0) {
            depth[u] = d;
            for (auto& v : graph[u]) {
                if (!vis[v] && v != p) {
                    dfs(v, u, d + 1);
                }
            }
        }

        static void solve(int u) {
            DepthDfs().dfs(u);
        }
    };
    DepthDfs::solve(u);

    struct Dfs {
        vector<pair<int, int>> ch;

        void dfs(int u, int p) {
            for (int i = 0; i < sz(graph[u]); i++) {
                int v = graph[u][i];
                if (v == p) {
                    ch.emplace_back(n - siz1[u][i], depth[u]);
                } else if (!vis[v]) {
                    dfs(v, u);
                }
            }
        }

        static vector<pair<int, int>> solve(int u, int p) {
            Dfs d;
            d.dfs(u, p);
            return d.ch;
        }
    };

    for (int _i = 0; _i < 2; _i++) {
        map<int, int> copt;
        auto query = [&](int x, int d) -> void {
            auto it = copt.lower_bound(x);
            if (it != copt.end()) {
                ans[x] = max(ans[x], d + it->second);
            }
        };
        auto update = [&](int x, int d) -> void {
            auto it = copt.lower_bound(x);
            if (it != copt.end() && it->second >= d) {
                return;
            }
            while (it != copt.begin() && d >= (--it)->second) {
                it = copt.erase(it);
            }
            copt[x] = d;
        };

        for (int i = 0; i < sz(graph[u]); i++) {
            int v = graph[u][i], csz = n - siz1[u][i];
            if (vis[v]) {
                continue;
            }
            auto&& cv = Dfs::solve(v, u);
            for (auto& [x, d] : cv) {
                query(x, d);
                ans[min(x, csz)] = max(ans[min(x, csz)], d);
            }
            for (auto& [x, d] : cv) {
                update(x, d);
            }
        }

        reverse(begin(graph[u]), end(graph[u]));
        reverse(begin(siz1[u]), end(siz1[u]));
    }
}

void dfs(int u) {
    while (true) {
        pair<int, int> mx {-1, -1};
        for (auto& v : graph[u]) {
            if (!vis[v]) {
                mx = max(mx, mp(siz[v], v));
            }
        }
        if (mx.first <= siz[u] / 2) {
            break;
        }
        int v = mx.second;
        siz[u] -= siz[v];
        siz[v] += siz[u];
        u = v;
    }
    go(u);
    vis[u] = true;
    for (auto& v : graph[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
}

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: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80