Submission #1099584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099584		onbert	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	628 ms	41956 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, lg = 20;
int N;
vector<int> adj[maxn];
int ans[maxn];

bool vis[maxn];
int FA[maxn], D[maxn], SZ[maxn];
void DFS(int u) {
    vis[u] = true;
    SZ[u] = 1;
    for (int v:adj[u]) if (!vis[v]) {
        FA[v] = u, D[v] = u;
        DFS(v);
        SZ[u] += SZ[v];
    }
}

int fa[maxn], grp[maxn], sz[maxn], d[maxn];
vector<int> node;
void dfs0(int u) {
    vis[u] = true;
    node.push_back(u);
    sz[u] = 1;
    bool ok = false;
    for (int v:adj[u]) if (!vis[v]) {
        dfs0(v);
        sz[u] += sz[v];
    }
}
void dfs1(int u, int anc) {
    vis[u] = true;
    grp[u] = anc;
    for (int v:adj[u]) if (!vis[v]) {
        fa[v] = u, d[v] = d[u] + 1;
        dfs1(v, anc);
    }
}

void centroid(int start) {
    node.clear();
    dfs0(start);
    int n = node.size();
    int cent = -1;
    for (int i:node) {
        bool ok = (n - sz[i] <= n/2);
        // cout << i << endl;
        // cout << n - sz[i] << " ";
        for (int j:adj[i]) if (sz[j] < sz[i]) {
            // cout << j << '.' << sz[j] << " ";
            if (sz[j] > n/2) ok = false;
        }
        // cout << endl;
        if (ok) cent = i;
    }
    // cout << cent << endl;
    for (int i:node) vis[i] = false;
    vis[cent] = true, fa[cent] = -1, grp[cent] = -1, d[cent] = 0;
    for (int i:adj[cent]) {
        fa[i] = cent;
        d[i] = 1;
        dfs1(i, i);
    }
    vector<pair<int,int>> vec;
    for (int i:node) if (i!=cent) {
        // if (i==5) cout << "test " << fa[i] << " " << FA[i] << endl;
        if (fa[i] == FA[i]) vec.push_back({SZ[i], i});
        else vec.push_back({N - SZ[fa[i]], i});
    }
    sort(vec.rbegin(), vec.rend());
    pair<int,int> mx1 = {0, cent}, mx2 = {0, cent};
    for (auto [val, u]:vec) {
        // cout << u << " " << val << " " << d[u] << " " << grp[u] << endl;
        if (mx1.second!=grp[u]) ans[val] = max(mx1.first + d[u] + 1, ans[val]);
        else ans[val] = max(mx2.first + d[u] + 1, ans[val]);

        // if (mx1.second!=grp[u]) cout << mx1.first + d[u] + 1 << endl;
        // else cout << mx2.first + d[u] + 1 << endl;
        
        if (mx1.second == grp[u]) mx1.first = max(d[u], mx1.first);
        else if (mx2.second == grp[u]) mx2.first = max(d[u], mx2.first);
        else if (d[u] > mx2.first) mx2 = {d[u], grp[u]};
        if (mx1.first < mx2.first) swap(mx1, mx2);
    }
    for (int i:node) vis[i] = false;
    for (int i:adj[cent]) {
        adj[i].erase(find(adj[i].begin(), adj[i].end(), cent));
        centroid(i);
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    for (int i=1;i<=N-1;i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    D[1] = 0, FA[1] = -1;
    DFS(1);

    for (int i=1;i<=N;i++) ans[i] = 1;

    for (int i=1;i<=N;i++) vis[i] = 0;
    centroid(1);

    for (int i=N/2-1;i>=1;i--) ans[i] = max(ans[i], ans[i+1]);
    for (int i=1;i<=N;i++) {
        if (i%2==0) cout << ans[i/2] << endl;
        else cout << "1\n";
    }
}

Compilation message (stderr)

meetings2.cpp: In function 'void dfs0(long long int)':
meetings2.cpp:27:10: warning: unused variable 'ok' [-Wunused-variable]
   27 |     bool ok = false;
      |          ^~

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