oj.uz

답안 #535017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535017 2022-03-09T10:07:24 Z chenwz Regions (IOI09_regions) C++11
100 / 100
 2380 ms 43512 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
  /* Sorted of intervals with the same nesting level. Each pair is
   * (ID, depth) where ID is the left end-point of the interval (inclusive).
   * The right end-point is implicit from the following interval.
   */
  vector<IP> ranges;
  int depth; /* Working depth during the DFS. */
};
vector<Emp> ES;
vector<Reg> RS;
/* Does a pre-order walk over the subtree rooted at root. id_pool contains
 * the next unused employee ID, and on return it will be updated to again
 * be the next available ID.
 * This procedure builds the RS arrays, after which the tree is no longer needed.
 */
void dfs(int u, int &timer) {
  auto& r = RS[ES[u].reg];
  r.ids.push_back(timer++);
  /* Depth changed, so after this point we need a new range */
  r.ranges.push_back({timer, ++r.depth});
  for (int v : ES[u].ch)
    dfs(v, timer);
  /* Undo the depth change, and start another interval after the last managee. */
  r.ranges.push_back({timer, --r.depth});
}
/* Query in O(R2 log R1) time, by counting for each employee in r2. */
LL query_by_id(const Reg &r1, const Reg &r2) {
  LL ans = 0;
  for (int pos : r2.ids) {
    /* Find the first range that starts at pos or later. This will
     * actually be the range after the one we want.
     */
    auto it = lower_bound(r1.ranges.begin(), r1.ranges.end(), make_pair(pos, INT_MAX));
    if (it != r1.ranges.begin())
      ans += prev(it)->second;
  }
  return ans;
}

/* Query in O(R1 log R2) time, by counting for each employee in r1 */
LL query_by_range(const Reg &r1, const Reg &r2) {
  LL ans = 0;
  for (size_t i = 0; i + 1 < r1.ranges.size(); i++) {
    int p1 = r1.ranges[i].first, p2 = r1.ranges[i + 1].first;
    /* Each employee from r2 in [p1, p2) has depth managers
     * from r1. Find the intersections of [p1, p2) with the
     * employee list for r2.
     */
    auto it1 = lower_bound(r2.ids.begin(), r2.ids.end(), p1),
         it2 = lower_bound(r2.ids.begin(), r2.ids.end(), p2);
    ans += r1.ranges[i].second * (it2 - it1);
  }
  return ans;
}

/* Query in O(R1 + R2) time, by counting for each employee in r1
 * but with a linear sweep instead of a binary search.
 */
LL query_stitch(const Reg &r1, const Reg &r2) {
  LL ans = 0;
  /* Find the first employee id that is in the first range */
  auto id = r2.ids.begin();
  if (r1.ranges.empty()) return ans;
  while (id != r2.ids.end() && *id < r1.ranges[0].first) id++;
  /* Iterate over the ranges as above */
  for (size_t i = 0; i + 1 < r1.ranges.size() && id != r2.ids.end(); i++) {
    /* Find the end of the section of employees from this range */
    auto id_bak = id;
    while (id != r2.ids.end() && *id < r1.ranges[i + 1].first)
      id++;
    ans += r1.ranges[i].second * (id - id_bak);
  }
  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 q = 0, r1, r2; q < Q; q++)
    cin >> r1 >> r2, cout << solve(r1 - 1, r2 - 1) << endl;
  return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct
4 Correct 6 ms 324 KB Output is correct
5 Correct 7 ms 380 KB Output is correct
6 Correct 21 ms 704 KB Output is correct
7 Correct 33 ms 548 KB Output is correct
8 Correct 38 ms 676 KB Output is correct
9 Correct 45 ms 1344 KB Output is correct
10 Correct 80 ms 1680 KB Output is correct
11 Correct 113 ms 2272 KB Output is correct
12 Correct 114 ms 3248 KB Output is correct
13 Correct 150 ms 3136 KB Output is correct
14 Correct 173 ms 3832 KB Output is correct
15 Correct 145 ms 7520 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 983 ms 9332 KB Output is correct
2 Correct 961 ms 8304 KB Output is correct
3 Correct 1561 ms 14160 KB Output is correct
4 Correct 244 ms 4892 KB Output is correct
5 Correct 324 ms 7676 KB Output is correct
6 Correct 648 ms 7544 KB Output is correct
7 Correct 616 ms 8752 KB Output is correct
8 Correct 992 ms 18128 KB Output is correct
9 Correct 1495 ms 24844 KB Output is correct
10 Correct 2117 ms 32992 KB Output is correct
11 Correct 2306 ms 29800 KB Output is correct
12 Correct 1014 ms 23512 KB Output is correct
13 Correct 1394 ms 25928 KB Output is correct
14 Correct 1791 ms 27408 KB Output is correct
15 Correct 2245 ms 35672 KB Output is correct
16 Correct 2281 ms 43512 KB Output is correct
17 Correct 2380 ms 41416 KB Output is correct