oj.uz

Submission #597560

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

using namespace std;

const int MAX_T = 200005 / 400;
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;
  }             
  const int BLOCK = sqrt(n);
  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 384 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 20 ms 464 KB Output is correct
7 Correct 29 ms 476 KB Output is correct
8 Correct 28 ms 464 KB Output is correct
9 Correct 48 ms 1360 KB Output is correct
10 Correct 73 ms 1232 KB Output is correct
11 Correct 68 ms 1752 KB Output is correct
12 Correct 113 ms 2640 KB Output is correct
13 Correct 158 ms 2348 KB Output is correct
14 Correct 166 ms 3256 KB Output is correct
15 Correct 112 ms 8536 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 758 ms 8552 KB Output is correct
2 Correct 937 ms 6736 KB Output is correct
3 Correct 1268 ms 11976 KB Output is correct
4 Correct 256 ms 3416 KB Output is correct
5 Correct 316 ms 6736 KB Output is correct
6 Correct 1862 ms 9388 KB Output is correct
7 Correct 2068 ms 11852 KB Output is correct
8 Correct 3830 ms 25868 KB Output is correct
9 Correct 1049 ms 17296 KB Output is correct
10 Execution timed out 8034 ms 46484 KB Time limit exceeded
11 Correct 1936 ms 17908 KB Output is correct
12 Correct 3759 ms 18664 KB Output is correct
13 Correct 4174 ms 19672 KB Output is correct
14 Execution timed out 8045 ms 22592 KB Time limit exceeded
15 Correct 6756 ms 28056 KB Output is correct
16 Correct 6208 ms 40452 KB Output is correct
17 Execution timed out 8045 ms 41352 KB Time limit exceeded