oj.uz

Submission #655335

# Submission time Handle Problem Language Result Execution time Memory
655335 2022-11-03T21:02:05 Z d4xn Regions (IOI09_regions) C++17
70 / 100
 8000 ms 35332 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, sq;
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;
  sq = sqrt(n);

  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() <= sq) 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() > sq) {
      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;
    }   
  }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:64:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     if (from[i].size() <= sq) continue;
      |         ~~~~~~~~~~~~~~~^~~~~
regions.cpp:79:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |     if (from[x].size() > sq) {
      |         ~~~~~~~~~~~~~~~^~~~

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 6784 KB Output is correct
4 Correct 12 ms 6708 KB Output is correct
5 Correct 7 ms 6828 KB Output is correct
6 Correct 18 ms 6864 KB Output is correct
7 Correct 36 ms 6864 KB Output is correct
8 Correct 24 ms 6932 KB Output is correct
9 Correct 31 ms 7248 KB Output is correct
10 Correct 100 ms 7376 KB Output is correct
11 Correct 91 ms 7680 KB Output is correct
12 Correct 136 ms 8144 KB Output is correct
13 Correct 217 ms 7904 KB Output is correct
14 Correct 346 ms 8540 KB Output is correct
15 Correct 259 ms 11076 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2182 ms 11720 KB Output is correct
2 Correct 2793 ms 10592 KB Output is correct
3 Correct 3581 ms 13564 KB Output is correct
4 Correct 316 ms 8528 KB Output is correct
5 Correct 415 ms 10192 KB Output is correct
6 Correct 4081 ms 13184 KB Output is correct
7 Correct 4379 ms 15080 KB Output is correct
8 Correct 5915 ms 23960 KB Output is correct
9 Correct 2482 ms 16708 KB Output is correct
10 Execution timed out 8102 ms 35332 KB Time limit exceeded
11 Correct 5315 ms 16860 KB Output is correct
12 Execution timed out 8032 ms 18448 KB Time limit exceeded
13 Execution timed out 8044 ms 18516 KB Time limit exceeded
14 Execution timed out 8060 ms 19372 KB Time limit exceeded
15 Execution timed out 8055 ms 22988 KB Time limit exceeded
16 Correct 7454 ms 28408 KB Output is correct
17 Execution timed out 8023 ms 30120 KB Time limit exceeded