oj.uz

Submission #655332

# Submission time Handle Problem Language Result Execution time Memory
655332 2022-11-03T20:57:34 Z d4xn Regions (IOI09_regions) C++17
85 / 100
 8000 ms 30080 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>
#define vll vector<ll>

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

int n, r, q, curr;
int reg[N], sz[N], pre[N], idx[N];
vll ans[R1];
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);

  for (int i = 0; i < r; i++) {
    if (from[i].size() <= R2) continue;
    ans[i].resize(r);
    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 (from[x].size() > 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 4 ms 6736 KB Output is correct
2 Correct 4 ms 6736 KB Output is correct
3 Correct 6 ms 6736 KB Output is correct
4 Correct 9 ms 6736 KB Output is correct
5 Correct 11 ms 6812 KB Output is correct
6 Correct 19 ms 6864 KB Output is correct
7 Correct 29 ms 6864 KB Output is correct
8 Correct 26 ms 6868 KB Output is correct
9 Correct 50 ms 7248 KB Output is correct
10 Correct 92 ms 7376 KB Output is correct
11 Correct 131 ms 7632 KB Output is correct
12 Correct 156 ms 8144 KB Output is correct
13 Correct 160 ms 7912 KB Output is correct
14 Correct 223 ms 8452 KB Output is correct
15 Correct 262 ms 11052 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2061 ms 11712 KB Output is correct
2 Correct 2576 ms 10704 KB Output is correct
3 Correct 3097 ms 13572 KB Output is correct
4 Correct 272 ms 8488 KB Output is correct
5 Correct 259 ms 10212 KB Output is correct
6 Correct 1495 ms 9808 KB Output is correct
7 Correct 1890 ms 10960 KB Output is correct
8 Correct 1385 ms 16072 KB Output is correct
9 Correct 2540 ms 16804 KB Output is correct
10 Correct 4564 ms 21756 KB Output is correct
11 Correct 4799 ms 16852 KB Output is correct
12 Correct 7107 ms 18444 KB Output is correct
13 Correct 6969 ms 18644 KB Output is correct
14 Execution timed out 8023 ms 19340 KB Time limit exceeded
15 Execution timed out 8048 ms 22988 KB Time limit exceeded
16 Correct 7419 ms 28360 KB Output is correct
17 Execution timed out 8066 ms 30080 KB Time limit exceeded