oj.uz

Submission #511184

# Submission time Handle Problem Language Result Execution time Memory
511184 2022-01-15T11:03:26 Z 600Mihnea Regions (IOI09_regions) C++17
18 / 100
 8000 ms 29708 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 <= 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 4 ms 6088 KB Output is correct
2 Correct 3 ms 6216 KB Output is correct
3 Correct 5 ms 6216 KB Output is correct
4 Correct 7 ms 6216 KB Output is correct
5 Correct 12 ms 6216 KB Output is correct
6 Correct 23 ms 6348 KB Output is correct
7 Correct 39 ms 6344 KB Output is correct
8 Correct 46 ms 6344 KB Output is correct
9 Correct 49 ms 7092 KB Output is correct
10 Correct 103 ms 7312 KB Output is correct
11 Correct 154 ms 7936 KB Output is correct
12 Correct 208 ms 8656 KB Output is correct
13 Correct 255 ms 8528 KB Output is correct
14 Incorrect 419 ms 9304 KB Output isn't correct
15 Incorrect 521 ms 11964 KB Output isn't correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8022 ms 12304 KB Time limit exceeded
2 Execution timed out 8052 ms 11084 KB Time limit exceeded
3 Execution timed out 8090 ms 14144 KB Time limit exceeded
4 Incorrect 554 ms 9504 KB Output isn't correct
5 Incorrect 503 ms 11016 KB Output isn't correct
6 Correct 3030 ms 10972 KB Output is correct
7 Incorrect 3785 ms 12372 KB Output isn't correct
8 Incorrect 3461 ms 17792 KB Output isn't correct
9 Incorrect 5091 ms 19060 KB Output isn't correct
10 Execution timed out 8020 ms 24172 KB Time limit exceeded
11 Execution timed out 8055 ms 19576 KB Time limit exceeded
12 Execution timed out 8005 ms 19848 KB Time limit exceeded
13 Execution timed out 8022 ms 20144 KB Time limit exceeded
14 Execution timed out 8015 ms 20000 KB Time limit exceeded
15 Execution timed out 8005 ms 24448 KB Time limit exceeded
16 Execution timed out 8029 ms 29708 KB Time limit exceeded
17 Execution timed out 8052 ms 28484 KB Time limit exceeded