Submission #1215358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215358		duckindog	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	167 ms	39684 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n;
vector<int> ad[N];

int sz[N], totalSz;

int depth[N];
int f[N][18];
int st[N], ed[N], timer;
void dfs(int u, int p = -1) { 
    st[u] = ++timer;
    sz[u] = 1;

    for (int i = 1; i <= 17; ++i) f[u][i] = f[f[u][i - 1]][i - 1];
    for (const auto& v : ad[u]) { 
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        f[v][0] = u;
        dfs(v, u);
        sz[u] += sz[v];
    }

    totalSz = sz[u];
    ed[u] = timer;
}
inline bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
int lca(int u, int v) {  
    if (anc(u, v)) return u;
    if (anc(v, u)) return v;

    for (int i = 17; i >= 0; --i) 
        if (!anc(f[u][i], v)) u = f[u][i];
    return f[u][0];
}
int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }

int centroid(int u, int p = -1) { 
    for (const auto& v : ad[u]) { 
        if (v == p) continue;
        if (sz[v] > totalSz / 2) return centroid(v, u);
    }
    return u;
}

int answer[N];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i < n; ++i) { 
        int u, v; cin >> u >> v;
        ad[u].push_back(v);
        ad[v].push_back(u);
    }

    int root = 1;
    dfs(root);
    root = centroid(root);
    depth[root] = 0;
    dfs(f[root][0] = root);

    vector<int> order(n); iota(order.begin(), order.end(), 1);
    sort(order.begin(), order.end(), [&](int x, int y) { 
        return sz[x] > sz[y];
    });

    int a = root, b = root, dia = 0;
    answer[n] = 1;
    for (const auto& u : order) { 
        if (u == root) continue;

        int disA = dist(a, u), disB = dist(b, u);
        if (max(disA, disB) > dia) { 
            if (disA >= disB) { 
                dia = disA;
                b = u;
            } else { 
                dia = disB;
                a = u;
            }
        }

        answer[sz[u] * 2] = max(answer[sz[u] * 2], dia + 1);
    }

    for (int i = n - 1; i >= 1; --i) {
        answer[i] = max(answer[i], answer[i + 1]);
    }
    for (int i = 1; i <= n; ++i) { 
        cout << (i & 1 ? 1 : answer[i]) << "\n"; 
    }
}

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