Submission #1032539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032539		thangdz2k7	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	344 ms	112464 KiB

meetings2

#include <bits/stdc++.h>
#define vi vector <int>
#define pb push_back

using namespace std;

struct LCA{
    vi st, ed, _lg, high;
    vector <vi> euler, adj;
    int cnt;

    void dfs(int u, int pa){
        ++ cnt;
        st[u] = cnt;
        euler[cnt].pb(u);
        for (int v : adj[u]){
            if (v == pa) continue;
            high[v] = high[u] + 1;
            dfs(v, u);
            euler[++ cnt].pb(u);
        }
        ed[u] = cnt;
    }

    int check(int u, int v) {
        return st[u] <= st[v] && ed[v] <= ed[u];
    }

    int min_by_time(int u, int v) {
        return (st[u] < st[v] ? u : v);
    }

    void add(int u, int v){
        adj[u].pb(v);
        adj[v].pb(u);
    }

    LCA(int n){
        st.resize(n + 3, 0);
        ed.resize(n + 3, 0);
        euler.resize(3 * n + 5);
        adj.resize(n + 3);
        _lg.resize(3 * n + 5);
        high.resize(n + 3, 1);
        for (int i = 0; i <= 3 * n; ++ i) _lg[i] = log2(i);
    }

    void init(int r){
        cnt = 0;
        dfs(r, 0);
        for (int lg = 1; lg < 20; ++lg) {
            for (int i = 1; i + (1 << lg) - 1 <= cnt; ++i)
                euler[i].pb(min_by_time(euler[i][lg - 1], euler[i + (1 << lg - 1)][lg - 1]));
        }
    }

    int get(int u, int v) {
        int L = min(st[u], st[v]);
        int R = max(ed[u], ed[v]);
        int lg = _lg[R - L + 1];
        return min_by_time(euler[L][lg], euler[R - (1 << lg) + 1][lg]);
    }

    int dist(int u, int v){
        int lc = get(u, v);
        return high[u] + high[v] - 2 * high[lc];
    }
};

const int N = 2e5 + 5;

int n, sz[N];
vector <int> adj[N];

void dfs(int u, int p = -1){
    sz[u] = 1;
    for (int v : adj[u]){
        if (v == p) continue;
        dfs(v, u); sz[u] += sz[v];
    }
}

int find_cen(int u, int p = -1){
    for (int v : adj[u]){
        if (v == p) continue;
        if (sz[v] * 2 > n) return find_cen(v, u);
    }
    return u;
}

vector <int> cur[N / 2];
int ans[N];

void solve(){
    cin >> n;
    LCA tree(n);
    for (int i = 1, u, v; i < n; ++ i){
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        tree.add(u, v);
    }

    dfs(1);
    int r = find_cen(1);
    tree.init(r); dfs(r);
    for (int i = 1; i <= n; ++ i) {
        if (i != r) cur[sz[i]].push_back(i);
        if (i & 1) ans[i] = 1;
    }

    int u = r, v = r, Max = 0;
    for (int i = n / 2; i >= 1; -- i){
        for (int k : cur[i]){
            if (tree.dist(u, k) < tree.dist(v, k)) swap(u, v);
            if (tree.dist(u, k) > Max){
                Max = tree.dist(u, k);
                v = k;
            }
        }
        ans[i * 2] = Max + 1;
    }

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

Compilation message (stderr)

meetings2.cpp: In member function 'void LCA::init(int)':
meetings2.cpp:53:78: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   53 |                 euler[i].pb(min_by_time(euler[i][lg - 1], euler[i + (1 << lg - 1)][lg - 1]));
      |                                                                           ~~~^~~

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