oj.uz

Submission #546355

# Submission time Handle Problem Language Result Execution time Memory
546355 2022-04-07T10:54:59 Z cadmiumsky Meetings 2 (JOI21_meetings2) C++14
4 / 100
 4000 ms 864 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'; 
  }
}

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 89 ms 340 KB Output is correct
5 Correct 97 ms 404 KB Output is correct
6 Correct 91 ms 404 KB Output is correct
7 Correct 91 ms 512 KB Output is correct
8 Correct 212 ms 404 KB Output is correct
9 Correct 487 ms 416 KB Output is correct
10 Correct 516 ms 400 KB Output is correct
11 Correct 502 ms 396 KB Output is correct
12 Correct 465 ms 404 KB Output is correct
13 Correct 511 ms 404 KB Output is correct
14 Correct 93 ms 460 KB Output is correct
15 Correct 87 ms 340 KB Output is correct
16 Correct 215 ms 400 KB Output is correct
17 Correct 476 ms 408 KB Output is correct
18 Correct 482 ms 340 KB Output is correct
19 Correct 227 ms 404 KB Output is correct
20 Correct 525 ms 400 KB Output is correct
21 Correct 202 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 89 ms 340 KB Output is correct
5 Correct 97 ms 404 KB Output is correct
6 Correct 91 ms 404 KB Output is correct
7 Correct 91 ms 512 KB Output is correct
8 Correct 212 ms 404 KB Output is correct
9 Correct 487 ms 416 KB Output is correct
10 Correct 516 ms 400 KB Output is correct
11 Correct 502 ms 396 KB Output is correct
12 Correct 465 ms 404 KB Output is correct
13 Correct 511 ms 404 KB Output is correct
14 Correct 93 ms 460 KB Output is correct
15 Correct 87 ms 340 KB Output is correct
16 Correct 215 ms 400 KB Output is correct
17 Correct 476 ms 408 KB Output is correct
18 Correct 482 ms 340 KB Output is correct
19 Correct 227 ms 404 KB Output is correct
20 Correct 525 ms 400 KB Output is correct
21 Correct 202 ms 340 KB Output is correct
22 Execution timed out 4046 ms 864 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 89 ms 340 KB Output is correct
5 Correct 97 ms 404 KB Output is correct
6 Correct 91 ms 404 KB Output is correct
7 Correct 91 ms 512 KB Output is correct
8 Correct 212 ms 404 KB Output is correct
9 Correct 487 ms 416 KB Output is correct
10 Correct 516 ms 400 KB Output is correct
11 Correct 502 ms 396 KB Output is correct
12 Correct 465 ms 404 KB Output is correct
13 Correct 511 ms 404 KB Output is correct
14 Correct 93 ms 460 KB Output is correct
15 Correct 87 ms 340 KB Output is correct
16 Correct 215 ms 400 KB Output is correct
17 Correct 476 ms 408 KB Output is correct
18 Correct 482 ms 340 KB Output is correct
19 Correct 227 ms 404 KB Output is correct
20 Correct 525 ms 400 KB Output is correct
21 Correct 202 ms 340 KB Output is correct
22 Execution timed out 4046 ms 864 KB Time limit exceeded
23 Halted 0 ms 0 KB -