oj.uz

Submission #388819

# Submission time Handle Problem Language Result Execution time Memory
388819 2021-04-13T05:05:16 Z rama_pang Meetings 2 (JOI21_meetings2) C++17
100 / 100
 2755 ms 71660 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 0 ms 316 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 0 ms 316 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 12 ms 1096 KB Output is correct
23 Correct 12 ms 1080 KB Output is correct
24 Correct 12 ms 1144 KB Output is correct
25 Correct 14 ms 1100 KB Output is correct
26 Correct 12 ms 1112 KB Output is correct
27 Correct 11 ms 1100 KB Output is correct
28 Correct 12 ms 1096 KB Output is correct
29 Correct 15 ms 1120 KB Output is correct
30 Correct 14 ms 1036 KB Output is correct
31 Correct 11 ms 1100 KB Output is correct
32 Correct 18 ms 1360 KB Output is correct
33 Correct 18 ms 1436 KB Output is correct
34 Correct 5 ms 972 KB Output is correct
35 Correct 4 ms 972 KB Output is correct
36 Correct 12 ms 1224 KB Output is correct
37 Correct 6 ms 1060 KB Output is correct
38 Correct 11 ms 1160 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 0 ms 316 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 12 ms 1096 KB Output is correct
23 Correct 12 ms 1080 KB Output is correct
24 Correct 12 ms 1144 KB Output is correct
25 Correct 14 ms 1100 KB Output is correct
26 Correct 12 ms 1112 KB Output is correct
27 Correct 11 ms 1100 KB Output is correct
28 Correct 12 ms 1096 KB Output is correct
29 Correct 15 ms 1120 KB Output is correct
30 Correct 14 ms 1036 KB Output is correct
31 Correct 11 ms 1100 KB Output is correct
32 Correct 18 ms 1360 KB Output is correct
33 Correct 18 ms 1436 KB Output is correct
34 Correct 5 ms 972 KB Output is correct
35 Correct 4 ms 972 KB Output is correct
36 Correct 12 ms 1224 KB Output is correct
37 Correct 6 ms 1060 KB Output is correct
38 Correct 11 ms 1160 KB Output is correct
39 Correct 1623 ms 45600 KB Output is correct
40 Correct 1516 ms 43912 KB Output is correct
41 Correct 1574 ms 45264 KB Output is correct
42 Correct 1514 ms 46100 KB Output is correct
43 Correct 1534 ms 46108 KB Output is correct
44 Correct 1542 ms 45856 KB Output is correct
45 Correct 2755 ms 66276 KB Output is correct
46 Correct 2537 ms 71660 KB Output is correct
47 Correct 485 ms 35852 KB Output is correct
48 Correct 387 ms 36144 KB Output is correct
49 Correct 1636 ms 55776 KB Output is correct
50 Correct 539 ms 37688 KB Output is correct
51 Correct 1475 ms 56720 KB Output is correct