oj.uz

Submission #597553

# Submission time Handle Problem Language Result Execution time Memory
597553 2022-07-16T10:16:53 Z MilosMilutinovic Regions (IOI09_regions) C++17
90 / 100
 8000 ms 48344 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 5 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 20 ms 464 KB Output is correct
7 Correct 29 ms 464 KB Output is correct
8 Correct 35 ms 464 KB Output is correct
9 Correct 23 ms 1360 KB Output is correct
10 Correct 69 ms 1232 KB Output is correct
11 Correct 105 ms 1820 KB Output is correct
12 Correct 122 ms 2832 KB Output is correct
13 Correct 144 ms 2512 KB Output is correct
14 Correct 197 ms 3408 KB Output is correct
15 Correct 203 ms 8676 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 8712 KB Output is correct
2 Correct 1010 ms 6992 KB Output is correct
3 Correct 1444 ms 12228 KB Output is correct
4 Correct 202 ms 3804 KB Output is correct
5 Correct 158 ms 7044 KB Output is correct
6 Correct 2072 ms 9452 KB Output is correct
7 Correct 1504 ms 10388 KB Output is correct
8 Correct 4364 ms 25884 KB Output is correct
9 Correct 1222 ms 18780 KB Output is correct
10 Execution timed out 8048 ms 48344 KB Time limit exceeded
11 Correct 2230 ms 19936 KB Output is correct
12 Correct 4299 ms 19964 KB Output is correct
13 Correct 5001 ms 21052 KB Output is correct
14 Execution timed out 8093 ms 24004 KB Time limit exceeded
15 Correct 7962 ms 29876 KB Output is correct
16 Correct 7722 ms 42260 KB Output is correct
17 Correct 7944 ms 42772 KB Output is correct