Submission #781930

#	Time	Username	Problem	Language	Result	Execution time	Memory
781930		jakobrs	Regions (IOI09_regions)	C++17	100 / 100	6063 ms	71524 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());
  }

  i64 critical_size = std::sqrt((f64)n);
  // std::clog << "Critical size: " << critical_size << '\n';
  std::vector<i64> special_regions;
  std::vector<i64> sridx(n, -1);
  for (i64 i = 0; i < r; i++) {
    if (regions[i].size() >= critical_size) {
      sridx[i] = special_regions.size();
      special_regions.push_back(i);
    }
  }
  // std::clog << "Special regions: " << special_regions.size() << '\n';

  std::vector<std::vector<i64>> lanswers(special_regions.size(),
                                         std::vector<i64>(r, 0));
  std::vector<std::vector<i64>> ranswers(special_regions.size(),
                                         std::vector<i64>(r, 0));

  std::vector<std::reference_wrapper<Node>> nodes_but_in_the_correct_order(
      nodes.begin(), nodes.end());

  std::sort(nodes_but_in_the_correct_order.begin(),
            nodes_but_in_the_correct_order.end(),
            [&](auto &&a, auto &&b) { return a.get().left < b.get().left; });

  // for (auto &node : nodes_but_in_the_correct_order) {
  //   std::cout << "Index:  " << &node.get() - &nodes[0] << '\n';
  //   std::cout << "Range:  " << node.get().left << " to " << node.get().right
  //             << '\n';
  //   std::cout << "Region: " << node.get().region << '\n';
  //   std::cout << "\n";
  // }

  // for (i64 r1 : special_regions) {
  //   i64 a = 0, b = 0;
  //   i64 count = 0;

  //   i64 up = 1;

  //   while (a + 1 < region_end_points[r1].size() && b < n) {
  //     Node &node = nodes_but_in_the_correct_order[b].get();
  //     if (node.left < region_end_points[r1][a].point) {
  //       b++;
  //     } else if (node.left >= region_end_points[r1][a + 1].point) {
  //       a++;
  //       up += region_end_points[r1][a].side ? -1 : 1;
  //     } else {
  //       lanswers[sridx[r1]][node.region] += up;
  //       b++;
  //     }
  //   }
  // }
  // for (i64 r2 : special_regions) {
  //   i64 b = 0;

  //   for (i64 a = 0; a < n; a++) {
  //     Node &node = nodes_but_in_the_correct_order[a].get();

  //     while (b < regions[r2].size() && nodes[regions[r2][b]].left < node.left) {
  //       b += 1;
  //     }

  //     while (b < regions[r2].size() &&
  //            nodes[regions[r2][b]].left < node.right) {
  //       ranswers[sridx[r2]][node.region] += 1;
  //       b += 1;
  //     }

  //     if (b == regions[r2].size())
  //       break;
  //   }
  // }

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

    // if (sridx[r1] != -1) {
    //   std::cout << lanswers[sridx[r1]][r2];
    //   std::cout << "!";
      // } else if (sridx[r2] != -1) {
      //   std::cout << ranswers[sridx[r2]][r1];
      //   std::cout << ":";
    {
      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::cout << std::endl;
  }
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:94:27: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'i64' {aka 'long int'} [-Wsign-compare]
   94 |     if (regions[i].size() >= critical_size) {
      |         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
regions.cpp:178:20: 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]
  178 |       while (a + 1 < region_end_points[r1].size() && b < regions[r2].size()) {
      |              ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:178:56: 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]
  178 |       while (a + 1 < region_end_points[r1].size() && b < regions[r2].size()) {
      |                                                      ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85