Submission #1037589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037589		juicy	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	171 ms	40824 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5, LG = 18;

int n;
int res[N], pr[LG][N], sz[N], dep[N];
vector<int> g[N];

void dfs(int u) {
  sz[u] = 1;
  for (int v : g[u]) {
    if (v != pr[0][u]) {
      pr[0][v] = u;
      dep[v] = dep[u] + 1;
      dfs(v);
      sz[u] += sz[v];
    }
  }
}

int findCen(int u, int p) {
  for (int v : g[u]) {
    if (v != p && sz[v] * 2 > n) {
      return findCen(v, u);
    }
  }
  return u;
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) {
    swap(u, v);
  }
  for (int j = LG - 1; ~j; --j) {
    if (dep[u] - (1 << j) >= dep[v]) {
      u = pr[j][u];
    }
  }
  if (u == v) {
    return u;
  }
  for (int j = LG - 1; ~j; --j) {
    if (pr[j][u] ^ pr[j][v]) {
      u = pr[j][u], v = pr[j][v];
    }
  }
  return pr[0][u];
}

int dis(int u, int v) {
  return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

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

  cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }  
  dfs(1);
  int c = findCen(1, 1);
  pr[0][c] = 0;
  dfs(c);
  for (int j = 1; j < LG; ++j) {
    for (int i = 1; i <= n; ++i) {
      pr[j][i] = pr[j - 1][pr[j - 1][i]];
    }
  }
  array<int, 3> best{0, c, c};
  vector<int> cands;
  for (int i = 1; i <= n; ++i) {
    if (i ^ c) {
      cands.push_back(i);
    }
  }
  sort(cands.begin(), cands.end(), [&](int i, int j) {
    return sz[i] > sz[j];
  });
  for (int i = n / 2, j = 0; i > 0; --i) {
    while (j < cands.size() && sz[cands[j]] == i) {
      int u = cands[j], a = best[1], b = best[2];
      best = max({best, {dis(u, a), a, u}, {dis(u, b), b, u}});
      ++j;
    } 
    res[i * 2] = best[0];
  }
  for (int i = 1; i <= n; ++i) {
    cout << res[i] + 1 << "\n";
  }
  return 0;
}

Compilation message (stderr)

meetings2.cpp: In function 'int main()':
meetings2.cpp:91:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     while (j < cands.size() && sz[cands[j]] == i) {
      |            ~~^~~~~~~~~~~~~~

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