oj.uz

Submission #597570

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

using namespace std;

const int BLOCK = 1000;

const int MAX_T = 200005 / BLOCK;
const int MAX_R = 25005;

int U[MAX_T][MAX_R];
int D[MAX_T][MAX_R];
int cnt[MAX_R];          
  
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<int> cc(r);
  for (int i = 0; i < n; i++) {
    cc[reg[i]] += 1;
  }             
  vector<bool> h(r);
  vector<int> id(r);
  vector<int> xs;
  int T = 0;
  for (int i = 0; i < r; i++) {
    if (cc[i] >= BLOCK) {
      h[i] = true;
      id[i] = ++T;
      xs.push_back(i);
    }
  }              
  for (int i = 0; i <= T; i++) {
    for (int j = 0; j < r; j++) {
      U[i][j] = D[i][j] = 0;
    }
  }
  vector<vector<pair<int, int>>> ev(r);
  vector<vector<int>> my(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;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 11 ms 336 KB Output is correct
6 Correct 10 ms 464 KB Output is correct
7 Correct 12 ms 464 KB Output is correct
8 Correct 23 ms 464 KB Output is correct
9 Correct 47 ms 1328 KB Output is correct
10 Correct 86 ms 1232 KB Output is correct
11 Correct 129 ms 1756 KB Output is correct
12 Correct 121 ms 2600 KB Output is correct
13 Correct 169 ms 2352 KB Output is correct
14 Correct 162 ms 3204 KB Output is correct
15 Correct 219 ms 8504 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 8416 KB Output is correct
2 Correct 1002 ms 6640 KB Output is correct
3 Correct 1320 ms 11972 KB Output is correct
4 Correct 242 ms 3408 KB Output is correct
5 Correct 331 ms 6720 KB Output is correct
6 Correct 608 ms 5596 KB Output is correct
7 Correct 859 ms 7524 KB Output is correct
8 Correct 986 ms 17156 KB Output is correct
9 Correct 1266 ms 17296 KB Output is correct
10 Correct 1496 ms 26840 KB Output is correct
11 Correct 2088 ms 17904 KB Output is correct
12 Correct 4125 ms 18424 KB Output is correct
13 Correct 4048 ms 19652 KB Output is correct
14 Correct 7657 ms 21160 KB Output is correct
15 Correct 6647 ms 27924 KB Output is correct
16 Correct 6765 ms 40404 KB Output is correct
17 Correct 7976 ms 39808 KB Output is correct