oj.uz

Submission #546356

# Submission time Handle Problem Language Result Execution time Memory
546356 2022-04-07T10:55:51 Z cadmiumsky Meetings 2 (JOI21_meetings2) C++14
4 / 100
 4000 ms 820 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 99 ms 404 KB Output is correct
5 Correct 101 ms 404 KB Output is correct
6 Correct 97 ms 340 KB Output is correct
7 Correct 99 ms 396 KB Output is correct
8 Correct 208 ms 408 KB Output is correct
9 Correct 523 ms 400 KB Output is correct
10 Correct 560 ms 400 KB Output is correct
11 Correct 497 ms 400 KB Output is correct
12 Correct 508 ms 396 KB Output is correct
13 Correct 559 ms 400 KB Output is correct
14 Correct 95 ms 340 KB Output is correct
15 Correct 85 ms 400 KB Output is correct
16 Correct 226 ms 396 KB Output is correct
17 Correct 493 ms 460 KB Output is correct
18 Correct 489 ms 396 KB Output is correct
19 Correct 241 ms 396 KB Output is correct
20 Correct 511 ms 400 KB Output is correct
21 Correct 197 ms 340 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 99 ms 404 KB Output is correct
5 Correct 101 ms 404 KB Output is correct
6 Correct 97 ms 340 KB Output is correct
7 Correct 99 ms 396 KB Output is correct
8 Correct 208 ms 408 KB Output is correct
9 Correct 523 ms 400 KB Output is correct
10 Correct 560 ms 400 KB Output is correct
11 Correct 497 ms 400 KB Output is correct
12 Correct 508 ms 396 KB Output is correct
13 Correct 559 ms 400 KB Output is correct
14 Correct 95 ms 340 KB Output is correct
15 Correct 85 ms 400 KB Output is correct
16 Correct 226 ms 396 KB Output is correct
17 Correct 493 ms 460 KB Output is correct
18 Correct 489 ms 396 KB Output is correct
19 Correct 241 ms 396 KB Output is correct
20 Correct 511 ms 400 KB Output is correct
21 Correct 197 ms 340 KB Output is correct
22 Execution timed out 4090 ms 820 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 99 ms 404 KB Output is correct
5 Correct 101 ms 404 KB Output is correct
6 Correct 97 ms 340 KB Output is correct
7 Correct 99 ms 396 KB Output is correct
8 Correct 208 ms 408 KB Output is correct
9 Correct 523 ms 400 KB Output is correct
10 Correct 560 ms 400 KB Output is correct
11 Correct 497 ms 400 KB Output is correct
12 Correct 508 ms 396 KB Output is correct
13 Correct 559 ms 400 KB Output is correct
14 Correct 95 ms 340 KB Output is correct
15 Correct 85 ms 400 KB Output is correct
16 Correct 226 ms 396 KB Output is correct
17 Correct 493 ms 460 KB Output is correct
18 Correct 489 ms 396 KB Output is correct
19 Correct 241 ms 396 KB Output is correct
20 Correct 511 ms 400 KB Output is correct
21 Correct 197 ms 340 KB Output is correct
22 Execution timed out 4090 ms 820 KB Time limit exceeded
23 Halted 0 ms 0 KB -