#include "parks.h"
#include <map>
#include <set>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int uf[200006];
int _find(int x) {
if (uf[x] == -1) return x;
return uf[x] = _find(uf[x]);
}
void _merge(int x, int y) {
x = _find(x), y = _find(y);
if (x != y) uf[x] = y;
}
map<pair<int, int>, int> m;
set<pair<int, int>> s;
int construct_roads(vector<int> x, vector<int> y) {
if ((int)x.size() == 1) return build({}, {}, {}, {}), 1;
int n = (int)x.size();
for (int i = 0; i < n; i++) uf[i] = -1;
vector<int> u, v, a, b;
vector<pair<int, int>> edges, n_edges;
vector<int> points;
for (int i = 0; i < n; i++) m[{ x[i], y[i] }] = i;
for (int i = 0; i < n; i++) if (m.count({ x[i], y[i] - 2 })) {
edges.push_back({ m[{ x[i], y[i] - 2 }], i });
_merge(edges.back().first, edges.back().second);
}
for (int i = 0; i < n; i++) if (!m.count({ x[i], y[i] - 2 }) || !m.count({ x[i], y[i] + 2 })) points.push_back(i);
sort(points.begin(), points.end(), [&](const int &a, const int &b) {
if (y[a] != y[b]) return y[a] < y[b];
return x[a] < x[b];
});
for (int t = 0; t < (int)points.size(); t++) {
int i = points[t];
if (m.count({ x[i] - 2, y[i] })) {
int t = m[{ x[i] - 2, y[i] }];
if (_find(t) != _find(i)) {
edges.push_back({ t, i });
_merge(t, i);
}
}
}
for (int t = 0; t < (int)points.size(); t++) {
int i = points[t];
if (m.count({ x[i] + 2, y[i] })) {
int t = m[{ x[i] + 2, y[i] }];
if (_find(t) != _find(i)) {
edges.push_back({ t, i });
_merge(t, i);
}
}
}
for (int i = 1; i < n; i++) if (_find(0) != _find(i)) return 0;
//int min_x = *min_element(x.begin(), x.end()), max_x = *max_element(x.begin(), x.end());
for (auto &i: edges) {
/*if (x[i.first] == x[i.second]) {
u.push_back(i.first);
v.push_back(i.second);
a.push_back(x[i.first] - 1);
b.push_back((y[i.first] + y[i.second]) / 2);
s.insert({ a.back(), b.back() });
} else*/ n_edges.push_back(i);
}
sort(n_edges.begin(), n_edges.end(), [&](const pair<int, int> &a, const pair<int, int> &b) {
if ((x[a.first] == x[a.second]) != (x[b.first] == x[b.second])) return x[a.first] == x[a.second];
if (x[a.first] + x[a.second] != x[b.first] + x[b.second]) return x[a.first] + x[a.second] < x[b.first] + x[b.second];
return y[a.first] + y[a.second] < y[b.first] + y[b.second];
});
for (auto &i: n_edges) {
if (x[i.first] == x[i.second]) {
if (!s.count({ x[i.first] - 1, (y[i.first] + y[i.second]) / 2 })) {
s.insert({ x[i.first] - 1, (y[i.first] + y[i.second]) / 2 });
u.push_back(i.first);
v.push_back(i.second);
a.push_back(x[i.first] - 1);
b.push_back((y[i.first] + y[i.second]) / 2);
} else {
if (s.count({ x[i.first] + 1, (y[i.first] + y[i.second]) / 2 })) return 0;
s.insert({ x[i.first] + 1, (y[i.first] + y[i.second]) / 2 });
u.push_back(i.first);
v.push_back(i.second);
a.push_back(x[i.first] + 1);
b.push_back((y[i.first] + y[i.second]) / 2);
}
} else {
if (!s.count({ (x[i.first] + x[i.second]) / 2, y[i.first] - 1 })) {
s.insert({ (x[i.first] + x[i.second]) / 2, y[i.first] - 1 });
u.push_back(i.first);
v.push_back(i.second);
a.push_back((x[i.first] + x[i.second]) / 2);
b.push_back(y[i.first] - 1);
} else {
if (s.count({ (x[i.first] + x[i.second]) / 2, y[i.first] + 1 })) return 0;
s.insert({ (x[i.first] + x[i.second]) / 2, y[i.first] + 1 });
u.push_back(i.first);
v.push_back(i.second);
a.push_back((x[i.first] + x[i.second]) / 2);
b.push_back(y[i.first] + 1);
}
}
}
build(u, v, a, b);
return 1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
263 ms |
19540 KB |
Output is correct |
10 |
Correct |
15 ms |
2488 KB |
Output is correct |
11 |
Correct |
95 ms |
11336 KB |
Output is correct |
12 |
Correct |
22 ms |
3624 KB |
Output is correct |
13 |
Correct |
39 ms |
4804 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
460 KB |
Output is correct |
16 |
Correct |
266 ms |
19528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
263 ms |
19540 KB |
Output is correct |
10 |
Correct |
15 ms |
2488 KB |
Output is correct |
11 |
Correct |
95 ms |
11336 KB |
Output is correct |
12 |
Correct |
22 ms |
3624 KB |
Output is correct |
13 |
Correct |
39 ms |
4804 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
460 KB |
Output is correct |
16 |
Correct |
266 ms |
19528 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
712 ms |
38860 KB |
Output is correct |
24 |
Correct |
0 ms |
204 KB |
Output is correct |
25 |
Correct |
3 ms |
460 KB |
Output is correct |
26 |
Correct |
3 ms |
460 KB |
Output is correct |
27 |
Correct |
4 ms |
592 KB |
Output is correct |
28 |
Correct |
195 ms |
15812 KB |
Output is correct |
29 |
Correct |
348 ms |
23256 KB |
Output is correct |
30 |
Correct |
502 ms |
31412 KB |
Output is correct |
31 |
Correct |
732 ms |
38968 KB |
Output is correct |
32 |
Correct |
0 ms |
204 KB |
Output is correct |
33 |
Correct |
0 ms |
204 KB |
Output is correct |
34 |
Correct |
0 ms |
204 KB |
Output is correct |
35 |
Correct |
0 ms |
204 KB |
Output is correct |
36 |
Correct |
0 ms |
204 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
1 ms |
204 KB |
Output is correct |
39 |
Correct |
1 ms |
204 KB |
Output is correct |
40 |
Correct |
0 ms |
204 KB |
Output is correct |
41 |
Correct |
0 ms |
204 KB |
Output is correct |
42 |
Correct |
0 ms |
204 KB |
Output is correct |
43 |
Correct |
3 ms |
460 KB |
Output is correct |
44 |
Correct |
3 ms |
588 KB |
Output is correct |
45 |
Incorrect |
228 ms |
15324 KB |
Solution announced impossible, but it is possible. |
46 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
263 ms |
19540 KB |
Output is correct |
10 |
Correct |
15 ms |
2488 KB |
Output is correct |
11 |
Correct |
95 ms |
11336 KB |
Output is correct |
12 |
Correct |
22 ms |
3624 KB |
Output is correct |
13 |
Correct |
39 ms |
4804 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
460 KB |
Output is correct |
16 |
Correct |
266 ms |
19528 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
712 ms |
38860 KB |
Output is correct |
24 |
Correct |
0 ms |
204 KB |
Output is correct |
25 |
Correct |
3 ms |
460 KB |
Output is correct |
26 |
Correct |
3 ms |
460 KB |
Output is correct |
27 |
Correct |
4 ms |
592 KB |
Output is correct |
28 |
Correct |
195 ms |
15812 KB |
Output is correct |
29 |
Correct |
348 ms |
23256 KB |
Output is correct |
30 |
Correct |
502 ms |
31412 KB |
Output is correct |
31 |
Correct |
732 ms |
38968 KB |
Output is correct |
32 |
Correct |
0 ms |
204 KB |
Output is correct |
33 |
Correct |
0 ms |
204 KB |
Output is correct |
34 |
Correct |
0 ms |
204 KB |
Output is correct |
35 |
Correct |
0 ms |
204 KB |
Output is correct |
36 |
Correct |
0 ms |
204 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
1 ms |
204 KB |
Output is correct |
39 |
Correct |
1 ms |
204 KB |
Output is correct |
40 |
Correct |
0 ms |
204 KB |
Output is correct |
41 |
Correct |
0 ms |
204 KB |
Output is correct |
42 |
Correct |
0 ms |
204 KB |
Output is correct |
43 |
Correct |
3 ms |
460 KB |
Output is correct |
44 |
Correct |
3 ms |
588 KB |
Output is correct |
45 |
Incorrect |
228 ms |
15324 KB |
Solution announced impossible, but it is possible. |
46 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
263 ms |
19540 KB |
Output is correct |
10 |
Correct |
15 ms |
2488 KB |
Output is correct |
11 |
Correct |
95 ms |
11336 KB |
Output is correct |
12 |
Correct |
22 ms |
3624 KB |
Output is correct |
13 |
Correct |
39 ms |
4804 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
460 KB |
Output is correct |
16 |
Correct |
266 ms |
19528 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
809 ms |
39684 KB |
Output is correct |
21 |
Correct |
777 ms |
40888 KB |
Output is correct |
22 |
Correct |
831 ms |
39636 KB |
Output is correct |
23 |
Correct |
620 ms |
34444 KB |
Output is correct |
24 |
Correct |
547 ms |
17860 KB |
Output is correct |
25 |
Correct |
655 ms |
19640 KB |
Output is correct |
26 |
Correct |
496 ms |
18896 KB |
Output is correct |
27 |
Correct |
691 ms |
38976 KB |
Output is correct |
28 |
Correct |
704 ms |
38868 KB |
Output is correct |
29 |
Correct |
882 ms |
39792 KB |
Output is correct |
30 |
Incorrect |
831 ms |
33288 KB |
Solution announced impossible, but it is possible. |
31 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
263 ms |
19540 KB |
Output is correct |
10 |
Correct |
15 ms |
2488 KB |
Output is correct |
11 |
Correct |
95 ms |
11336 KB |
Output is correct |
12 |
Correct |
22 ms |
3624 KB |
Output is correct |
13 |
Correct |
39 ms |
4804 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
460 KB |
Output is correct |
16 |
Correct |
266 ms |
19528 KB |
Output is correct |
17 |
Correct |
744 ms |
39904 KB |
Output is correct |
18 |
Correct |
780 ms |
39824 KB |
Output is correct |
19 |
Incorrect |
732 ms |
27676 KB |
Solution announced impossible, but it is possible. |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
263 ms |
19540 KB |
Output is correct |
10 |
Correct |
15 ms |
2488 KB |
Output is correct |
11 |
Correct |
95 ms |
11336 KB |
Output is correct |
12 |
Correct |
22 ms |
3624 KB |
Output is correct |
13 |
Correct |
39 ms |
4804 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
460 KB |
Output is correct |
16 |
Correct |
266 ms |
19528 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
712 ms |
38860 KB |
Output is correct |
24 |
Correct |
0 ms |
204 KB |
Output is correct |
25 |
Correct |
3 ms |
460 KB |
Output is correct |
26 |
Correct |
3 ms |
460 KB |
Output is correct |
27 |
Correct |
4 ms |
592 KB |
Output is correct |
28 |
Correct |
195 ms |
15812 KB |
Output is correct |
29 |
Correct |
348 ms |
23256 KB |
Output is correct |
30 |
Correct |
502 ms |
31412 KB |
Output is correct |
31 |
Correct |
732 ms |
38968 KB |
Output is correct |
32 |
Correct |
0 ms |
204 KB |
Output is correct |
33 |
Correct |
0 ms |
204 KB |
Output is correct |
34 |
Correct |
0 ms |
204 KB |
Output is correct |
35 |
Correct |
0 ms |
204 KB |
Output is correct |
36 |
Correct |
0 ms |
204 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
1 ms |
204 KB |
Output is correct |
39 |
Correct |
1 ms |
204 KB |
Output is correct |
40 |
Correct |
0 ms |
204 KB |
Output is correct |
41 |
Correct |
0 ms |
204 KB |
Output is correct |
42 |
Correct |
0 ms |
204 KB |
Output is correct |
43 |
Correct |
3 ms |
460 KB |
Output is correct |
44 |
Correct |
3 ms |
588 KB |
Output is correct |
45 |
Incorrect |
228 ms |
15324 KB |
Solution announced impossible, but it is possible. |
46 |
Halted |
0 ms |
0 KB |
- |