Submission #1215354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215354		duckindog	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	2 ms	4936 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];
void dfs(int u, int p = -1) { 
    sz[u] = 1;

    for (const auto& v : ad[u]) { 
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
        sz[u] += sz[v];
    }

    totalSz = sz[u];
}

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;
}

namespace IT { 
    int f[N << 2];
    void update(int s, int l, int r, int p, int x) { 
        if (l == r) { 
            f[s] = max(f[s], x);
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) update(s << 1, l, mid, p, x);
        else update(s << 1 | 1, mid + 1, r, p, x);
        f[s] = max(f[s << 1], f[s << 1 | 1]);
    }
    int query(int s, int l, int r, int u, int v) { 
        if (v < l || u > r) return 0;
        if (u <= l && r <= v) return f[s];
        int mid = (l + r) >> 1;
        return max(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
    }
}

int id[N];
void idDFS(int u, int p = -1) { 
    for (const auto& v : ad[u]) { 
        if (v == p) continue;
        id[v] = id[u];
        idDFS(v, 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(root);

    for (int i = 0; i < (int)ad[root].size(); ++i) { 
        int u = ad[root][i];
        id[u] = i + 1;
        idDFS(u, 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];
    });

    answer[n] = 1;
    for (const auto& u : order) { 
        if (u == root) continue;

        IT::update(1, 1, n, id[u], depth[u]);
        int dis = max(IT::query(1, 1, n, 1, id[u] - 1),
                        IT::query(1, 1, n, id[u] + 1, n)) + depth[u] + 1;

        answer[sz[u] * 2] = max(answer[sz[u] * 2], dis);
    }

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