Submission #1162692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162692		fryingduc	Meetings 2 (JOI21_meetings2)	C++20	4 / 100	4 ms	5704 KiB

meetings2

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
const int LG = 19;
int n, h[maxn], par[maxn];
vector<int> g[maxn];
bool in_diam[maxn];
int sz[maxn];
int up[maxn][LG + 1];
int res[maxn];

void dfs_diam(int u, int prev) {
  for (auto v:g[u]) {
    if (v == prev) continue;
    h[v] = h[u] + 1;
    par[v] = u;
    dfs_diam(v, u);
  }
}

pair<int, int> lowest[maxn];
int ord[maxn];
int anc[maxn];

void dfs(int u, int prev, int p) {
  sz[u] = 1;
  anc[u] = p;
  for (auto v:g[u]) {
    if (v == prev) continue;
    h[v] = h[u] + 1;
    par[v] = u;
    up[v][0] = u;
    for (int i = 1; i <= LG; ++i) {
      up[v][i] = up[up[v][i - 1]][i - 1];
    }
    dfs(v, u, (prev ? p : v));
    sz[u] += sz[v];
  }
}

void solve() {
  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_diam(1, 0);
  int r1 = max_element(h + 1, h + n + 1) - h;
  h[r1] = par[r1] = 0, dfs_diam(r1, 0);
  int c = max_element(h + 1, h + n + 1) - h;
  int d = h[c];
  while (h[c] > d / 2) {
    c = par[c];
  }
  h[c] = 0, dfs(c, 0, 0);
  iota(ord + 1, ord + n + 1, 1);
  sort(ord + 1, ord + n + 1, [](const int &x, const int &y) -> bool {
    return h[x] > h[y];
  });
  for (int i = 1; i <= n; ++i) {
    int u = ord[i];
    if (u == c) continue;
    if (!lowest[sz[u]].first) {
      lowest[sz[u]].first = u;
    } else if (!lowest[sz[u]].second) {
      if (anc[lowest[sz[u]].first] != anc[u]) {
        lowest[sz[u]].second = u;
      }
    }
  }
  debug(c);
  for (int i = n - 1; i; --i) {
    vector<pair<int, int>> x;
    if (lowest[i].first) {
      x.emplace_back(h[lowest[i].first], lowest[i].first);
    }
    if (lowest[i].second) {
      x.emplace_back(h[lowest[i].second], lowest[i].second);
    }
    if (lowest[i + 1].first) {
      x.emplace_back(h[lowest[i + 1].first], lowest[i + 1].first);
    }
    if (lowest[i + 1].second) {
      x.emplace_back(h[lowest[i + 1].second], lowest[i + 1].second);
    }
    sort(x.begin(), x.end(), greater<pair<int, int>>());
    lowest[i] = make_pair(0, 0);
    for (auto j:x) {
      int u = j.second;
      if (!lowest[i].first) {
        lowest[i].first = u;
      } else if (!lowest[i].second) {
        if (anc[lowest[i].first] != anc[u]) {
          lowest[i].second = u;
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (i & 1) {
      cout << 1 << '\n';
      continue;
    }
    auto t = lowest[i / 2];
    debug(i / 2, t);
    if (!t.first) {
      cout << 1 << '\n';
    } else if (!t.second) {
      if (n - sz[t.first] < i / 2) {
        cout << 1 << '\n';
        continue;
      }
      int p = t.first;
      int res = 0;
      for (int j = LG; j >= 0; --j) {
        if (up[p][j] and n - sz[up[p][j]] >= i / 2) {
          p = up[p][j];
          res += (1 << j);
        }
      }
//      debug(i, t.first, p);
      cout << res + 2 << '\n';
    } else {
      cout << h[t.first] + h[t.second] + 1 << '\n';
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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