oj.uz

Submission #265289

# Submission time Handle Problem Language Result Execution time Memory
265289 2020-08-14T14:56:18 Z WLZ Regions (IOI09_regions) C++14
90 / 100
 8000 ms 61512 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() >= 2 * 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() >= 2 * k) {
      cout << ans1[r1][r2] << endl;
    } else if ((int) reg[r2].size() >= 2 * 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 2 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 8 ms 384 KB Output is correct
6 Correct 15 ms 512 KB Output is correct
7 Correct 24 ms 512 KB Output is correct
8 Correct 31 ms 512 KB Output is correct
9 Correct 52 ms 1152 KB Output is correct
10 Correct 77 ms 1152 KB Output is correct
11 Correct 104 ms 1664 KB Output is correct
12 Correct 136 ms 2552 KB Output is correct
13 Correct 173 ms 2296 KB Output is correct
14 Correct 169 ms 3036 KB Output is correct
15 Correct 210 ms 6520 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 7536 KB Output is correct
2 Correct 921 ms 6332 KB Output is correct
3 Correct 1678 ms 9988 KB Output is correct
4 Correct 248 ms 3320 KB Output is correct
5 Correct 346 ms 5496 KB Output is correct
6 Correct 2181 ms 11808 KB Output is correct
7 Correct 2400 ms 14956 KB Output is correct
8 Correct 3520 ms 29372 KB Output is correct
9 Correct 1499 ms 15800 KB Output is correct
10 Execution timed out 8007 ms 61512 KB Time limit exceeded
11 Correct 2587 ms 17100 KB Output is correct
12 Correct 4842 ms 17992 KB Output is correct
13 Correct 5819 ms 18444 KB Output is correct
14 Execution timed out 8041 ms 20268 KB Time limit exceeded
15 Correct 5500 ms 24260 KB Output is correct
16 Correct 4580 ms 31316 KB Output is correct
17 Correct 6609 ms 36572 KB Output is correct