oj.uz

답안 #597563

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
597563 2022-07-16T10:30:03 Z MilosMilutinovic Regions (IOI09_regions) C++14
90 / 100
 8000 ms 41172 KB 
/**
 *    author:  wxhtzdy
 *    created: 16.07.2022 11:38:01
**/
#include <bits/stdc++.h>

using namespace std;

const int BLOCK = 450;

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 27 ms 512 KB Output is correct
7 Correct 33 ms 464 KB Output is correct
8 Correct 27 ms 464 KB Output is correct
9 Correct 56 ms 1360 KB Output is correct
10 Correct 73 ms 1232 KB Output is correct
11 Correct 84 ms 1744 KB Output is correct
12 Correct 122 ms 2680 KB Output is correct
13 Correct 146 ms 2256 KB Output is correct
14 Correct 185 ms 3200 KB Output is correct
15 Correct 238 ms 8448 KB Output is correct

Subtask #2
75.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 998 ms 8476 KB Output is correct
2 Correct 915 ms 6732 KB Output is correct
3 Correct 1610 ms 11944 KB Output is correct
4 Correct 287 ms 3408 KB Output is correct
5 Correct 338 ms 6728 KB Output is correct
6 Correct 1917 ms 9384 KB Output is correct
7 Correct 1653 ms 8740 KB Output is correct
8 Correct 4037 ms 25784 KB Output is correct
9 Correct 1038 ms 17308 KB Output is correct
10 Correct 5282 ms 37476 KB Output is correct
11 Correct 2193 ms 17904 KB Output is correct
12 Correct 3657 ms 18432 KB Output is correct
13 Correct 4664 ms 19592 KB Output is correct
14 Execution timed out 8044 ms 22660 KB Time limit exceeded
15 Correct 7291 ms 28020 KB Output is correct
16 Correct 6274 ms 40376 KB Output is correct
17 Execution timed out 8016 ms 41172 KB Time limit exceeded