oj.uz

답안 #265273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
265273 2020-08-14T14:40:51 Z WLZ Regions (IOI09_regions) C++14
95 / 100
 8000 ms 29284 KB 
#include <bits/stdc++.h>
using namespace std;

int n, r, q, cur = 0;
vector<int> h, s;
vector< vector<int> > g;
vector< vector< pair<int, int> > > reg;

int dfs(int u) {
  int st = cur++;
  int en = st;
  for (auto& v : g[u]) {
    en = dfs(v);
  }
  reg[h[u]].push_back({st, 1});
  reg[h[u]].push_back({en, -1});
  return en;
}

long long solve(int r1, int r2) {
  int cur = 0, idx = -1;
  long long ans = 0;
  for (auto& p : reg[r2]) {
    if (p.second == -1) {
      continue;
    }
    while (idx + 1 < (int) reg[r1].size() && reg[r1][idx + 1].first < p.first) {
      idx++;
      cur += reg[r1][idx].second;
    }
    ans += (long long) cur;
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> r >> q;
  h.resize(n + 1);
  s.resize(n + 1);
  cin >> h[1];
  g.resize(n + 1);
  for (int i = 2; i <= n; i++) {
    cin >> s[i] >> h[i];
    g[s[i]].push_back(i);
  }
  reg.resize(r + 1);
  dfs(1);
  for (int i = 1; i <= r; i++) {
    sort(reg[i].begin(), reg[i].end());
  }
  while (q--) {
    int r1, r2;
    cin >> r1 >> r2;
    cout << solve(r1, r2) << endl;
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 17 ms 512 KB Output is correct
7 Correct 27 ms 640 KB Output is correct
8 Correct 30 ms 512 KB Output is correct
9 Correct 44 ms 1280 KB Output is correct
10 Correct 75 ms 1276 KB Output is correct
11 Correct 108 ms 1664 KB Output is correct
12 Correct 131 ms 2552 KB Output is correct
13 Correct 125 ms 2296 KB Output is correct
14 Correct 195 ms 2944 KB Output is correct
15 Correct 226 ms 6400 KB Output is correct

Subtask #2
80.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3974 ms 7412 KB Output is correct
2 Execution timed out 8031 ms 6264 KB Time limit exceeded
3 Correct 5044 ms 9972 KB Output is correct
4 Correct 231 ms 3168 KB Output is correct
5 Correct 367 ms 5248 KB Output is correct
6 Correct 834 ms 4984 KB Output is correct
7 Correct 1190 ms 6652 KB Output is correct
8 Correct 949 ms 13184 KB Output is correct
9 Correct 1758 ms 15096 KB Output is correct
10 Correct 2426 ms 20936 KB Output is correct
11 Correct 3148 ms 16032 KB Output is correct
12 Correct 4343 ms 16624 KB Output is correct
13 Correct 5023 ms 17136 KB Output is correct
14 Correct 7390 ms 17132 KB Output is correct
15 Correct 4970 ms 22256 KB Output is correct
16 Correct 4590 ms 29284 KB Output is correct
17 Correct 5298 ms 28012 KB Output is correct