Submission #398839

#	Time	Username	Problem	Language	Result	Execution time	Memory
398839		12tqian	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	726 ms	61132 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

struct LCAJump {
    int n;
    std::vector<std::vector<int>> par;
    std::vector<std::vector<int>> adj;
    std::vector<int> depth;

    void init(int _n) {
        n = _n;
        int d = 1;
        while ((1 << d) < n) d++;
        par.assign(d, std::vector<int>(n));
        adj.resize(n);
        depth.resize(n);
    }

    void ae(int x, int y) {
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    void gen(int root = 0) {
        par[0][root] = root;
        dfs(root);
    }

    void dfs(int src = 0) {
        for (int i = 1; i < (int)par.size(); i++) {
            par[i][src] = par[i - 1][par[i - 1][src]];
        }
        for (int nxt: adj[src]) {
            if (nxt == par[0][src]) continue;
            depth[nxt] = depth[par[0][nxt] = src] + 1;
            dfs(nxt);
        }
    }

    int jump(int x, int d) {
        for (int i = 0; i < (int)par.size(); i++) {
            if ((d >> i) & 1) {
                x = par[i][x];
            }
        }
        return x;
    }
    
    int lca(int x, int y) {
        if (depth[x] < depth[y]) std::swap(x, y);
        x = jump(x, depth[x] - depth[y]);
        if (x == y) return x;
        for (int i = (int)par.size() - 1; i >= 0; i--) {
            int nx = par[i][x];
            int ny = par[i][y];
            if (nx != ny) x = nx, y = ny;
        }
        return par[0][x];
    }

    int dist(int x, int y) {
        return depth[x] + depth[y] - 2 * depth[lca(x, y)];
    }
};

LCAJump L;

struct DynamicDiameter {
    pi ed;
    void init(int x) {
        ed = {x, x};
    }
    void add(int x) {
        int d1 = L.dist(ed.f, x);
        int d2 = L.dist(ed.s, x);
        int d3 = L.dist(ed.f, ed.s);
        if (d3 >= max(d1, d2)) return;
        if (d1 >= d2) ed.s = x;
        else ed.f = x;
    }
    int get() {
        return L.dist(ed.f, ed.s);
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0); 
    int n; cin >> n;
    L.init(n);
    vector<vi> g(n);
    vi size(n);
    vi par(n);
    f0r(i, n - 1) {
        int u, v; cin >> u >> v;
        --u, --v;
        g[u].pb(v);
        g[v].pb(u);
        L.ae(u, v);
    }
    function<void(int, int)> dfs_size = [&](int u, int p) {
        size[u] = 1;
        par[u] = p;
        each(v, g[u]) {
            if (v == p) continue;
            dfs_size(v, u);
            size[u] += size[v];
        }
    };
    auto get_centroid = [&](int u) -> int {
        dfs_size(u, -1);
        int p = -1;
        do {
            int go = -1;
            each(v, g[u]) {
                if (v == p) continue;
                if (2 * size[v] > n) go = v;
            } 
            p = u;
            u = go;
        } while (u != -1);
        return p;
    };
    int c = get_centroid(0);
    L.gen(c);
    dfs_size(c, -1);
    vi ans(n + 1, 1);
    vector<vi> on(n + 1); // when things get turned on
    f0r(i, n) {
        if (i == c) continue;
        on[size[i]].pb(i);
    }
    DynamicDiameter D;
    D.init(c);
    for (int i = n / 2; i >= 1; i--) {
        each(u, on[i]) {
            D.add(u);
        }
        ans[2 * i] = D.get() + 1;
    }
    f1r(i, 1, n + 1) cout << ans[i] << '\n';


    return 0;
}

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