oj.uz

Submission #511185

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

using namespace std;

const int N = (int) 2e5 + 7;
const int R = 25000 + 7;
const int CNT = 10;
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 <= r; 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6088 KB Output is correct
2 Correct 3 ms 6216 KB Output is correct
3 Correct 4 ms 6216 KB Output is correct
4 Correct 7 ms 6216 KB Output is correct
5 Correct 9 ms 6216 KB Output is correct
6 Correct 11 ms 6344 KB Output is correct
7 Correct 33 ms 6344 KB Output is correct
8 Correct 40 ms 6344 KB Output is correct
9 Correct 51 ms 6856 KB Output is correct
10 Correct 80 ms 6984 KB Output is correct
11 Correct 139 ms 7364 KB Output is correct
12 Correct 176 ms 7916 KB Output is correct
13 Correct 178 ms 7648 KB Output is correct
14 Correct 317 ms 8344 KB Output is correct
15 Correct 319 ms 11048 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2285 ms 12276 KB Output is correct
2 Correct 2989 ms 11104 KB Output is correct
3 Correct 3256 ms 14120 KB Output is correct
4 Correct 417 ms 8572 KB Output is correct
5 Correct 496 ms 10180 KB Output is correct
6 Correct 1878 ms 10196 KB Output is correct
7 Correct 2603 ms 11588 KB Output is correct
8 Correct 2019 ms 17056 KB Output is correct
9 Correct 3250 ms 18320 KB Output is correct
10 Correct 5265 ms 23672 KB Output is correct
11 Correct 5104 ms 18944 KB Output is correct
12 Execution timed out 8086 ms 19764 KB Time limit exceeded
13 Execution timed out 8038 ms 19892 KB Time limit exceeded
14 Execution timed out 8022 ms 19696 KB Time limit exceeded
15 Execution timed out 8032 ms 24112 KB Time limit exceeded
16 Execution timed out 8096 ms 29456 KB Time limit exceeded
17 Execution timed out 8023 ms 28196 KB Time limit exceeded