oj.uz

Submission #511181

# Submission time Handle Problem Language Result Execution time Memory
511181 2022-01-15T10:59:06 Z 600Mihnea Regions (IOI09_regions) C++17
55 / 100
 8000 ms 28112 KB 
#include <bits/stdc++.h>

using namespace std;

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

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++) {
    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 3 ms 6188 KB Output is correct
3 Correct 4 ms 6088 KB Output is correct
4 Correct 6 ms 6088 KB Output is correct
5 Correct 10 ms 6216 KB Output is correct
6 Correct 24 ms 6216 KB Output is correct
7 Correct 35 ms 6216 KB Output is correct
8 Correct 40 ms 6216 KB Output is correct
9 Correct 53 ms 6728 KB Output is correct
10 Correct 89 ms 6728 KB Output is correct
11 Correct 119 ms 6984 KB Output is correct
12 Correct 144 ms 7548 KB Output is correct
13 Correct 165 ms 7248 KB Output is correct
14 Correct 275 ms 7932 KB Output is correct
15 Correct 188 ms 10412 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8031 ms 11428 KB Time limit exceeded
2 Execution timed out 8068 ms 10440 KB Time limit exceeded
3 Execution timed out 8053 ms 13480 KB Time limit exceeded
4 Correct 291 ms 7972 KB Output is correct
5 Correct 377 ms 9536 KB Output is correct
6 Correct 1299 ms 9232 KB Output is correct
7 Correct 1538 ms 10520 KB Output is correct
8 Correct 1213 ms 15392 KB Output is correct
9 Correct 2281 ms 16168 KB Output is correct
10 Correct 4700 ms 21184 KB Output is correct
11 Correct 4243 ms 16132 KB Output is correct
12 Execution timed out 8026 ms 18284 KB Time limit exceeded
13 Execution timed out 8066 ms 18396 KB Time limit exceeded
14 Execution timed out 8038 ms 18400 KB Time limit exceeded
15 Execution timed out 8013 ms 22684 KB Time limit exceeded
16 Execution timed out 8063 ms 28112 KB Time limit exceeded
17 Execution timed out 8096 ms 26836 KB Time limit exceeded