oj.uz

Submission #535460

# Submission time Handle Problem Language Result Execution time Memory
535460 2022-03-10T09:50:54 Z chenwz Regions (IOI09_regions) C++11
100 / 100
 3792 ms 46456 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} 时间点:时间点位置到root路径上的cnt
  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 sz1 = reg1.ids.size(), sz2 = reg2.ids.size();
  int costs[2] = {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);

  // return cache[key] = query_by_range(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 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 16 ms 524 KB Output is correct
7 Correct 27 ms 584 KB Output is correct
8 Correct 20 ms 652 KB Output is correct
9 Correct 59 ms 1388 KB Output is correct
10 Correct 98 ms 1776 KB Output is correct
11 Correct 123 ms 2252 KB Output is correct
12 Correct 139 ms 3132 KB Output is correct
13 Correct 169 ms 3016 KB Output is correct
14 Correct 261 ms 3900 KB Output is correct
15 Correct 294 ms 8116 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1226 ms 9536 KB Output is correct
2 Correct 1340 ms 8248 KB Output is correct
3 Correct 2121 ms 14812 KB Output is correct
4 Correct 231 ms 4936 KB Output is correct
5 Correct 393 ms 8084 KB Output is correct
6 Correct 624 ms 7440 KB Output is correct
7 Correct 712 ms 8660 KB Output is correct
8 Correct 1098 ms 19136 KB Output is correct
9 Correct 2068 ms 25000 KB Output is correct
10 Correct 3792 ms 34300 KB Output is correct
11 Correct 3742 ms 29684 KB Output is correct
12 Correct 1339 ms 23448 KB Output is correct
13 Correct 1816 ms 26076 KB Output is correct
14 Correct 2171 ms 27660 KB Output is correct
15 Correct 2609 ms 36840 KB Output is correct
16 Correct 2779 ms 46456 KB Output is correct
17 Correct 2819 ms 43956 KB Output is correct