| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 781930 |
2023-07-13T13:43:37 Z |
jakobrs |
Regions (IOI09_regions) |
C++17 |
|
6063 ms |
71524 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());
}
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
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()) {
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
6 ms |
336 KB |
Output is correct |
| 6 |
Correct |
8 ms |
464 KB |
Output is correct |
| 7 |
Correct |
21 ms |
464 KB |
Output is correct |
| 8 |
Correct |
31 ms |
592 KB |
Output is correct |
| 9 |
Correct |
36 ms |
1360 KB |
Output is correct |
| 10 |
Correct |
68 ms |
1832 KB |
Output is correct |
| 11 |
Correct |
106 ms |
2640 KB |
Output is correct |
| 12 |
Correct |
93 ms |
3864 KB |
Output is correct |
| 13 |
Correct |
93 ms |
4176 KB |
Output is correct |
| 14 |
Correct |
183 ms |
5440 KB |
Output is correct |
| 15 |
Correct |
176 ms |
8944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3729 ms |
12300 KB |
Output is correct |
| 2 |
Correct |
6063 ms |
11956 KB |
Output is correct |
| 3 |
Correct |
5596 ms |
15500 KB |
Output is correct |
| 4 |
Correct |
196 ms |
5504 KB |
Output is correct |
| 5 |
Correct |
306 ms |
7624 KB |
Output is correct |
| 6 |
Correct |
707 ms |
15184 KB |
Output is correct |
| 7 |
Correct |
889 ms |
19772 KB |
Output is correct |
| 8 |
Correct |
948 ms |
34968 KB |
Output is correct |
| 9 |
Correct |
1749 ms |
26840 KB |
Output is correct |
| 10 |
Correct |
2365 ms |
71524 KB |
Output is correct |
| 11 |
Correct |
2557 ms |
31248 KB |
Output is correct |
| 12 |
Correct |
2951 ms |
30740 KB |
Output is correct |
| 13 |
Correct |
3694 ms |
31000 KB |
Output is correct |
| 14 |
Correct |
4159 ms |
38808 KB |
Output is correct |
| 15 |
Correct |
5411 ms |
36556 KB |
Output is correct |
| 16 |
Correct |
5883 ms |
41000 KB |
Output is correct |
| 17 |
Correct |
5841 ms |
47480 KB |
Output is correct |
