oj.uz

Submission #511178

# Submission time Handle Problem Language Result Execution time Memory
511178 2022-01-15T10:56:36 Z 600Mihnea Regions (IOI09_regions) C++17
45 / 100
 8000 ms 27972 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e5 + 7;
const int R = 25000 + 7;
const int M = 500;
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[R][M];

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);
  int y = 0;
  for (int i = 1; i <= r; i++) {
    assert(y + 7 < M);
    if ((int) verts[i].size() >= M) {
      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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6088 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 5 ms 6088 KB Output is correct
4 Correct 7 ms 6088 KB Output is correct
5 Correct 6 ms 6216 KB Output is correct
6 Correct 23 ms 6216 KB Output is correct
7 Correct 33 ms 6216 KB Output is correct
8 Correct 44 ms 6216 KB Output is correct
9 Correct 58 ms 6752 KB Output is correct
10 Correct 93 ms 6728 KB Output is correct
11 Correct 119 ms 6984 KB Output is correct
12 Correct 172 ms 7512 KB Output is correct
13 Correct 148 ms 7268 KB Output is correct
14 Correct 275 ms 7880 KB Output is correct
15 Correct 211 ms 10440 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8090 ms 11560 KB Time limit exceeded
2 Execution timed out 8045 ms 10360 KB Time limit exceeded
3 Execution timed out 8095 ms 13364 KB Time limit exceeded
4 Correct 321 ms 7944 KB Output is correct
5 Correct 320 ms 9476 KB Output is correct
6 Incorrect 4405 ms 9656 KB Output isn't correct
7 Correct 1738 ms 10380 KB Output is correct
8 Incorrect 1708 ms 15900 KB Output isn't correct
9 Correct 2351 ms 16172 KB Output is correct
10 Correct 4207 ms 21128 KB Output is correct
11 Correct 3716 ms 16188 KB Output is correct
12 Execution timed out 8073 ms 18188 KB Time limit exceeded
13 Execution timed out 8037 ms 18400 KB Time limit exceeded
14 Execution timed out 8029 ms 18408 KB Time limit exceeded
15 Execution timed out 8092 ms 22752 KB Time limit exceeded
16 Execution timed out 8077 ms 27972 KB Time limit exceeded
17 Execution timed out 8099 ms 26864 KB Time limit exceeded