oj.uz

Submission #271935

# Submission time Handle Problem Language Result Execution time Memory
271935 2020-08-18T08:02:05 Z WLZ Regions (IOI09_regions) C++14
75 / 100
 8000 ms 112488 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);
  int k = floor(sqrt(n));
  for (int i = 1; i <= r; i++) {
    sort(reg[i].begin(), reg[i].end());
  }
  vector< vector<long long> > ans1(r + 1), ans2(r + 1);
  for (int i = 1; i <= r; i++) {
    if ((int) reg[i].size() >= k) {
      ans1[i].resize(r + 1);
      ans2[i].resize(r + 1);
      for (int j = 1; j <= r; j++) {
        if (i == j) {
          continue;
        }
        ans1[i][j] = solve(i, j);
        ans2[i][j] = solve(j, i);
      }
    }
  }
  while (q--) {
    int r1, r2;
    cin >> r1 >> r2;
    if ((int) reg[r1].size() >= k) {
      cout << ans1[r1][r2] << endl;
    } else if ((int) reg[r2].size() >= k) {
      cout << ans2[r2][r1] << endl;
    } else {
      cout << solve(r1, r2) << endl;
    }
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 13 ms 384 KB Output is correct
6 Correct 18 ms 512 KB Output is correct
7 Correct 44 ms 512 KB Output is correct
8 Correct 47 ms 512 KB Output is correct
9 Correct 52 ms 1168 KB Output is correct
10 Correct 81 ms 1152 KB Output is correct
11 Correct 142 ms 1964 KB Output is correct
12 Correct 128 ms 2432 KB Output is correct
13 Correct 243 ms 2680 KB Output is correct
14 Correct 432 ms 3704 KB Output is correct
15 Correct 474 ms 7328 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1661 ms 7988 KB Output is correct
2 Correct 1450 ms 6884 KB Output is correct
3 Correct 1935 ms 11012 KB Output is correct
4 Correct 841 ms 9556 KB Output is correct
5 Correct 593 ms 10120 KB Output is correct
6 Correct 2407 ms 11808 KB Output is correct
7 Correct 3080 ms 20440 KB Output is correct
8 Correct 4062 ms 29296 KB Output is correct
9 Correct 6301 ms 39344 KB Output is correct
10 Execution timed out 8106 ms 73656 KB Time limit exceeded
11 Execution timed out 8106 ms 73124 KB Time limit exceeded
12 Correct 5300 ms 17996 KB Output is correct
13 Correct 7658 ms 28976 KB Output is correct
14 Execution timed out 8020 ms 20136 KB Time limit exceeded
15 Correct 6966 ms 24164 KB Output is correct
16 Execution timed out 8031 ms 112488 KB Time limit exceeded
17 Execution timed out 8026 ms 36364 KB Time limit exceeded