oj.uz

Submission #597562

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

using namespace std;

const int BLOCK = 300;

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 0 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 21 ms 464 KB Output is correct
7 Correct 30 ms 464 KB Output is correct
8 Correct 27 ms 464 KB Output is correct
9 Correct 49 ms 1360 KB Output is correct
10 Correct 68 ms 1232 KB Output is correct
11 Correct 102 ms 1744 KB Output is correct
12 Correct 103 ms 2640 KB Output is correct
13 Correct 141 ms 2348 KB Output is correct
14 Correct 172 ms 3196 KB Output is correct
15 Correct 189 ms 8460 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 8572 KB Output is correct
2 Correct 936 ms 6772 KB Output is correct
3 Correct 1370 ms 11972 KB Output is correct
4 Correct 218 ms 3412 KB Output is correct
5 Correct 256 ms 6736 KB Output is correct
6 Correct 1633 ms 9532 KB Output is correct
7 Correct 1843 ms 11856 KB Output is correct
8 Correct 3934 ms 25884 KB Output is correct
9 Correct 2535 ms 23884 KB Output is correct
10 Execution timed out 8018 ms 46348 KB Time limit exceeded
11 Correct 6628 ms 37088 KB Output is correct
12 Correct 3848 ms 18428 KB Output is correct
13 Correct 3951 ms 19588 KB Output is correct
14 Execution timed out 8045 ms 22508 KB Time limit exceeded
15 Correct 7940 ms 27888 KB Output is correct
16 Correct 6937 ms 40376 KB Output is correct
17 Execution timed out 8038 ms 41120 KB Time limit exceeded