oj.uz

Submission #511183

# Submission time Handle Problem Language Result Execution time Memory
511183 2022-01-15T11:01:38 Z 600Mihnea Regions (IOI09_regions) C++17
13 / 100
 8000 ms 29756 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e5 + 7;
const int R = 25000 + 7;
const int CNT = 100;
int n;
int r;
int q;
int par[N];
int id[N];
int type[N];
vector<int> g[N];
vector<int> pos[R];
vector<int> verts[R];
int low[N];
int high[N];
int top;
int solution[CNT + 7][R];

void build(int a) {
  low[a] = ++top;
  verts[type[a]].push_back(a);
  pos[type[a]].push_back(top);
  for (auto &b : g[a]) {
    build(b);
  }
  high[a] = top;
}

int getcnt(int prefix, int value) {
  int sol = 0, low = 0, high = (int) pos[value].size() - 1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (pos[value][mid] <= prefix) {
      sol = mid + 1;
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return sol;
}

signed main() {
  ///freopen ("input", "r", stdin);

  cin >> n >> r >> q;
  cin >> type[1];
  for (int i = 2; i <= n; i++) {
    cin >> par[i] >> type[i];
    g[par[i]].push_back(i);
  }
  build(1);
  vector<pair<int, int>> ord;
  for (int i = 1; i <= n; i++) {
    ord.push_back({(int) verts[i].size(), i});
  }
  sort(ord.rbegin(), ord.rend());
  int y = 0;
  for (int j = 0; j < min(n, CNT); j++) {
    int i = ord[j].second;
    y++;
    id[i] = y;
    for (auto &v : verts[i]) {
      for (int b = 1; b <= n; b++) {
        solution[y][b] += getcnt(high[v], b) - getcnt(low[v] - 1, b);
      }
    }
  }

  for (int iq = 1; iq <= q; iq++) {
    int a, b;
    cin >> a >> b;
    if (id[a]) {
      cout << solution[id[a]][b] << "\n";
      continue;
    }
    int sol = 0;
    for (auto &v : verts[a]) {
      sol += getcnt(high[v], b) - getcnt(low[v] - 1, b);
    }
    cout << sol << endl;
  }
  return 0;
}

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6216 KB Output is correct
2 Correct 3 ms 6216 KB Output is correct
3 Correct 4 ms 6216 KB Output is correct
4 Correct 6 ms 6352 KB Output is correct
5 Correct 10 ms 6472 KB Output is correct
6 Correct 24 ms 7008 KB Output is correct
7 Correct 39 ms 7296 KB Output is correct
8 Correct 26 ms 7496 KB Output is correct
9 Correct 56 ms 9276 KB Output is correct
10 Correct 162 ms 11352 KB Output is correct
11 Correct 299 ms 13588 KB Output is correct
12 Correct 434 ms 16120 KB Output is correct
13 Correct 553 ms 17308 KB Output is correct
14 Incorrect 1587 ms 18200 KB Output isn't correct
15 Incorrect 1975 ms 20956 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8064 ms 12260 KB Time limit exceeded
2 Execution timed out 8058 ms 11092 KB Time limit exceeded
3 Execution timed out 8092 ms 14260 KB Time limit exceeded
4 Incorrect 2699 ms 18268 KB Output isn't correct
5 Incorrect 2258 ms 19836 KB Output isn't correct
6 Execution timed out 8026 ms 14756 KB Time limit exceeded
7 Execution timed out 8058 ms 14748 KB Time limit exceeded
8 Execution timed out 8058 ms 20144 KB Time limit exceeded
9 Execution timed out 8029 ms 20476 KB Time limit exceeded
10 Execution timed out 8045 ms 24732 KB Time limit exceeded
11 Execution timed out 8016 ms 19768 KB Time limit exceeded
12 Execution timed out 8042 ms 19840 KB Time limit exceeded
13 Execution timed out 8060 ms 20056 KB Time limit exceeded
14 Execution timed out 8047 ms 20064 KB Time limit exceeded
15 Execution timed out 8023 ms 24436 KB Time limit exceeded
16 Execution timed out 8092 ms 29756 KB Time limit exceeded
17 Execution timed out 8020 ms 28528 KB Time limit exceeded