oj.uz

Submission #535455

# Submission time Handle Problem Language Result Execution time Memory
535455 2022-03-10T09:45:26 Z chenwz Regions (IOI09_regions) C++11
100 / 100
 2273 ms 46736 KB 
// IOI2009 – Regions
#include <bits/stdc++.h>
using namespace std;
using VI = vector<int>;
using IP = pair<int, int>;
using LL = long long;
struct Emp {     // Employee
  int tin, reg;  // tin(dfs时间戳), reg(区域)
  VI ch;         // 被指导的
};
struct Reg {
  VI ids;             // 其中的Employee
  vector<IP> ranges;  // 时间戳排序的 {ID: cnt} cnt是到祖先的同reg数量
  int cnt;
};
vector<Emp> ES;
vector<Reg> RS;
void dfs(int u, int &timer) {
  auto &r = RS[ES[u].reg];
  r.ids.push_back(timer++), r.ranges.push_back({timer, ++r.cnt});
  for (int v : ES[u].ch) dfs(v, timer);
  r.ranges.push_back({timer, --r.cnt});  // 子树u终点，cnt离开子树后祖先的r数量
}
LL query_by_id(const Reg &r1, const Reg &r2) {
  LL ans = 0;  // 针对r2中的每个id，找寻r1中包含id的区间 O(|R2|log|R1|)
  auto &rv = r1.ranges;
  for (int u : r2.ids) {  // 找到第一个起点在u之后的区间，它之前的区间就是目标
    auto it = lower_bound(begin(rv), end(rv), make_pair(u, INT_MAX));
    if (it != rv.begin()) ans += prev(it)->second;
  }
  return ans;
}
LL query_by_range(const Reg &r1, const Reg &r2) {
  LL ans = 0;  // 针对r1中的每个区间，看看r2中有多少个id在其中, O(|R1|log(|R2|))
  const auto &rv = r2.ids;
  for (size_t i = 0; i + 1 < r1.ranges.size(); i++) {
    int p1 = r1.ranges[i].first, p2 = r1.ranges[i + 1].first;
    auto it1 = lower_bound(begin(rv), end(rv), p1),
         it2 = lower_bound(begin(rv), end(rv), p2);
    ans += r1.ranges[i].second * (it2 - it1);
  }
  return ans;
}
LL query_stitch(const Reg &r1, const Reg &r2) {
  LL ans = 0;  // 针对r2中的每个id，线性在r1中查找，时间O(|R1|+|R2|)
  auto p = r2.ids.begin();
  if (r1.ranges.empty()) return ans;
  while (p != r2.ids.end() && *p < r1.ranges[0].first) p++;
  for (size_t i = 0; i + 1 < r1.ranges.size() && p != r2.ids.end(); i++) {
    auto np = p;
    while (np != r2.ids.end() && *np < r1.ranges[i + 1].first) np++;
    ans += r1.ranges[i].second * (np - p), p = np;
  }
  return ans;
}
LL solve(int r1, int r2) {
  static map<IP, LL> cache;
  IP key(r1, r2);
  if (cache.count(key)) return cache[key];
  const Reg &reg1 = RS[r1], &reg2 = RS[r2];
  int sz1 = reg1.ids.size(), sz2 = reg2.ids.size();
  int costs[3] = {sz1 * ((int)log2(sz2) + 2) * 5,
                  sz2 * ((int)log2(sz1) + 2) * 5, sz1 + sz2};
  int k = min_element(costs, costs + 3) - costs;
  if (k == 0) return cache[key] = query_by_range(reg1, reg2);
  if (k == 1) return cache[key] = query_by_id(reg1, reg2);
  return cache[key] = query_stitch(reg1, reg2);
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int N, R, Q, timer = 0;
  cin >> N >> R >> Q, ES.resize(N), RS.resize(R);
  cin >> ES[0].reg, --ES[0].reg;
  for (int i = 1, fa; i < N; i++)
    cin >> fa >> ES[i].reg, --ES[i].reg, ES[fa - 1].ch.push_back(i);
  dfs(0, timer);
  // for (int i = 0; i < R; i++) {
  //   if (RS[i].ids.empty()) continue;
  //   printf("reg %d: ", i + 1);
  //   for (int id : RS[i].ids) printf(" %d, ", id + 1);
  //   puts("");
  //   for (auto p : RS[i].ranges) {
  //     printf("%d(%d),  ", p.first, p.second);
  //   }
  //   puts("");
  // }
  for (int q = 0, r1, r2; q < Q; q++) {
    cin >> r1 >> r2;
    // printf("query : %d-%d\n", r1, r2);
    cout << solve(r1 - 1, r2 - 1) << 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 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 10 ms 660 KB Output is correct
7 Correct 34 ms 544 KB Output is correct
8 Correct 31 ms 676 KB Output is correct
9 Correct 49 ms 1384 KB Output is correct
10 Correct 52 ms 1712 KB Output is correct
11 Correct 104 ms 2248 KB Output is correct
12 Correct 115 ms 3200 KB Output is correct
13 Correct 144 ms 3084 KB Output is correct
14 Correct 185 ms 3832 KB Output is correct
15 Correct 154 ms 8156 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 9520 KB Output is correct
2 Correct 646 ms 8504 KB Output is correct
3 Correct 1511 ms 15052 KB Output is correct
4 Correct 227 ms 4892 KB Output is correct
5 Correct 333 ms 8040 KB Output is correct
6 Correct 502 ms 7564 KB Output is correct
7 Correct 723 ms 8872 KB Output is correct
8 Correct 811 ms 19244 KB Output is correct
9 Correct 1373 ms 25064 KB Output is correct
10 Correct 1992 ms 34316 KB Output is correct
11 Correct 2273 ms 29832 KB Output is correct
12 Correct 1016 ms 23412 KB Output is correct
13 Correct 1391 ms 26196 KB Output is correct
14 Correct 1655 ms 27652 KB Output is correct
15 Correct 2164 ms 36820 KB Output is correct
16 Correct 2269 ms 46736 KB Output is correct
17 Correct 1925 ms 44184 KB Output is correct