#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 3e2;
#define all(x) (x).begin(), (x).end()
int p[N];
int find(int x){
return (x == p[x] ? x : p[x] = find(p[x]));
}
bool unite(int x, int y){
x = find(x);
y = find(y);
if (x == y) return false;
if (rand() & 1) swap(x, y);
p[x] = y;
return true;
}
bool can(vector<int> &x, vector<int> &y, vector<int> &U, vector<int> &V, vector<int> &A, vector<int> &B, const vector<int> &dx, const vector<int> &dy){
int n = x.size();
bool ok = true;
set<pair<int, int>> points;
for (int it = 0; it < n - 1; it++){
A[it] = B[it] = 0;
int i = U[it], j = V[it];
int X = (x[i] + x[j]) / 2, Y = (y[i] + y[j]) / 2;
if (x[i] == x[j]){
for (int d : dx){
if (!points.count({x[i] + d, Y})){
A[it] = x[i] + d;
break;
}
}
B[it] = Y;
} else {
for (int d : dy){
if (!points.count({X, y[i] + d})){
B[it] = y[i] + d;
break;
}
}
A[it] = X;
}
if (A[it] == 0 || B[it] == 0) ok = false;
points.insert({A[it], B[it]});
}
return ok;
}
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
if (n == 1) {
build({}, {}, {}, {});
return 1;
}
vector<int> perm(n);
iota(all(perm), 0);
sort(all(perm), [&](int i, int j){
return x[i] < x[j] || x[i] == x[j] && y[i] < y[j];
});
iota(p, p + n, 0);
map<pair<int, int>, int> id;
for (int i = 0; i < n; i++){
id[{x[i], y[i]}] = i;
}
vector<int> U, V, A(n - 1), B(n - 1);
vector<int> dx = {0, 2};
vector<int> dy = {2, 0};
for (int it = 0; it < dx.size(); it++){
for (int i : perm){
int X = x[i] + dx[it], Y = y[i] + dy[it];
if (id.find({X, Y}) != id.end()){
int j = id[{X, Y}];
if (!unite(i, j)) continue;
U.push_back(i);
V.push_back(j);
}
}
}
if (U.size() != n - 1) return 0;
if (can(x, y, U, V, A, B, {1, -1}, {1, -1})){
build(U, V, A, B);
return 1;
}
if (can(x, y, U, V, A, B, {1, -1}, {-1, 1})){
build(U, V, A, B);
return 1;
}
if (can(x, y, U, V, A, B, {-1, 1}, {1, -1})){
build(U, V, A, B);
return 1;
}
if (can(x, y, U, V, A, B, {-1, 1}, {-1, 1})){
build(U, V, A, B);
return 1;
}
return 0;
}
Compilation message
parks.cpp: In lambda function:
parks.cpp:73:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
73 | return x[i] < x[j] || x[i] == x[j] && y[i] < y[j];
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:88:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int it = 0; it < dx.size(); it++){
| ~~~^~~~~~~~~~~
parks.cpp:100:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
100 | if (U.size() != n - 1) return 0;
| ~~~~~~~~~^~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
300 KB |
Output is correct |
9 |
Correct |
150 ms |
15516 KB |
Output is correct |
10 |
Correct |
12 ms |
1996 KB |
Output is correct |
11 |
Correct |
71 ms |
8596 KB |
Output is correct |
12 |
Correct |
19 ms |
2904 KB |
Output is correct |
13 |
Correct |
35 ms |
5384 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
464 KB |
Output is correct |
16 |
Correct |
161 ms |
15652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
300 KB |
Output is correct |
9 |
Correct |
150 ms |
15516 KB |
Output is correct |
10 |
Correct |
12 ms |
1996 KB |
Output is correct |
11 |
Correct |
71 ms |
8596 KB |
Output is correct |
12 |
Correct |
19 ms |
2904 KB |
Output is correct |
13 |
Correct |
35 ms |
5384 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
464 KB |
Output is correct |
16 |
Correct |
161 ms |
15652 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
300 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
390 ms |
31380 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
2 ms |
460 KB |
Output is correct |
26 |
Correct |
3 ms |
588 KB |
Output is correct |
27 |
Correct |
4 ms |
736 KB |
Output is correct |
28 |
Correct |
123 ms |
12740 KB |
Output is correct |
29 |
Correct |
267 ms |
19128 KB |
Output is correct |
30 |
Correct |
304 ms |
25316 KB |
Output is correct |
31 |
Correct |
402 ms |
31452 KB |
Output is correct |
32 |
Correct |
1 ms |
204 KB |
Output is correct |
33 |
Correct |
1 ms |
320 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 |
0 ms |
204 KB |
Output is correct |
38 |
Correct |
0 ms |
204 KB |
Output is correct |
39 |
Correct |
0 ms |
204 KB |
Output is correct |
40 |
Correct |
0 ms |
204 KB |
Output is correct |
41 |
Correct |
1 ms |
204 KB |
Output is correct |
42 |
Correct |
1 ms |
296 KB |
Output is correct |
43 |
Correct |
2 ms |
460 KB |
Output is correct |
44 |
Correct |
3 ms |
588 KB |
Output is correct |
45 |
Incorrect |
185 ms |
15048 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 |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
300 KB |
Output is correct |
9 |
Correct |
150 ms |
15516 KB |
Output is correct |
10 |
Correct |
12 ms |
1996 KB |
Output is correct |
11 |
Correct |
71 ms |
8596 KB |
Output is correct |
12 |
Correct |
19 ms |
2904 KB |
Output is correct |
13 |
Correct |
35 ms |
5384 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
464 KB |
Output is correct |
16 |
Correct |
161 ms |
15652 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
300 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
390 ms |
31380 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
2 ms |
460 KB |
Output is correct |
26 |
Correct |
3 ms |
588 KB |
Output is correct |
27 |
Correct |
4 ms |
736 KB |
Output is correct |
28 |
Correct |
123 ms |
12740 KB |
Output is correct |
29 |
Correct |
267 ms |
19128 KB |
Output is correct |
30 |
Correct |
304 ms |
25316 KB |
Output is correct |
31 |
Correct |
402 ms |
31452 KB |
Output is correct |
32 |
Correct |
1 ms |
204 KB |
Output is correct |
33 |
Correct |
1 ms |
320 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 |
0 ms |
204 KB |
Output is correct |
38 |
Correct |
0 ms |
204 KB |
Output is correct |
39 |
Correct |
0 ms |
204 KB |
Output is correct |
40 |
Correct |
0 ms |
204 KB |
Output is correct |
41 |
Correct |
1 ms |
204 KB |
Output is correct |
42 |
Correct |
1 ms |
296 KB |
Output is correct |
43 |
Correct |
2 ms |
460 KB |
Output is correct |
44 |
Correct |
3 ms |
588 KB |
Output is correct |
45 |
Incorrect |
185 ms |
15048 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 |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
300 KB |
Output is correct |
9 |
Correct |
150 ms |
15516 KB |
Output is correct |
10 |
Correct |
12 ms |
1996 KB |
Output is correct |
11 |
Correct |
71 ms |
8596 KB |
Output is correct |
12 |
Correct |
19 ms |
2904 KB |
Output is correct |
13 |
Correct |
35 ms |
5384 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
464 KB |
Output is correct |
16 |
Correct |
161 ms |
15652 KB |
Output is correct |
17 |
Correct |
1 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 |
403 ms |
30640 KB |
Output is correct |
21 |
Correct |
426 ms |
30568 KB |
Output is correct |
22 |
Correct |
393 ms |
30780 KB |
Output is correct |
23 |
Correct |
324 ms |
26340 KB |
Output is correct |
24 |
Correct |
239 ms |
19680 KB |
Output is correct |
25 |
Correct |
292 ms |
21424 KB |
Output is correct |
26 |
Correct |
249 ms |
21572 KB |
Output is correct |
27 |
Correct |
376 ms |
30512 KB |
Output is correct |
28 |
Correct |
408 ms |
30512 KB |
Output is correct |
29 |
Correct |
552 ms |
30532 KB |
Output is correct |
30 |
Correct |
415 ms |
30544 KB |
Output is correct |
31 |
Correct |
1 ms |
204 KB |
Output is correct |
32 |
Incorrect |
25 ms |
2508 KB |
Solution announced impossible, but it is possible. |
33 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
300 KB |
Output is correct |
9 |
Correct |
150 ms |
15516 KB |
Output is correct |
10 |
Correct |
12 ms |
1996 KB |
Output is correct |
11 |
Correct |
71 ms |
8596 KB |
Output is correct |
12 |
Correct |
19 ms |
2904 KB |
Output is correct |
13 |
Correct |
35 ms |
5384 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
464 KB |
Output is correct |
16 |
Correct |
161 ms |
15652 KB |
Output is correct |
17 |
Correct |
419 ms |
31076 KB |
Output is correct |
18 |
Correct |
521 ms |
30920 KB |
Output is correct |
19 |
Incorrect |
518 ms |
30640 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 |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
300 KB |
Output is correct |
9 |
Correct |
150 ms |
15516 KB |
Output is correct |
10 |
Correct |
12 ms |
1996 KB |
Output is correct |
11 |
Correct |
71 ms |
8596 KB |
Output is correct |
12 |
Correct |
19 ms |
2904 KB |
Output is correct |
13 |
Correct |
35 ms |
5384 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
464 KB |
Output is correct |
16 |
Correct |
161 ms |
15652 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
300 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
390 ms |
31380 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
2 ms |
460 KB |
Output is correct |
26 |
Correct |
3 ms |
588 KB |
Output is correct |
27 |
Correct |
4 ms |
736 KB |
Output is correct |
28 |
Correct |
123 ms |
12740 KB |
Output is correct |
29 |
Correct |
267 ms |
19128 KB |
Output is correct |
30 |
Correct |
304 ms |
25316 KB |
Output is correct |
31 |
Correct |
402 ms |
31452 KB |
Output is correct |
32 |
Correct |
1 ms |
204 KB |
Output is correct |
33 |
Correct |
1 ms |
320 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 |
0 ms |
204 KB |
Output is correct |
38 |
Correct |
0 ms |
204 KB |
Output is correct |
39 |
Correct |
0 ms |
204 KB |
Output is correct |
40 |
Correct |
0 ms |
204 KB |
Output is correct |
41 |
Correct |
1 ms |
204 KB |
Output is correct |
42 |
Correct |
1 ms |
296 KB |
Output is correct |
43 |
Correct |
2 ms |
460 KB |
Output is correct |
44 |
Correct |
3 ms |
588 KB |
Output is correct |
45 |
Incorrect |
185 ms |
15048 KB |
Solution announced impossible, but it is possible. |
46 |
Halted |
0 ms |
0 KB |
- |