oj.uz

Submission #597550

# Submission time Handle Problem Language Result Execution time Memory
597550 2022-07-16T10:13:58 Z MilosMilutinovic Regions (IOI09_regions) C++14
80 / 100
 8000 ms 48528 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 = max(1, (int) sqrt(n));
  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 4 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 11 ms 512 KB Output is correct
7 Correct 28 ms 464 KB Output is correct
8 Correct 33 ms 464 KB Output is correct
9 Correct 47 ms 1360 KB Output is correct
10 Correct 83 ms 1232 KB Output is correct
11 Correct 96 ms 1824 KB Output is correct
12 Correct 138 ms 2832 KB Output is correct
13 Correct 205 ms 2492 KB Output is correct
14 Correct 192 ms 3400 KB Output is correct
15 Correct 233 ms 8688 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 8704 KB Output is correct
2 Correct 1014 ms 7000 KB Output is correct
3 Correct 1478 ms 12216 KB Output is correct
4 Correct 291 ms 3716 KB Output is correct
5 Correct 337 ms 7044 KB Output is correct
6 Correct 1998 ms 9356 KB Output is correct
7 Correct 2112 ms 12160 KB Output is correct
8 Correct 4316 ms 25884 KB Output is correct
9 Correct 1451 ms 18852 KB Output is correct
10 Execution timed out 8026 ms 48528 KB Time limit exceeded
11 Correct 2131 ms 19928 KB Output is correct
12 Correct 4033 ms 19952 KB Output is correct
13 Correct 4542 ms 21280 KB Output is correct
14 Execution timed out 8009 ms 24180 KB Time limit exceeded
15 Execution timed out 8048 ms 29996 KB Time limit exceeded
16 Correct 6920 ms 42316 KB Output is correct
17 Execution timed out 8052 ms 42652 KB Time limit exceeded