oj.uz

Submission #655250

# Submission time Handle Problem Language Result Execution time Memory
655250 2022-11-03T15:45:30 Z d4xn Regions (IOI09_regions) C++17
85 / 100
 8000 ms 27396 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 = 550;

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 4 ms 464 KB Output is correct
5 Correct 6 ms 464 KB Output is correct
6 Correct 23 ms 1488 KB Output is correct
7 Correct 32 ms 1104 KB Output is correct
8 Correct 42 ms 1360 KB Output is correct
9 Correct 71 ms 2248 KB Output is correct
10 Correct 199 ms 2896 KB Output is correct
11 Correct 233 ms 2740 KB Output is correct
12 Correct 543 ms 4296 KB Output is correct
13 Correct 521 ms 3356 KB Output is correct
14 Correct 530 ms 3528 KB Output is correct
15 Correct 431 ms 6696 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1576 ms 7908 KB Output is correct
2 Correct 1715 ms 6964 KB Output is correct
3 Correct 2295 ms 10500 KB Output is correct
4 Correct 198 ms 2960 KB Output is correct
5 Correct 349 ms 4872 KB Output is correct
6 Correct 1579 ms 5012 KB Output is correct
7 Correct 1897 ms 6704 KB Output is correct
8 Correct 1405 ms 12500 KB Output is correct
9 Correct 2403 ms 14616 KB Output is correct
10 Correct 4242 ms 20572 KB Output is correct
11 Correct 5194 ms 16300 KB Output is correct
12 Correct 6493 ms 16964 KB Output is correct
13 Correct 6449 ms 17156 KB Output is correct
14 Execution timed out 8034 ms 17436 KB Time limit exceeded
15 Execution timed out 8069 ms 22084 KB Time limit exceeded
16 Correct 7560 ms 27396 KB Output is correct
17 Execution timed out 8019 ms 25920 KB Time limit exceeded