#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
template <size_t N>
struct dsu
{
int64_t p[N];
dsu() { fill(p, p + N, -1); }
int64_t repr(int64_t u) { return p[u] < 0 ? u : p[u] = repr(p[u]); }
bool merge(int64_t i, int64_t j)
{
i = repr(i);
j = repr(j);
if (i == j)
return 0;
if (p[i] > p[j])
swap(i, j);
p[i] += p[j];
p[j] = i;
return 1;
}
bool same_set(int64_t i, int64_t j) { return repr(i) == repr(j); }
int64_t set_size(int64_t i) { return -p[repr(i)]; }
void reset() { fill(p.begin(), p.end(), -1); }
};
struct fountain
{
int x, y;
size_t i;
};
constexpr size_t N = 200000;
fountain f[N];
vector<pair<size_t, size_t>> edges;
vector<uint32_t> dual[N];
dsu<N> d;
set<pair<int, int>> points, marked;
set<tuple<int, int, uint32_t>> midpoints;
pair<int, int> dual_coords[N];
void mark_cut_points(uint32_t u, uint32_t p = -1)
{
for (auto const &v : dual[u])
if (v != p)
{
marked.emplace((dual_coords[u].first + dual_coords[v].first) >> 1, (dual_coords[u].second + dual_coords[v].second) >> 1);
mark_cut_points(v, u);
}
}
int construct_roads(vector<int> x, vector<int> y)
{
size_t n = x.size();
for (size_t i = 0; i < n; ++i)
points.emplace(x[i], y[i]);
size_t l = 0;
for (size_t i = 0; i < n; ++i)
if (points.find({x[i] + 2, y[i]}) != points.end() &&
points.find({x[i], y[i] + 2}) != points.end() &&
points.find({x[i] + 2, y[i] + 2}) != points.end())
midpoints.emplace(x[i] + 1, y[i] + 1, l++), dual_coords[l - 1] = {x[i] + 1, y[i] + 1};
for (auto const &[x, y, i] : midpoints)
{
auto it = midpoints.lower_bound({x + 2, y, 0});
if (it != midpoints.end() && get<0>(*it) == x + 2 && get<1>(*it) == y)
dual[i].push_back(get<2>(*it)), dual[get<2>(*it)].push_back(i);
it = midpoints.lower_bound({x, y + 2, 0});
if (it != midpoints.end() && get<0>(*it) == x && get<1>(*it) == y + 2)
dual[i].push_back(get<2>(*it)), dual[get<2>(*it)].push_back(i);
}
for (size_t i = 0; i < l; ++i)
if (dual[i].size() < 4)
dual[l].push_back(i), dual[i].push_back(l);
mark_cut_points(l);
for (size_t i = 0; i < x.size(); ++i)
f[i].i = i, f[i].x = x[i], f[i].y = y[i];
sort(f, f + n, [](auto const &a, auto const &b)
{ return a.y == b.y ? a.x < b.x : a.y < b.y; });
for (size_t i = 0; i < n;)
{
size_t j = i;
while (j < n && f[j].y == f[i].y)
++j;
for (size_t k = i + 1; k < j; ++k)
if (f[k - 1].x + 2 == f[k].x)
if (marked.find({f[k - 1].x + 1, f[k - 1].y}) == marked.end() &&
d.merge(f[k - 1].i, f[k].i))
edges.emplace_back(f[k - 1].i, f[k].i);
if (f[j].y == f[i].y + 2)
{
size_t k = j;
while (i < j && k < n && f[k].y == f[j].y)
{
if (f[i].x < f[k].x)
++i;
else if (f[k].x < f[i].x)
++k;
else
{
if (marked.find({f[i].x, f[i].y + 1}) == marked.end() &&
d.merge(f[i].i, f[k].i))
edges.emplace_back(f[k].i, f[i].i);
++i;
++k;
}
}
}
i = j;
}
if (d.set_size(0) != n)
return 0;
vector<int> u, v, a, b;
for (auto const &[i, j] : edges)
{
u.push_back(i);
v.push_back(j);
if (x[i] == x[j])
{
b.push_back((y[i] + y[j]) >> 1);
if (((x[i] & 3) == 2) ^ ((min(y[i], y[j]) & 3) == 2))
a.push_back(x[i] - 1);
else
a.push_back(x[i] + 1);
}
else
{
a.push_back((x[i] + x[j]) >> 1);
if (((y[i] & 3) == 2) ^ ((min(x[i], x[j]) & 3) == 2))
b.push_back(y[i] + 1);
else
b.push_back(y[i] - 1);
}
}
build(u, v, a, b);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:127:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
127 | if (d.set_size(0) != n)
| ~~~~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6484 KB |
Output is correct |
3 |
Correct |
3 ms |
6484 KB |
Output is correct |
4 |
Correct |
3 ms |
6472 KB |
Output is correct |
5 |
Correct |
3 ms |
6484 KB |
Output is correct |
6 |
Correct |
3 ms |
6484 KB |
Output is correct |
7 |
Correct |
4 ms |
6516 KB |
Output is correct |
8 |
Correct |
3 ms |
6484 KB |
Output is correct |
9 |
Correct |
80 ms |
22196 KB |
Output is correct |
10 |
Correct |
9 ms |
8152 KB |
Output is correct |
11 |
Correct |
41 ms |
15012 KB |
Output is correct |
12 |
Correct |
11 ms |
8920 KB |
Output is correct |
13 |
Correct |
18 ms |
11156 KB |
Output is correct |
14 |
Correct |
3 ms |
6612 KB |
Output is correct |
15 |
Correct |
3 ms |
6740 KB |
Output is correct |
16 |
Correct |
80 ms |
22188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6484 KB |
Output is correct |
3 |
Correct |
3 ms |
6484 KB |
Output is correct |
4 |
Correct |
3 ms |
6472 KB |
Output is correct |
5 |
Correct |
3 ms |
6484 KB |
Output is correct |
6 |
Correct |
3 ms |
6484 KB |
Output is correct |
7 |
Correct |
4 ms |
6516 KB |
Output is correct |
8 |
Correct |
3 ms |
6484 KB |
Output is correct |
9 |
Correct |
80 ms |
22196 KB |
Output is correct |
10 |
Correct |
9 ms |
8152 KB |
Output is correct |
11 |
Correct |
41 ms |
15012 KB |
Output is correct |
12 |
Correct |
11 ms |
8920 KB |
Output is correct |
13 |
Correct |
18 ms |
11156 KB |
Output is correct |
14 |
Correct |
3 ms |
6612 KB |
Output is correct |
15 |
Correct |
3 ms |
6740 KB |
Output is correct |
16 |
Correct |
80 ms |
22188 KB |
Output is correct |
17 |
Incorrect |
3 ms |
6484 KB |
Tree @(3, 3) appears more than once: for edges on positions 1 and 2 |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6484 KB |
Output is correct |
3 |
Correct |
3 ms |
6484 KB |
Output is correct |
4 |
Correct |
3 ms |
6472 KB |
Output is correct |
5 |
Correct |
3 ms |
6484 KB |
Output is correct |
6 |
Correct |
3 ms |
6484 KB |
Output is correct |
7 |
Correct |
4 ms |
6516 KB |
Output is correct |
8 |
Correct |
3 ms |
6484 KB |
Output is correct |
9 |
Correct |
80 ms |
22196 KB |
Output is correct |
10 |
Correct |
9 ms |
8152 KB |
Output is correct |
11 |
Correct |
41 ms |
15012 KB |
Output is correct |
12 |
Correct |
11 ms |
8920 KB |
Output is correct |
13 |
Correct |
18 ms |
11156 KB |
Output is correct |
14 |
Correct |
3 ms |
6612 KB |
Output is correct |
15 |
Correct |
3 ms |
6740 KB |
Output is correct |
16 |
Correct |
80 ms |
22188 KB |
Output is correct |
17 |
Incorrect |
3 ms |
6484 KB |
Tree @(3, 3) appears more than once: for edges on positions 1 and 2 |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6484 KB |
Output is correct |
3 |
Correct |
3 ms |
6484 KB |
Output is correct |
4 |
Correct |
3 ms |
6472 KB |
Output is correct |
5 |
Correct |
3 ms |
6484 KB |
Output is correct |
6 |
Correct |
3 ms |
6484 KB |
Output is correct |
7 |
Correct |
4 ms |
6516 KB |
Output is correct |
8 |
Correct |
3 ms |
6484 KB |
Output is correct |
9 |
Correct |
80 ms |
22196 KB |
Output is correct |
10 |
Correct |
9 ms |
8152 KB |
Output is correct |
11 |
Correct |
41 ms |
15012 KB |
Output is correct |
12 |
Correct |
11 ms |
8920 KB |
Output is correct |
13 |
Correct |
18 ms |
11156 KB |
Output is correct |
14 |
Correct |
3 ms |
6612 KB |
Output is correct |
15 |
Correct |
3 ms |
6740 KB |
Output is correct |
16 |
Correct |
80 ms |
22188 KB |
Output is correct |
17 |
Correct |
3 ms |
6484 KB |
Output is correct |
18 |
Correct |
3 ms |
6484 KB |
Output is correct |
19 |
Correct |
3 ms |
6484 KB |
Output is correct |
20 |
Correct |
248 ms |
39016 KB |
Output is correct |
21 |
Correct |
245 ms |
38864 KB |
Output is correct |
22 |
Correct |
255 ms |
38988 KB |
Output is correct |
23 |
Correct |
189 ms |
34208 KB |
Output is correct |
24 |
Correct |
139 ms |
22108 KB |
Output is correct |
25 |
Correct |
207 ms |
26344 KB |
Output is correct |
26 |
Correct |
148 ms |
26380 KB |
Output is correct |
27 |
Correct |
200 ms |
38596 KB |
Output is correct |
28 |
Correct |
198 ms |
38160 KB |
Output is correct |
29 |
Correct |
257 ms |
38064 KB |
Output is correct |
30 |
Correct |
251 ms |
38160 KB |
Output is correct |
31 |
Correct |
2 ms |
6484 KB |
Output is correct |
32 |
Correct |
15 ms |
8892 KB |
Output is correct |
33 |
Correct |
64 ms |
14376 KB |
Output is correct |
34 |
Correct |
216 ms |
39076 KB |
Output is correct |
35 |
Correct |
9 ms |
7740 KB |
Output is correct |
36 |
Correct |
41 ms |
11628 KB |
Output is correct |
37 |
Correct |
92 ms |
16568 KB |
Output is correct |
38 |
Correct |
90 ms |
19784 KB |
Output is correct |
39 |
Correct |
129 ms |
24228 KB |
Output is correct |
40 |
Correct |
171 ms |
30232 KB |
Output is correct |
41 |
Correct |
256 ms |
34320 KB |
Output is correct |
42 |
Correct |
271 ms |
39692 KB |
Output is correct |
43 |
Correct |
3 ms |
6484 KB |
Output is correct |
44 |
Correct |
3 ms |
6484 KB |
Output is correct |
45 |
Correct |
3 ms |
6484 KB |
Output is correct |
46 |
Correct |
3 ms |
6484 KB |
Output is correct |
47 |
Correct |
3 ms |
6484 KB |
Output is correct |
48 |
Correct |
3 ms |
6484 KB |
Output is correct |
49 |
Correct |
3 ms |
6484 KB |
Output is correct |
50 |
Correct |
3 ms |
6484 KB |
Output is correct |
51 |
Correct |
3 ms |
6484 KB |
Output is correct |
52 |
Correct |
3 ms |
6484 KB |
Output is correct |
53 |
Correct |
3 ms |
6484 KB |
Output is correct |
54 |
Correct |
4 ms |
6740 KB |
Output is correct |
55 |
Correct |
4 ms |
6868 KB |
Output is correct |
56 |
Correct |
95 ms |
22276 KB |
Output is correct |
57 |
Correct |
148 ms |
30160 KB |
Output is correct |
58 |
Correct |
144 ms |
30220 KB |
Output is correct |
59 |
Correct |
2 ms |
6484 KB |
Output is correct |
60 |
Correct |
3 ms |
6484 KB |
Output is correct |
61 |
Correct |
3 ms |
6484 KB |
Output is correct |
62 |
Correct |
178 ms |
38132 KB |
Output is correct |
63 |
Correct |
172 ms |
38176 KB |
Output is correct |
64 |
Correct |
179 ms |
38108 KB |
Output is correct |
65 |
Correct |
5 ms |
6952 KB |
Output is correct |
66 |
Correct |
7 ms |
7444 KB |
Output is correct |
67 |
Correct |
97 ms |
22144 KB |
Output is correct |
68 |
Correct |
175 ms |
30980 KB |
Output is correct |
69 |
Correct |
268 ms |
38116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6484 KB |
Output is correct |
3 |
Correct |
3 ms |
6484 KB |
Output is correct |
4 |
Correct |
3 ms |
6472 KB |
Output is correct |
5 |
Correct |
3 ms |
6484 KB |
Output is correct |
6 |
Correct |
3 ms |
6484 KB |
Output is correct |
7 |
Correct |
4 ms |
6516 KB |
Output is correct |
8 |
Correct |
3 ms |
6484 KB |
Output is correct |
9 |
Correct |
80 ms |
22196 KB |
Output is correct |
10 |
Correct |
9 ms |
8152 KB |
Output is correct |
11 |
Correct |
41 ms |
15012 KB |
Output is correct |
12 |
Correct |
11 ms |
8920 KB |
Output is correct |
13 |
Correct |
18 ms |
11156 KB |
Output is correct |
14 |
Correct |
3 ms |
6612 KB |
Output is correct |
15 |
Correct |
3 ms |
6740 KB |
Output is correct |
16 |
Correct |
80 ms |
22188 KB |
Output is correct |
17 |
Correct |
203 ms |
38492 KB |
Output is correct |
18 |
Correct |
204 ms |
38684 KB |
Output is correct |
19 |
Correct |
229 ms |
38800 KB |
Output is correct |
20 |
Correct |
278 ms |
37520 KB |
Output is correct |
21 |
Correct |
203 ms |
34336 KB |
Output is correct |
22 |
Correct |
3 ms |
6484 KB |
Output is correct |
23 |
Correct |
33 ms |
11724 KB |
Output is correct |
24 |
Correct |
17 ms |
8732 KB |
Output is correct |
25 |
Correct |
71 ms |
14140 KB |
Output is correct |
26 |
Correct |
108 ms |
18052 KB |
Output is correct |
27 |
Correct |
116 ms |
22680 KB |
Output is correct |
28 |
Correct |
150 ms |
26536 KB |
Output is correct |
29 |
Correct |
190 ms |
31768 KB |
Output is correct |
30 |
Correct |
224 ms |
35232 KB |
Output is correct |
31 |
Correct |
256 ms |
39056 KB |
Output is correct |
32 |
Correct |
212 ms |
38160 KB |
Output is correct |
33 |
Correct |
181 ms |
38164 KB |
Output is correct |
34 |
Correct |
5 ms |
7124 KB |
Output is correct |
35 |
Correct |
7 ms |
7636 KB |
Output is correct |
36 |
Correct |
110 ms |
22448 KB |
Output is correct |
37 |
Correct |
154 ms |
30988 KB |
Output is correct |
38 |
Correct |
234 ms |
38168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
6484 KB |
Output is correct |
2 |
Correct |
3 ms |
6484 KB |
Output is correct |
3 |
Correct |
3 ms |
6484 KB |
Output is correct |
4 |
Correct |
3 ms |
6472 KB |
Output is correct |
5 |
Correct |
3 ms |
6484 KB |
Output is correct |
6 |
Correct |
3 ms |
6484 KB |
Output is correct |
7 |
Correct |
4 ms |
6516 KB |
Output is correct |
8 |
Correct |
3 ms |
6484 KB |
Output is correct |
9 |
Correct |
80 ms |
22196 KB |
Output is correct |
10 |
Correct |
9 ms |
8152 KB |
Output is correct |
11 |
Correct |
41 ms |
15012 KB |
Output is correct |
12 |
Correct |
11 ms |
8920 KB |
Output is correct |
13 |
Correct |
18 ms |
11156 KB |
Output is correct |
14 |
Correct |
3 ms |
6612 KB |
Output is correct |
15 |
Correct |
3 ms |
6740 KB |
Output is correct |
16 |
Correct |
80 ms |
22188 KB |
Output is correct |
17 |
Incorrect |
3 ms |
6484 KB |
Tree @(3, 3) appears more than once: for edges on positions 1 and 2 |
18 |
Halted |
0 ms |
0 KB |
- |