oj.uz

Submission #535456

# Submission time Handle Problem Language Result Execution time Memory
535456 2022-03-10T09:47:09 Z chenwz Regions (IOI09_regions) C++11
80 / 100
 8000 ms 42392 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);

  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 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 4 ms 352 KB Output is correct
5 Correct 6 ms 412 KB Output is correct
6 Correct 18 ms 528 KB Output is correct
7 Correct 25 ms 728 KB Output is correct
8 Correct 29 ms 640 KB Output is correct
9 Correct 50 ms 1432 KB Output is correct
10 Correct 71 ms 1664 KB Output is correct
11 Correct 115 ms 2308 KB Output is correct
12 Correct 115 ms 3300 KB Output is correct
13 Correct 167 ms 3016 KB Output is correct
14 Correct 236 ms 3952 KB Output is correct
15 Correct 296 ms 8048 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1163 ms 9480 KB Output is correct
2 Correct 1353 ms 8380 KB Output is correct
3 Correct 2218 ms 14812 KB Output is correct
4 Correct 298 ms 4908 KB Output is correct
5 Correct 429 ms 7972 KB Output is correct
6 Correct 580 ms 7528 KB Output is correct
7 Correct 647 ms 8660 KB Output is correct
8 Correct 1336 ms 19184 KB Output is correct
9 Correct 2372 ms 24996 KB Output is correct
10 Correct 4451 ms 34312 KB Output is correct
11 Correct 3893 ms 29796 KB Output is correct
12 Correct 6606 ms 23548 KB Output is correct
13 Correct 7878 ms 26280 KB Output is correct
14 Execution timed out 8023 ms 26344 KB Time limit exceeded
15 Execution timed out 8064 ms 34176 KB Time limit exceeded
16 Execution timed out 8045 ms 42392 KB Time limit exceeded
17 Execution timed out 8035 ms 42120 KB Time limit exceeded