제출 #546356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546356		cadmiumsky	Meetings 2 (JOI21_meetings2)	C++14	4 / 100	4090 ms	820 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] = 1;
  pin[node] = inp++;
  for(int i = 1; i < 16; i++)
    p[node][i] = p[p[node][i - 1]][i - 1];
  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) {
  if(isanc(x, y))
    return x;
  if(isanc(x, y))
    return y;
  int temp = x;
  for(int i = 15; i >= 0; i--) {
    if(!isanc(p[temp][i], y))
      temp = p[temp][i];
  }
  return p[temp][0];
}
int dist(int x, int y) {
  if(x == y)
    return 0;
  int lca = blca(x, y);
  return depth[x] + depth[y] - depth[lca] * 2;
}

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'; 
    if(i % 2 == 1)
      assert(rez[i] == 1);
  }
}

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