oj.uz

Submission #597567

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

using namespace std;

const int BLOCK = 500;

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 0 ms 336 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 6 ms 336 KB Output is correct
6 Correct 17 ms 464 KB Output is correct
7 Correct 27 ms 464 KB Output is correct
8 Correct 28 ms 464 KB Output is correct
9 Correct 37 ms 1360 KB Output is correct
10 Correct 74 ms 1232 KB Output is correct
11 Correct 84 ms 1836 KB Output is correct
12 Correct 90 ms 2640 KB Output is correct
13 Correct 154 ms 2292 KB Output is correct
14 Correct 156 ms 3196 KB Output is correct
15 Correct 223 ms 8448 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 8436 KB Output is correct
2 Correct 879 ms 6732 KB Output is correct
3 Correct 1328 ms 11968 KB Output is correct
4 Correct 213 ms 3408 KB Output is correct
5 Correct 228 ms 6728 KB Output is correct
6 Correct 778 ms 6796 KB Output is correct
7 Correct 688 ms 7532 KB Output is correct
8 Correct 862 ms 17412 KB Output is correct
9 Correct 1016 ms 17304 KB Output is correct
10 Correct 1614 ms 26836 KB Output is correct
11 Correct 1912 ms 17912 KB Output is correct
12 Correct 3933 ms 18420 KB Output is correct
13 Correct 4360 ms 19720 KB Output is correct
14 Execution timed out 8013 ms 22568 KB Time limit exceeded
15 Correct 7319 ms 27900 KB Output is correct
16 Correct 6248 ms 40376 KB Output is correct
17 Execution timed out 8007 ms 41128 KB Time limit exceeded