Submission #781932

#	Time	Username	Problem	Language	Result	Execution time	Memory
781932		jakobrs	Regions (IOI09_regions)	C++17	100 / 100	6186 ms	36980 KiB

regions

#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 (stderr)

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 / 15
• Subtask 2: 85 / 85