oj.uz

Submission #655256

# Submission time Handle Problem Language Result Execution time Memory
655256 2022-11-03T15:54:15 Z d4xn Regions (IOI09_regions) C++17
70 / 100
 4569 ms 55324 KB 
#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define vi vector<int>
#define vvi vector<vi>

const int N = 200000, R1 = 25000, R2 = 500;

int n, r, q, curr;
int reg[N], sz[N], pre[N], idx[N];
ll ans[R2][R2];
vi adj[N], from[R1], pos[R1];

void dfs(int u) {
  sz[u] = 1;
  pre[curr] = reg[u];
  pos[reg[u]].pb(curr);
  idx[u] = curr;
  curr++;

  for (int &v : adj[u]) {
    dfs(v);
    sz[u] += sz[v];
  }
}

int query(int a, int b, int c) {
  int l = lower_bound(all(pos[c]), a) - pos[c].begin();
  int r = upper_bound(all(pos[c]), b) - pos[c].begin();
  return r-l;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> r >> q;

  int mx = 0;
  for (int i = 0; i < n; i++) {
    if (i) {
      int x;
      cin >> x;
      x--;
      adj[x].pb(i);
    }
  
    cin >> reg[i];
    reg[i]--;
    from[reg[i]].pb(i);
    mx = max(mx, (int)from[reg[i]].size());
  }

  curr = 0;
  dfs(0);

  if (r <= R2) {
    // precalc all queries
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < r; j++) {
        if (i == j) continue;
        ans[i][j] = 0;
        for (int &u : from[i]) {
          ans[i][j] += query(idx[u], idx[u] + sz[u] - 1, j);
        }
      }
    }
  }

  assert(!(r > R2 && mx > R2));

  while (q--) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    if (r <= R2) {
      cout << ans[x][y] << endl;
    }
    else {
      ll cnt = 0;
      for (int &u : from[x]) {
        cnt += query(idx[u], idx[u] + sz[u] - 1, y);
      }
      cout << cnt << endl;
    }   
  }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6224 KB Output is correct
2 Correct 4 ms 6224 KB Output is correct
3 Correct 5 ms 6224 KB Output is correct
4 Correct 7 ms 6352 KB Output is correct
5 Correct 8 ms 6352 KB Output is correct
6 Correct 20 ms 7248 KB Output is correct
7 Correct 34 ms 6828 KB Output is correct
8 Correct 43 ms 7140 KB Output is correct
9 Correct 69 ms 7880 KB Output is correct
10 Correct 200 ms 8420 KB Output is correct
11 Correct 254 ms 8084 KB Output is correct
12 Correct 543 ms 9336 KB Output is correct
13 Correct 548 ms 8728 KB Output is correct
14 Correct 490 ms 8904 KB Output is correct
15 Correct 420 ms 11432 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1577 ms 11972 KB Output is correct
2 Correct 1742 ms 11128 KB Output is correct
3 Correct 2375 ms 14032 KB Output is correct
4 Correct 272 ms 7924 KB Output is correct
5 Correct 358 ms 9552 KB Output is correct
6 Correct 1309 ms 9292 KB Output is correct
7 Correct 1907 ms 10440 KB Output is correct
8 Correct 1316 ms 15556 KB Output is correct
9 Correct 2174 ms 16164 KB Output is correct
10 Correct 4257 ms 21192 KB Output is correct
11 Correct 4569 ms 16280 KB Output is correct
12 Runtime error 95 ms 35528 KB Execution killed with signal 6
13 Runtime error 79 ms 35960 KB Execution killed with signal 6
14 Runtime error 89 ms 35608 KB Execution killed with signal 6
15 Runtime error 89 ms 44480 KB Execution killed with signal 6
16 Runtime error 88 ms 55324 KB Execution killed with signal 6
17 Runtime error 91 ms 52892 KB Execution killed with signal 6