Submission #723209

#	Time	Username	Problem	Language	Result	Execution time	Memory
723209		Abrar_Al_Samit	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	5 ms	5028 KiB

meetings2

    #include <bits/stdc++.h>
    #ifdef __LOCAL__
    #include <debug_local.h>
    #endif
    using namespace std;
    const int mxN = 2e5 + 5;
    vector<int> ad[mxN];
    int sz[mxN];
    int p[mxN][20];
    int d[mxN];
    int n;
    void dfs(int u, int par) {
      sz[u] = 1;
      for (int i = 1; i < 20; i++) p[u][i] = p[p[u][i - 1]][i - 1];
      for (int v : ad[u]) {
        if (v == par) continue;
        p[v][0] = u;
        d[v] = d[u] + 1;
        dfs(v, u);
        sz[u] += sz[v];
      }
    }
    int get(int u, int par) {
      for (int v : ad[u]) {
        if (v == par) continue;
        if (sz[v] * 2 > n) return get(v, u);
      }
      return u;
    }
    int lca(int u, int v) {
      if (d[u] < d[v]) swap(u, v);
      for (int i = 19; i >= 0; i--) {
        if (d[p[u][i]] >= d[v]) u = p[u][i];
      }
      if (u == v) return u;
      for (int i = 19; i >= 0; i--) {
        if (p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
      }
      return p[u][0];
    }
    int dist(int a, int b) {
      return d[a] + d[b] - 2 * d[lca(a, b)];
    }
    void testCase() {
      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);
      }
      dfs(1, -1);
      int c = get(1, -1);
      c = 1;
      p[c][0] = c;
      d[c] = 0;
      dfs(c, -1);
      vector<int> ans(n + 1);
      vector<int> v[n + 1];
      for (int i = 1; i <= n; i++) {
        v[sz[i]].push_back(i);
      }
      int a = c, b = c, d = 0;
      for (int i = n; i >= 1; i--) {
        for (int o : v[i]) {
          int ao = dist(a, o);
          int bo = dist(b, o);
          if (max(ao, bo) > d) {
            if (ao > bo) {
              d = ao;
              b = o;
            } else {
              d = bo;
              a = o;
            }
          }
        }
        ans[i] = max(ans[i], d + 1);
        ans[i - 1] = max(ans[i - 1], ans[i]);
      }
      for (int i = 1; i <= n; i++) {
        if (i & 1) cout << "1\n";
        else cout << ans[i / 2] << "\n";
      }
      cout << "\n";
    }
    int main() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      testCase();
      return 0;
    }

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