oj.uz

Submission #655334

# Submission time Handle Problem Language Result Execution time Memory
655334 2022-11-03T21:01:55 Z d4xn Regions (IOI09_regions) C++17
80 / 100
 8000 ms 37496 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 6748 KB Output is correct
3 Correct 4 ms 6736 KB Output is correct
4 Correct 9 ms 6736 KB Output is correct
5 Correct 10 ms 6736 KB Output is correct
6 Correct 19 ms 6820 KB Output is correct
7 Correct 29 ms 6864 KB Output is correct
8 Correct 42 ms 6864 KB Output is correct
9 Correct 47 ms 7248 KB Output is correct
10 Correct 85 ms 7376 KB Output is correct
11 Correct 119 ms 7632 KB Output is correct
12 Correct 154 ms 8164 KB Output is correct
13 Correct 188 ms 7888 KB Output is correct
14 Correct 241 ms 8512 KB Output is correct
15 Correct 258 ms 11088 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1847 ms 11728 KB Output is correct
2 Correct 2769 ms 10596 KB Output is correct
3 Correct 3472 ms 13572 KB Output is correct
4 Correct 293 ms 8516 KB Output is correct
5 Correct 408 ms 10192 KB Output is correct
6 Correct 3158 ms 13188 KB Output is correct
7 Correct 4233 ms 14940 KB Output is correct
8 Correct 6375 ms 23960 KB Output is correct
9 Correct 2859 ms 16808 KB Output is correct
10 Execution timed out 8018 ms 37496 KB Time limit exceeded
11 Correct 4959 ms 16856 KB Output is correct
12 Correct 7312 ms 18448 KB Output is correct
13 Correct 7224 ms 18640 KB Output is correct
14 Execution timed out 8092 ms 19264 KB Time limit exceeded
15 Execution timed out 8023 ms 22988 KB Time limit exceeded
16 Correct 7992 ms 28356 KB Output is correct
17 Execution timed out 8050 ms 30088 KB Time limit exceeded