oj.uz

Submission #657596

# Submission time Handle Problem Language Result Execution time Memory
657596 2022-11-10T11:05:24 Z d4xn Regions (IOI09_regions) C++17
100 / 100
 5360 ms 30644 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];
bool vis[N];
 
void dfs2(int rg, int u, int cnt) {
    if (reg[u] == rg) vis[u] = 1;
    ans[rg][reg[u]] += cnt;
    for (int &v : adj[u]) {
        dfs2(rg, v, cnt+(reg[u] == rg));
    }
}
 
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++) {
      vis[i] = 0;
    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]) {
        if (vis[u]) continue;
        dfs2(reg[u], u, 0);
    }
  }
 
  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 6764 KB Output is correct
2 Correct 5 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 9 ms 6736 KB Output is correct
6 Correct 22 ms 6828 KB Output is correct
7 Correct 28 ms 6864 KB Output is correct
8 Correct 40 ms 6864 KB Output is correct
9 Correct 53 ms 7248 KB Output is correct
10 Correct 88 ms 7376 KB Output is correct
11 Correct 118 ms 7632 KB Output is correct
12 Correct 122 ms 8144 KB Output is correct
13 Correct 186 ms 7820 KB Output is correct
14 Correct 339 ms 8512 KB Output is correct
15 Correct 224 ms 11088 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1777 ms 11788 KB Output is correct
2 Correct 2162 ms 10672 KB Output is correct
3 Correct 2830 ms 13668 KB Output is correct
4 Correct 270 ms 8528 KB Output is correct
5 Correct 352 ms 10192 KB Output is correct
6 Correct 1533 ms 9936 KB Output is correct
7 Correct 1812 ms 11080 KB Output is correct
8 Correct 1427 ms 16200 KB Output is correct
9 Correct 2537 ms 16892 KB Output is correct
10 Correct 4461 ms 21884 KB Output is correct
11 Correct 5360 ms 17048 KB Output is correct
12 Correct 1240 ms 18632 KB Output is correct
13 Correct 1995 ms 18824 KB Output is correct
14 Correct 2671 ms 22008 KB Output is correct
15 Correct 3105 ms 23260 KB Output is correct
16 Correct 2695 ms 28552 KB Output is correct
17 Correct 2694 ms 30644 KB Output is correct