Submission #546351

#	Time	Username	Problem	Language	Result	Execution time	Memory
546351		cadmiumsky	Meetings 2 (JOI21_meetings2)	C++14	0 / 100	105 ms	456 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;
}
int dist(int x, int y) {
  if(x == y)
    return 0;
  int lca = p[blca(x, y)][0];
  return depth[x] + depth[y] - depth[lca] * 2;
}
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 = 0; i < (1 << n); i++) {
    vector<int> cand;
    for(int j = 0; j < n; j++) {
      if(i & (1 << j))
        cand.push_back(j + 1);
    }
    int cnt = 0;
    int maxx = n * n + n * n * n;
    for(int j = 1; j <= n; j++) {
      int cst = 0;
      for(auto x : cand)
        cst += dist(x, j);
      if(cst < maxx)
        cnt = 1, maxx = cst;
      else if(cst == maxx)
        cnt++;
    }
    rez[__builtin_popcount(i)] = max(rez[__builtin_popcount(i)], cnt);
  }
  //for(int i = 1; i <= n; i++) {
    //for(int j = i + 1; j <= n; j++)
      //upd(i, j);
  //}
  for(int i = 1; i <= n; i++) {
    cout << rez[i] << '\n'; 
  }
}

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