oj.uz

Submission #511186

# Submission time Handle Problem Language Result Execution time Memory
511186 2022-01-15T11:15:40 Z 600Mihnea Regions (IOI09_regions) C++17
4 / 100
 208 ms 64884 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e5 + 7;
const int R = 25000 + 7;
const int CNT = 100;
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];
int act[CNT + 7];
int who[CNT + 7];
int y;

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;
}

void dfs(int a) {
  act[id[type[a]]]++;
  for (auto &b : g[a]) {
    dfs(b);
  }
  for (int j = 1; j <= y; j++) {
    solution[who[j]][type[a]] += act[who[j]];
  }
  act[id[type[a]]]--;
}

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());
  for (int j = 0; j < min(n, CNT); j++) {
    int i = ord[j].second;
    y++;
    id[i] = y;
    who[y] = i;
  }
  dfs(1);

  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
4.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6216 KB Output is correct
2 Correct 3 ms 6216 KB Output is correct
3 Correct 8 ms 6344 KB Output is correct
4 Correct 9 ms 6472 KB Output is correct
5 Runtime error 12 ms 12840 KB Execution killed with signal 11
6 Runtime error 8 ms 12616 KB Execution killed with signal 11
7 Incorrect 32 ms 6600 KB Output isn't correct
8 Incorrect 31 ms 6692 KB Output isn't correct
9 Runtime error 12 ms 13804 KB Execution killed with signal 11
10 Runtime error 15 ms 14024 KB Execution killed with signal 11
11 Runtime error 18 ms 14664 KB Execution killed with signal 11
12 Runtime error 33 ms 15728 KB Execution killed with signal 11
13 Runtime error 26 ms 15272 KB Execution killed with signal 11
14 Runtime error 47 ms 16568 KB Execution killed with signal 11
15 Runtime error 49 ms 23280 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 23892 KB Execution killed with signal 11
2 Runtime error 67 ms 21600 KB Execution killed with signal 11
3 Runtime error 82 ms 27708 KB Execution killed with signal 11
4 Runtime error 37 ms 16732 KB Execution killed with signal 11
5 Runtime error 41 ms 20156 KB Execution killed with signal 11
6 Runtime error 51 ms 19948 KB Execution killed with signal 11
7 Runtime error 66 ms 22564 KB Execution killed with signal 11
8 Runtime error 95 ms 33300 KB Execution killed with signal 11
9 Runtime error 165 ms 35548 KB Execution killed with signal 11
10 Runtime error 201 ms 46080 KB Execution killed with signal 11
11 Runtime error 183 ms 36588 KB Execution killed with signal 11
12 Runtime error 208 ms 38992 KB Execution killed with signal 11
13 Runtime error 185 ms 39356 KB Execution killed with signal 11
14 Runtime error 183 ms 39292 KB Execution killed with signal 11
15 Runtime error 190 ms 48136 KB Execution killed with signal 11
16 Runtime error 193 ms 64884 KB Execution killed with signal 11
17 Runtime error 184 ms 56372 KB Execution killed with signal 11