oj.uz

Submission #597569

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

using namespace std;

const int BLOCK = 700;

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 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 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 19 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 44 ms 1360 KB Output is correct
10 Correct 69 ms 1232 KB Output is correct
11 Correct 97 ms 1744 KB Output is correct
12 Correct 99 ms 2640 KB Output is correct
13 Correct 88 ms 2340 KB Output is correct
14 Correct 229 ms 3192 KB Output is correct
15 Correct 208 ms 8516 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 921 ms 8332 KB Output is correct
2 Correct 1054 ms 6700 KB Output is correct
3 Correct 1501 ms 11932 KB Output is correct
4 Correct 159 ms 3408 KB Output is correct
5 Correct 314 ms 6736 KB Output is correct
6 Correct 562 ms 5600 KB Output is correct
7 Correct 653 ms 7524 KB Output is correct
8 Correct 532 ms 17176 KB Output is correct
9 Correct 885 ms 17300 KB Output is correct
10 Correct 1821 ms 26836 KB Output is correct
11 Correct 2183 ms 17904 KB Output is correct
12 Correct 3759 ms 18540 KB Output is correct
13 Correct 3991 ms 19696 KB Output is correct
14 Execution timed out 8029 ms 21864 KB Time limit exceeded
15 Correct 7330 ms 27852 KB Output is correct
16 Correct 5973 ms 40472 KB Output is correct
17 Correct 7377 ms 40356 KB Output is correct