oj.uz

Submission #597554

# Submission time Handle Problem Language Result Execution time Memory
597554 2022-07-16T10:17:41 Z MilosMilutinovic Regions (IOI09_regions) C++14
75 / 100
 8000 ms 48380 KB 
/**
 *    author:  wxhtzdy
 *    created: 16.07.2022 11:38:01
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, r, q;
  cin >> n >> r >> q;
  vector<vector<int>> g(n);
  vector<int> reg(n);
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      int p;
      cin >> p;
      --p;
      g[p].push_back(i);
    }
    cin >> reg[i];
    --reg[i];
  }
  vector<vector<int>> ids(r);
  for (int i = 0; i < n; i++) {
    ids[reg[i]].push_back(i);
  }             
  int BLOCK = 400;
  vector<bool> h(r);
  vector<int> id(r);
  vector<int> xs;
  int T = 0;
  for (int i = 0; i < r; i++) {
    if (ids[i].size() >= BLOCK) {
      h[i] = true;
      id[i] = ++T;
      xs.push_back(i);
    }
  }              
  vector<vector<int>> U(T + 1, vector<int>(r));
  vector<vector<int>> D(T + 1, vector<int>(r));
  vector<vector<pair<int, int>>> ev(r);
  vector<vector<int>> my(r);
  vector<int> cnt(r);
  function<void(int)> Dfs = [&](int v) {
    if (h[reg[v]]) {
      for (int i = 0; i < r; i++) {
        U[id[reg[v]]][i] += cnt[i]; 
      }
    }        
    for (int i : xs) {
      D[id[i]][reg[v]] += cnt[i];
    }
    cnt[reg[v]] += 1;
    ++T;
    ev[reg[v]].emplace_back(T - 1, -1);
    my[reg[v]].push_back(T);
    for (int u : g[v]) {
      Dfs(u);
    }
    ev[reg[v]].emplace_back(T, +1);
    cnt[reg[v]] -= 1;
  };
  Dfs(0);
  while (q--) {
    int r1, r2;
    cin >> r1 >> r2;
    --r1; --r2;
    if (h[r1]) {       
      cout << D[id[r1]][r2] << endl; 
    } else if (h[r2]) {
      cout << U[id[r2]][r1] << endl;
    } else {
      int ptr = 0;
      long long ans = 0;
      for (int i = 0; i < (int) ev[r1].size(); i++) {
        while (ptr < (int) my[r2].size() && my[r2][ptr] <= ev[r1][i].first) {
          ptr += 1;
        }
        ans += ptr * ev[r1][i].second;
      }
      cout << ans << endl;
    }
  }
  return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:36:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     if (ids[i].size() >= BLOCK) {
      |         ~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 6 ms 208 KB Output is correct
5 Correct 4 ms 336 KB Output is correct
6 Correct 17 ms 464 KB Output is correct
7 Correct 25 ms 464 KB Output is correct
8 Correct 27 ms 464 KB Output is correct
9 Correct 51 ms 1360 KB Output is correct
10 Correct 73 ms 1228 KB Output is correct
11 Correct 50 ms 1832 KB Output is correct
12 Correct 104 ms 2768 KB Output is correct
13 Correct 122 ms 2512 KB Output is correct
14 Correct 171 ms 3408 KB Output is correct
15 Correct 225 ms 8668 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 8772 KB Output is correct
2 Correct 897 ms 6996 KB Output is correct
3 Correct 1404 ms 12232 KB Output is correct
4 Correct 210 ms 3716 KB Output is correct
5 Correct 289 ms 6992 KB Output is correct
6 Correct 1978 ms 9608 KB Output is correct
7 Correct 1677 ms 10448 KB Output is correct
8 Correct 4376 ms 25916 KB Output is correct
9 Correct 1507 ms 18780 KB Output is correct
10 Execution timed out 8061 ms 48380 KB Time limit exceeded
11 Correct 2102 ms 19932 KB Output is correct
12 Correct 4117 ms 20096 KB Output is correct
13 Correct 5013 ms 21052 KB Output is correct
14 Execution timed out 8089 ms 24084 KB Time limit exceeded
15 Execution timed out 8048 ms 29976 KB Time limit exceeded
16 Execution timed out 8050 ms 42248 KB Time limit exceeded
17 Execution timed out 8041 ms 39980 KB Time limit exceeded