oj.uz

Submission #655248

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

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 2 ms 336 KB Output is correct
4 Correct 7 ms 336 KB Output is correct
5 Correct 4 ms 464 KB Output is correct
6 Correct 31 ms 1176 KB Output is correct
7 Correct 34 ms 896 KB Output is correct
8 Correct 48 ms 1104 KB Output is correct
9 Correct 89 ms 1836 KB Output is correct
10 Correct 119 ms 1144 KB Output is correct
11 Correct 359 ms 2396 KB Output is correct
12 Correct 129 ms 2140 KB Output is correct
13 Correct 630 ms 3040 KB Output is correct
14 Correct 667 ms 3356 KB Output is correct
15 Correct 493 ms 6356 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1983 ms 7660 KB Output is correct
2 Correct 2051 ms 6708 KB Output is correct
3 Correct 2621 ms 10072 KB Output is correct
4 Correct 287 ms 3024 KB Output is correct
5 Correct 390 ms 4876 KB Output is correct
6 Correct 1669 ms 5016 KB Output is correct
7 Correct 1949 ms 6700 KB Output is correct
8 Correct 1794 ms 12508 KB Output is correct
9 Correct 2961 ms 14612 KB Output is correct
10 Correct 5766 ms 20576 KB Output is correct
11 Correct 6301 ms 16304 KB Output is correct
12 Execution timed out 8019 ms 16884 KB Time limit exceeded
13 Execution timed out 8016 ms 17160 KB Time limit exceeded
14 Execution timed out 8036 ms 17444 KB Time limit exceeded
15 Execution timed out 8058 ms 22104 KB Time limit exceeded
16 Execution timed out 8058 ms 27336 KB Time limit exceeded
17 Execution timed out 8039 ms 25956 KB Time limit exceeded