oj.uz

Submission #655246

# Submission time Handle Problem Language Result Execution time Memory
655246 2022-11-03T15:40:30 Z d4xn Regions (IOI09_regions) C++17
80 / 100
 8000 ms 27368 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 = 600;

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

  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 1 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 5 ms 464 KB Output is correct
6 Correct 13 ms 1488 KB Output is correct
7 Correct 34 ms 1104 KB Output is correct
8 Correct 42 ms 1388 KB Output is correct
9 Correct 88 ms 2356 KB Output is correct
10 Correct 265 ms 3048 KB Output is correct
11 Correct 313 ms 2896 KB Output is correct
12 Correct 654 ms 4284 KB Output is correct
13 Correct 720 ms 3580 KB Output is correct
14 Correct 645 ms 3704 KB Output is correct
15 Correct 628 ms 6720 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2277 ms 7976 KB Output is correct
2 Correct 2236 ms 7052 KB Output is correct
3 Correct 2679 ms 10468 KB Output is correct
4 Correct 367 ms 3024 KB Output is correct
5 Correct 347 ms 4868 KB Output is correct
6 Correct 1771 ms 5036 KB Output is correct
7 Correct 2196 ms 6700 KB Output is correct
8 Correct 1251 ms 12500 KB Output is correct
9 Correct 2998 ms 14608 KB Output is correct
10 Correct 5156 ms 20584 KB Output is correct
11 Correct 6019 ms 16296 KB Output is correct
12 Correct 7784 ms 16968 KB Output is correct
13 Correct 7958 ms 17160 KB Output is correct
14 Execution timed out 8061 ms 17464 KB Time limit exceeded
15 Execution timed out 8021 ms 22000 KB Time limit exceeded
16 Execution timed out 8013 ms 27368 KB Time limit exceeded
17 Execution timed out 8010 ms 25896 KB Time limit exceeded