oj.uz

Submission #597556

# Submission time Handle Problem Language Result Execution time Memory
597556 2022-07-16T10:18:43 Z MilosMilutinovic Regions (IOI09_regions) C++14
80 / 100
 8000 ms 48368 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 = 350;
  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 5 ms 208 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 18 ms 476 KB Output is correct
7 Correct 23 ms 464 KB Output is correct
8 Correct 26 ms 464 KB Output is correct
9 Correct 44 ms 1360 KB Output is correct
10 Correct 67 ms 1232 KB Output is correct
11 Correct 100 ms 1824 KB Output is correct
12 Correct 132 ms 2836 KB Output is correct
13 Correct 135 ms 2496 KB Output is correct
14 Correct 176 ms 3396 KB Output is correct
15 Correct 234 ms 8692 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 917 ms 8708 KB Output is correct
2 Correct 1063 ms 7004 KB Output is correct
3 Correct 1688 ms 12244 KB Output is correct
4 Correct 176 ms 3728 KB Output is correct
5 Correct 277 ms 7056 KB Output is correct
6 Correct 2167 ms 9388 KB Output is correct
7 Correct 2047 ms 10992 KB Output is correct
8 Correct 4626 ms 25964 KB Output is correct
9 Correct 1650 ms 18788 KB Output is correct
10 Execution timed out 8042 ms 48368 KB Time limit exceeded
11 Correct 2120 ms 19924 KB Output is correct
12 Correct 4687 ms 19900 KB Output is correct
13 Correct 4884 ms 21048 KB Output is correct
14 Execution timed out 8071 ms 24060 KB Time limit exceeded
15 Execution timed out 8031 ms 30088 KB Time limit exceeded
16 Correct 7145 ms 42264 KB Output is correct
17 Execution timed out 8023 ms 42800 KB Time limit exceeded