Submission #546414

#	Time	Username	Problem	Language	Result	Execution time	Memory
546414		cadmiumsky	Meetings 2 (JOI21_meetings2)	C++14	20 / 100	958 ms	1064 KiB

meetings2

#include <bits/stdc++.h>
 
using namespace std;
 
const int nmax = 4e3 + 5;
 
int n;
vector<int> g[nmax];
int pin[nmax], pout[nmax], inp;
int area[nmax], depth[nmax];
int p[nmax][16];
void init(int node, int f) {
  p[node][0] = f;
  depth[node] = depth[f] + 1;
  area[node] ++;
  pin[node] = inp++;
  for(int i = 1; i < 16; i++)
    p[node][i] = p[p[node][i - 1]][i - 1];
  //cout << node << '\n';
  //for(int i = 0; i < 16; i++)
    //cout << p[node][i] << ' ';
  //cout << '\n';
  for(auto x : g[node]) {
    if(x == f)
      continue;
    init(x, node);
    area[node] += area[x];
  }
  pout[node] = inp - 1;
  return;
}
bool isanc(int f, int node) {
  return pin[f] <= pin[node] && pout[node] <= pout[f];
}
int rez[nmax];
int blca(int x, int y) {
  int temp = x;
  for(int i = 15; i >= 0; i--) {
    if(!isanc(p[temp][i], y))
      temp = p[temp][i];
  }
  return temp;
}
void upd(int x, int y) {
  if(isanc(y, x)) 
    swap(x, y);
  if(isanc(x, y)) {
    int k = blca(y, x);
    //cout << x << ' ' << y << ' ' << k << ' ' << isanc(k, y) << '\n';
    //cout << n - area[k] <<
    int u = min(n - area[k], area[y]);
    rez[u * 2] = max(rez[u * 2], depth[y] - depth[x] + 1);
    return;
  }
  else {
    int u = min(area[x], area[y]);
    int lca = blca(x, y);
    lca = p[lca][0];
    rez[u * 2] = max(rez[u * 2], depth[x] + depth[y] - 2 * depth[lca] + 1);
  }
  return;
}
 
int main() {
  cin >> n;
  for(int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  init(1, 1);
  for(int i = 1; i <= n; i++) {
    for(int j = i + 1; j <= n; j++)
      upd(i, j);
  }
  for(int i = n; i > 0; i--) {
    if(i % 2 == 0)
      rez[i] = max({1, rez[i + 2], rez[i]});
    else
      rez[i] = 1;
  }
  for(int i = 1; i <= n; i++) {
    cout << rez[i] << '\n'; 
  }
}

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