oj.uz

Submission #655245

# Submission time Handle Problem Language Result Execution time Memory
655245 2022-11-03T15:40:11 Z d4xn Regions (IOI09_regions) C++17
75 / 100
 8000 ms 27324 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 R2 = 500;

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

void init() {
  reg.resize(n);
  sz.resize(n);
  pre.resize(n);
  idx.resize(n);
  adj.resize(n);
  from.resize(r);
  pos.resize(r);
}

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;
  init();

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

  curr = 0;
  dfs(0);

  if (r <= 500) {
    // 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);
        }
      }
    }
  }

  while (q--) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    if (r <= 500) {
      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 0 ms 208 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 5 ms 464 KB Output is correct
5 Correct 9 ms 464 KB Output is correct
6 Correct 15 ms 1360 KB Output is correct
7 Correct 41 ms 932 KB Output is correct
8 Correct 43 ms 1272 KB Output is correct
9 Correct 89 ms 2120 KB Output is correct
10 Correct 228 ms 2792 KB Output is correct
11 Correct 306 ms 2632 KB Output is correct
12 Correct 573 ms 4020 KB Output is correct
13 Correct 541 ms 3304 KB Output is correct
14 Correct 560 ms 3528 KB Output is correct
15 Correct 497 ms 6584 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1709 ms 7816 KB Output is correct
2 Correct 1814 ms 6884 KB Output is correct
3 Correct 2104 ms 10260 KB Output is correct
4 Correct 275 ms 3024 KB Output is correct
5 Correct 272 ms 4892 KB Output is correct
6 Correct 1496 ms 5004 KB Output is correct
7 Correct 2142 ms 6704 KB Output is correct
8 Correct 1690 ms 12504 KB Output is correct
9 Correct 3040 ms 14608 KB Output is correct
10 Correct 5136 ms 20588 KB Output is correct
11 Correct 6164 ms 16308 KB Output is correct
12 Correct 7369 ms 16980 KB Output is correct
13 Execution timed out 8026 ms 17100 KB Time limit exceeded
14 Execution timed out 8064 ms 17440 KB Time limit exceeded
15 Execution timed out 8058 ms 22060 KB Time limit exceeded
16 Execution timed out 8013 ms 27324 KB Time limit exceeded
17 Execution timed out 8061 ms 25916 KB Time limit exceeded