oj.uz

Submission #511177

# Submission time Handle Problem Language Result Execution time Memory
511177 2022-01-15T10:49:52 Z 600Mihnea Regions (IOI09_regions) C++17
80 / 100
 8000 ms 35392 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e5 + 7;
const int M = 500;
int n;
int r;
int q;
int par[N];
int type[N];
vector<int> g[N];
vector<int> pos[N];
vector<int> verts[N];
int low[N];
int high[N];
int top;

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);
  for (int iq = 1; iq <= q; iq++) {
    int a, b;
    cin >> a >> b;
    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 7 ms 14280 KB Output is correct
2 Correct 8 ms 14280 KB Output is correct
3 Correct 11 ms 14280 KB Output is correct
4 Correct 11 ms 14280 KB Output is correct
5 Correct 13 ms 14408 KB Output is correct
6 Correct 26 ms 14408 KB Output is correct
7 Correct 39 ms 14428 KB Output is correct
8 Correct 40 ms 14536 KB Output is correct
9 Correct 68 ms 14920 KB Output is correct
10 Correct 101 ms 14920 KB Output is correct
11 Correct 129 ms 15176 KB Output is correct
12 Correct 155 ms 15736 KB Output is correct
13 Correct 137 ms 15432 KB Output is correct
14 Correct 304 ms 16072 KB Output is correct
15 Correct 291 ms 18676 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8026 ms 19296 KB Time limit exceeded
2 Execution timed out 8016 ms 18112 KB Time limit exceeded
3 Execution timed out 8028 ms 21104 KB Time limit exceeded
4 Correct 311 ms 16132 KB Output is correct
5 Correct 411 ms 17736 KB Output is correct
6 Correct 1324 ms 17408 KB Output is correct
7 Correct 1318 ms 18636 KB Output is correct
8 Correct 1366 ms 23596 KB Output is correct
9 Correct 1989 ms 24408 KB Output is correct
10 Correct 4317 ms 29288 KB Output is correct
11 Correct 3970 ms 24424 KB Output is correct
12 Correct 3879 ms 25724 KB Output is correct
13 Correct 4461 ms 25864 KB Output is correct
14 Correct 5488 ms 25868 KB Output is correct
15 Correct 6702 ms 30248 KB Output is correct
16 Correct 6818 ms 35392 KB Output is correct
17 Execution timed out 8004 ms 34308 KB Time limit exceeded