Submission #388819

#	Time	Username	Problem	Language	Result	Execution time	Memory
388819		rama_pang	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	2755 ms	71660 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;

class SegTree {
 public:
  int sz;
  vector<int> tree;

  SegTree(int sz = 0) : sz(sz), tree(2 * sz, -1) {}

  void Modify(int p, int x) {
    tree[p += sz] = x;
    for (p /= 2; p > 0; p /= 2) {
      tree[p] = max(tree[p * 2], tree[p * 2 + 1]);
    }
  }

  int Query(int l, int r) {
    int res = -1;
    for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) res = max(res, tree[l++]);
      if (r & 1) res = max(res, tree[--r]);
    }
    return res;
  }
};

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

  int N;
  cin >> N;
  vector<vector<int>> adj(N);
  for (int i = 1; i < N; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }

  // Let's fix X, the number of attendees.
  // Define size_r(v) = number of nodes in subtree of v, if rooted at r.
  //
  // If X is odd, then the answer is 1.
  //   Proof: Assume there is a vertex u which minimizes the total sum of distance.
  //   Then, by moving to an adjacent vertex v, the total sum is changed by
  //   size_u(v) - size_v(u). Since X is odd, this total sum != 0. Thus there can
  //   only be a single optimal u.
  //
  // If X is even, then the optimal meeting nodes form a path.
  //   Assume u and v is the endpoint of this path. size_u(v) >= X/2 and size_v(u) >= X/2
  //   must be satisfied (we put X/2 in the subtree of both endpoints).
  //   The number of meeting points is the number of nodes in the path from u to v.
  //
  // We can enumerate every possible path with centroid decomposition.
  // Time complexity: O(N log^2 N).

  vector<int> ans(N + 1, 1);

  vector<int> siz(N);
  vector<int> dead(N);
  vector<int> depth(N);

  const auto GetCentroid = [&](int s) -> int {
    const auto Dfs = [&](const auto &self, int u, int p) -> void {
      siz[u] = 1;
      for (auto v : adj[u]) if (!dead[v] && v != p) {
        self(self, v, u);
        siz[u] += siz[v];
      }
    };
    Dfs(Dfs, s, -1);
    int p = -1, u = s;
    while (u != -1) {
      pair<int, int> mx = {-1, -1};
      for (auto v : adj[u]) if (!dead[v] && v != p) {
        mx = max(mx, {siz[v], v});
      }
      if (mx.first * 2 <= siz[s]) {
        break;
      } else {
        tie(p, u) = pair(u, mx.second);
      }
    }
    assert(u != -1);
    return u;
  };

  const auto Dfs = [&](const auto &self, int u, int p, vector<int> &ls) -> void {
    ls.emplace_back(u);
    siz[u] = 1;
    depth[u] = p == -1 ? 0 : (depth[p] + 1);
    for (auto v : adj[u]) if (!dead[v] && v != p) {
      self(self, v, u, ls);
      siz[u] += siz[v];
    }
  };

  const auto Decompose = [&](const auto &self, int centroid) -> void {
    centroid = GetCentroid(centroid);
    depth[centroid] = 0;

    static SegTree segtree(N + 1);
    static vector<vector<int>> sub(N);
    static vector<vector<pair<int, int>>> ls(N + 1);

    for (int rep = 0; rep < 2; rep++) {
      reverse(begin(adj[centroid]), end(adj[centroid]));
      Dfs(Dfs, centroid, -1, sub[centroid]); sub[centroid].clear();
      for (auto v : adj[centroid]) if (!dead[v]) {
        Dfs(Dfs, v, centroid, sub[v]);
        for (auto x : sub[v]) {
          if (int other = segtree.Query(siz[x], N); other != -1) {
            assert(siz[x] * 2 <= N);
            ans[siz[x] * 2] = max(ans[siz[x] * 2], depth[x] + 1 + other);
          }
          if (siz[x] <= siz[centroid] - siz[v]) {
            ans[siz[x] * 2] = max(ans[siz[x] * 2], depth[x] + 1);
          }
        }
        for (auto x : sub[v]) {
          if (segtree.Query(siz[x], siz[x]) < depth[x]) {
            segtree.Modify(siz[x], depth[x]);
          }
        }
      }
      for (auto v : adj[centroid]) if (!dead[v]) {
        for (auto x : sub[v]) {
          segtree.Modify(siz[x], -1);
          ls[siz[x]].clear();
        }
        sub[v].clear();
      }
    }

    dead[centroid] = 1;
    for (auto v : adj[centroid]) if (!dead[v]) self(self, v);
  };

  Decompose(Decompose, 0);

  for (int i = N; i >= 2; i--) {
    ans[i - 2] = max(ans[i - 2], ans[i]);
  }
  for (int i = 1; i <= N; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

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