oj.uz

Submission #657583

# Submission time Handle Problem Language Result Execution time Memory
657583 2022-11-10T10:12:05 Z d4xn Regions (IOI09_regions) C++17
90 / 100
 8000 ms 29764 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,0);
    for (int &u : from[i]) {
      for (int j = 0; j < sz[u]; j++) {
        ans[i][pre[idx[u]+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 5 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 7 ms 6736 KB Output is correct
5 Correct 11 ms 6736 KB Output is correct
6 Correct 24 ms 6864 KB Output is correct
7 Correct 26 ms 6864 KB Output is correct
8 Correct 28 ms 6864 KB Output is correct
9 Correct 41 ms 7320 KB Output is correct
10 Correct 96 ms 7376 KB Output is correct
11 Correct 119 ms 7632 KB Output is correct
12 Correct 144 ms 8144 KB Output is correct
13 Correct 218 ms 7904 KB Output is correct
14 Correct 304 ms 8528 KB Output is correct
15 Correct 255 ms 11088 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2550 ms 11712 KB Output is correct
2 Correct 2313 ms 10600 KB Output is correct
3 Correct 4460 ms 13572 KB Output is correct
4 Correct 200 ms 8528 KB Output is correct
5 Correct 353 ms 10112 KB Output is correct
6 Correct 1384 ms 9808 KB Output is correct
7 Correct 1653 ms 10984 KB Output is correct
8 Correct 1442 ms 16080 KB Output is correct
9 Correct 2288 ms 16796 KB Output is correct
10 Correct 4175 ms 21792 KB Output is correct
11 Correct 4951 ms 16860 KB Output is correct
12 Correct 1590 ms 18444 KB Output is correct
13 Correct 2706 ms 18640 KB Output is correct
14 Correct 3034 ms 21836 KB Output is correct
15 Correct 6250 ms 23056 KB Output is correct
16 Execution timed out 8006 ms 28360 KB Time limit exceeded
17 Execution timed out 8045 ms 29764 KB Time limit exceeded