oj.uz

Submission #781932

# Submission time Handle Problem Language Result Execution time Memory
781932 2023-07-13T13:47:52 Z jakobrs Regions (IOI09_regions) C++17
100 / 100
 6186 ms 36980 KB 
#include <algorithm>
#include <cmath>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>

using i64 = int64_t;
using f64 = double;

struct Node {
  i64 region;
  i64 parent;

  std::vector<i64> children;

  i64 left = -1, right = -1;
};

void dfs(std::vector<Node> &nodes, i64 node, i64 &counter) {
  nodes[node].left = counter++;

  for (i64 child : nodes[node].children) {
    dfs(nodes, child, counter);
  }

  nodes[node].right = counter;
}

int main() {
  i64 n, r, q;
  std::cin >> n >> r >> q;

  std::vector<Node> nodes(n);
  std::vector<std::vector<i64>> regions(r);
  {
    i64 h;
    std::cin >> h;
    nodes[0] = {
        .region = h - 1,
        .parent = -1,
    };
    regions[h - 1].push_back(0);
  }

  for (i64 i = 1; i < n; i++) {
    i64 s, h;
    std::cin >> s >> h;
    nodes[i] = {
        .region = h - 1,
        .parent = s - 1,
    };
    regions[h - 1].push_back(i);
    nodes[s - 1].children.push_back(i);
  }

  i64 counter = 0;
  dfs(nodes, 0, counter);

  auto correct_comparator = [&](i64 lhs, i64 rhs) {
    return nodes[lhs].left < nodes[rhs].left;
  };

  for (i64 i = 0; i < r; i++) {
    std::sort(regions[i].begin(), regions[i].end(), correct_comparator);
  }

  struct Endpoint {
    bool side;
    i64 point;

    bool operator<(const Endpoint &rhs) const {
      return std::make_tuple(point, !side) <
             std::make_tuple(rhs.point, !rhs.side);
    }
  };

  std::vector<std::vector<Endpoint>> region_end_points(r);
  for (i64 i = 0; i < n; i++) {
    region_end_points[nodes[i].region].push_back(
        {.side = false, .point = nodes[i].left});
    region_end_points[nodes[i].region].push_back(
        {.side = true, .point = nodes[i].right});
  }
  for (i64 i = 0; i < r; i++) {
    std::sort(region_end_points[i].begin(), region_end_points[i].end());
  }

  for (i64 i = 0; i < q; i++) {
    i64 r1, r2;
    std::cin >> r1 >> r2;
    r1--, r2--;

    i64 a = 0, b = 0;
    i64 count = 0;

    i64 up = 1;

    while (a + 1 < region_end_points[r1].size() && b < regions[r2].size()) {
      if (nodes[regions[r2][b]].left < region_end_points[r1][a].point) {
        b++;
      } else if (nodes[regions[r2][b]].left >=
                 region_end_points[r1][a + 1].point) {
        a++;
        up += region_end_points[r1][a].side ? -1 : 1;
      } else {
        count += up;
        b++;
      }
    }

    std::cout << count << std::endl;
  }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:99:18: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'std::vector<main()::Endpoint>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     while (a + 1 < region_end_points[r1].size() && b < regions[r2].size()) {
      |            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:99:54: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     while (a + 1 < region_end_points[r1].size() && b < regions[r2].size()) {
      |                                                    ~~^~~~~~~~~~~~~~~~~~~~

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 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 17 ms 336 KB Output is correct
7 Correct 23 ms 464 KB Output is correct
8 Correct 32 ms 592 KB Output is correct
9 Correct 38 ms 1232 KB Output is correct
10 Correct 54 ms 1744 KB Output is correct
11 Correct 75 ms 2512 KB Output is correct
12 Correct 99 ms 3460 KB Output is correct
13 Correct 156 ms 3804 KB Output is correct
14 Correct 173 ms 4976 KB Output is correct
15 Correct 213 ms 8304 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3648 ms 11104 KB Output is correct
2 Correct 6186 ms 10696 KB Output is correct
3 Correct 5588 ms 14164 KB Output is correct
4 Correct 209 ms 5004 KB Output is correct
5 Correct 276 ms 6944 KB Output is correct
6 Correct 747 ms 7796 KB Output is correct
7 Correct 930 ms 10764 KB Output is correct
8 Correct 934 ms 17668 KB Output is correct
9 Correct 1646 ms 24380 KB Output is correct
10 Correct 2735 ms 29448 KB Output is correct
11 Correct 2781 ms 27916 KB Output is correct
12 Correct 3115 ms 27064 KB Output is correct
13 Correct 3758 ms 27392 KB Output is correct
14 Correct 4608 ms 28620 KB Output is correct
15 Correct 4967 ms 32804 KB Output is correct
16 Correct 6101 ms 36884 KB Output is correct
17 Correct 6181 ms 36980 KB Output is correct