oj.uz

Submission #657593

# Submission time Handle Problem Language Result Execution time Memory
657593 2022-11-10T10:55:40 Z d4xn Regions (IOI09_regions) C++17
75 / 100
 4564 ms 30648 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 r, int u, int cnt) {
    vis[u] = 1;
    ans[r][reg[u]] += cnt;
    for (int &v : adj[u]) {
        dfs2(r, v, cnt+(reg[u] == 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;
 
  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 6736 KB Output is correct
2 Correct 4 ms 6736 KB Output is correct
3 Correct 7 ms 6736 KB Output is correct
4 Correct 7 ms 6744 KB Output is correct
5 Correct 7 ms 6736 KB Output is correct
6 Correct 22 ms 6864 KB Output is correct
7 Correct 34 ms 6864 KB Output is correct
8 Correct 34 ms 6864 KB Output is correct
9 Correct 48 ms 7248 KB Output is correct
10 Correct 75 ms 7376 KB Output is correct
11 Correct 99 ms 7632 KB Output is correct
12 Correct 102 ms 8144 KB Output is correct
13 Correct 176 ms 7888 KB Output is correct
14 Correct 264 ms 8528 KB Output is correct
15 Correct 251 ms 11088 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1835 ms 11792 KB Output isn't correct
2 Incorrect 1973 ms 10680 KB Output isn't correct
3 Incorrect 3090 ms 13648 KB Output isn't correct
4 Correct 263 ms 8528 KB Output is correct
5 Correct 329 ms 10192 KB Output is correct
6 Correct 1469 ms 9952 KB Output is correct
7 Correct 1632 ms 11044 KB Output is correct
8 Correct 1385 ms 16228 KB Output is correct
9 Correct 2331 ms 16924 KB Output is correct
10 Correct 3959 ms 21932 KB Output is correct
11 Correct 4564 ms 17048 KB Output is correct
12 Correct 1341 ms 18636 KB Output is correct
13 Correct 1984 ms 18832 KB Output is correct
14 Incorrect 2071 ms 22000 KB Output isn't correct
15 Correct 2863 ms 23296 KB Output is correct
16 Correct 2936 ms 28548 KB Output is correct
17 Incorrect 2426 ms 30648 KB Output isn't correct