#include "parks.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;
// #define X first
// #define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
namespace {
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2E5 + 5;
const int dx[] = {2, 0, -2, 0};
const int dy[] = {0, 2, 0, -2};
map<pii, int> fountain;
vector<int> p(maxn);
vector<int> adj[maxn];
int R(int x) {return x ^ p[x] ? p[x] = R(p[x]) : x;}
int U(int x, int y) {x = R(x), y = R(y); return x ^ y ? p[x] = y, 1 : 0;}
} /// end of namespace
int construct_roads(vector<int> X, vector<int> Y) {
int N = X.size();
vector<int> u, v, a, b;
if (N == 1) return build({}, {}, {}, {}), 1;
iota(ALL(p), 0);
for (int i = 0; i < N; ++i) fountain[{X[i], Y[i]}] = i+1;
for (int i = 0; i < N; ++i) {
for (int d = 0; d < 4; ++d) {
int nei = fountain[{X[i] + dx[d], Y[i] + dy[d]}];
if (nei-1 > i and U(i, nei-1)) u.eb(i), v.eb(nei-1);
}
}
for (int i = 0; i < N; ++i) if (R(i) != R(0)) return 0;
int M = u.size(); a.assign(M, -1), b.assign(M, -1);
// assert(M == N-1);
for (int i = 0; i < M; ++i) {
if (X[u[i]] == X[v[i]]) {
int midY = Y[u[i]] + Y[v[i]] >> 1;
if ((X[u[i]] + 1 + midY) % 4 == 2) a[i] = X[u[i]] + 1;
else a[i] = X[u[i]] - 1;
b[i] = midY;
}
}
for (int i = 0; i < M; ++i) {
if (Y[u[i]] == Y[v[i]]) {
int midX = X[u[i]] + X[v[i]] >> 1;
if ((Y[u[i]] + 1 + midX) % 4 == 0) b[i] = Y[u[i]] + 1;
else b[i] = Y[u[i]] - 1;
a[i] = midX;
}
}
return build(u, v, a, b), 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:61:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int midY = Y[u[i]] + Y[v[i]] >> 1;
parks.cpp:70:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | int midX = X[u[i]] + X[v[i]] >> 1;
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5708 KB |
Output is correct |
2 |
Correct |
4 ms |
5708 KB |
Output is correct |
3 |
Correct |
4 ms |
5708 KB |
Output is correct |
4 |
Correct |
4 ms |
5708 KB |
Output is correct |
5 |
Correct |
4 ms |
5788 KB |
Output is correct |
6 |
Correct |
4 ms |
5792 KB |
Output is correct |
7 |
Correct |
4 ms |
5708 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
323 ms |
31624 KB |
Output is correct |
10 |
Correct |
19 ms |
8652 KB |
Output is correct |
11 |
Correct |
101 ms |
20236 KB |
Output is correct |
12 |
Correct |
27 ms |
10016 KB |
Output is correct |
13 |
Correct |
65 ms |
15804 KB |
Output is correct |
14 |
Correct |
5 ms |
5964 KB |
Output is correct |
15 |
Correct |
6 ms |
6220 KB |
Output is correct |
16 |
Correct |
324 ms |
31540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5708 KB |
Output is correct |
2 |
Correct |
4 ms |
5708 KB |
Output is correct |
3 |
Correct |
4 ms |
5708 KB |
Output is correct |
4 |
Correct |
4 ms |
5708 KB |
Output is correct |
5 |
Correct |
4 ms |
5788 KB |
Output is correct |
6 |
Correct |
4 ms |
5792 KB |
Output is correct |
7 |
Correct |
4 ms |
5708 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
323 ms |
31624 KB |
Output is correct |
10 |
Correct |
19 ms |
8652 KB |
Output is correct |
11 |
Correct |
101 ms |
20236 KB |
Output is correct |
12 |
Correct |
27 ms |
10016 KB |
Output is correct |
13 |
Correct |
65 ms |
15804 KB |
Output is correct |
14 |
Correct |
5 ms |
5964 KB |
Output is correct |
15 |
Correct |
6 ms |
6220 KB |
Output is correct |
16 |
Correct |
324 ms |
31540 KB |
Output is correct |
17 |
Incorrect |
4 ms |
5708 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 |
4 ms |
5708 KB |
Output is correct |
2 |
Correct |
4 ms |
5708 KB |
Output is correct |
3 |
Correct |
4 ms |
5708 KB |
Output is correct |
4 |
Correct |
4 ms |
5708 KB |
Output is correct |
5 |
Correct |
4 ms |
5788 KB |
Output is correct |
6 |
Correct |
4 ms |
5792 KB |
Output is correct |
7 |
Correct |
4 ms |
5708 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
323 ms |
31624 KB |
Output is correct |
10 |
Correct |
19 ms |
8652 KB |
Output is correct |
11 |
Correct |
101 ms |
20236 KB |
Output is correct |
12 |
Correct |
27 ms |
10016 KB |
Output is correct |
13 |
Correct |
65 ms |
15804 KB |
Output is correct |
14 |
Correct |
5 ms |
5964 KB |
Output is correct |
15 |
Correct |
6 ms |
6220 KB |
Output is correct |
16 |
Correct |
324 ms |
31540 KB |
Output is correct |
17 |
Incorrect |
4 ms |
5708 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 |
4 ms |
5708 KB |
Output is correct |
2 |
Correct |
4 ms |
5708 KB |
Output is correct |
3 |
Correct |
4 ms |
5708 KB |
Output is correct |
4 |
Correct |
4 ms |
5708 KB |
Output is correct |
5 |
Correct |
4 ms |
5788 KB |
Output is correct |
6 |
Correct |
4 ms |
5792 KB |
Output is correct |
7 |
Correct |
4 ms |
5708 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
323 ms |
31624 KB |
Output is correct |
10 |
Correct |
19 ms |
8652 KB |
Output is correct |
11 |
Correct |
101 ms |
20236 KB |
Output is correct |
12 |
Correct |
27 ms |
10016 KB |
Output is correct |
13 |
Correct |
65 ms |
15804 KB |
Output is correct |
14 |
Correct |
5 ms |
5964 KB |
Output is correct |
15 |
Correct |
6 ms |
6220 KB |
Output is correct |
16 |
Correct |
324 ms |
31540 KB |
Output is correct |
17 |
Correct |
4 ms |
5708 KB |
Output is correct |
18 |
Correct |
4 ms |
5792 KB |
Output is correct |
19 |
Correct |
4 ms |
5792 KB |
Output is correct |
20 |
Correct |
731 ms |
45916 KB |
Output is correct |
21 |
Correct |
705 ms |
45616 KB |
Output is correct |
22 |
Correct |
722 ms |
45688 KB |
Output is correct |
23 |
Correct |
634 ms |
50200 KB |
Output is correct |
24 |
Correct |
828 ms |
48196 KB |
Output is correct |
25 |
Correct |
755 ms |
37260 KB |
Output is correct |
26 |
Correct |
849 ms |
37292 KB |
Output is correct |
27 |
Correct |
895 ms |
45056 KB |
Output is correct |
28 |
Correct |
924 ms |
44972 KB |
Output is correct |
29 |
Correct |
915 ms |
45032 KB |
Output is correct |
30 |
Correct |
826 ms |
44972 KB |
Output is correct |
31 |
Correct |
4 ms |
5708 KB |
Output is correct |
32 |
Correct |
32 ms |
8964 KB |
Output is correct |
33 |
Correct |
243 ms |
27412 KB |
Output is correct |
34 |
Correct |
660 ms |
45848 KB |
Output is correct |
35 |
Correct |
18 ms |
7244 KB |
Output is correct |
36 |
Correct |
113 ms |
12936 KB |
Output is correct |
37 |
Correct |
350 ms |
19972 KB |
Output is correct |
38 |
Correct |
218 ms |
20272 KB |
Output is correct |
39 |
Correct |
378 ms |
25616 KB |
Output is correct |
40 |
Correct |
496 ms |
31020 KB |
Output is correct |
41 |
Correct |
639 ms |
36524 KB |
Output is correct |
42 |
Correct |
845 ms |
41836 KB |
Output is correct |
43 |
Correct |
4 ms |
5792 KB |
Output is correct |
44 |
Correct |
4 ms |
5708 KB |
Output is correct |
45 |
Correct |
4 ms |
5708 KB |
Output is correct |
46 |
Correct |
4 ms |
5792 KB |
Output is correct |
47 |
Correct |
4 ms |
5708 KB |
Output is correct |
48 |
Correct |
4 ms |
5796 KB |
Output is correct |
49 |
Correct |
4 ms |
5708 KB |
Output is correct |
50 |
Correct |
4 ms |
5708 KB |
Output is correct |
51 |
Correct |
4 ms |
5708 KB |
Output is correct |
52 |
Correct |
4 ms |
5708 KB |
Output is correct |
53 |
Correct |
4 ms |
5708 KB |
Output is correct |
54 |
Correct |
6 ms |
6092 KB |
Output is correct |
55 |
Correct |
7 ms |
6220 KB |
Output is correct |
56 |
Correct |
345 ms |
27808 KB |
Output is correct |
57 |
Correct |
559 ms |
37648 KB |
Output is correct |
58 |
Correct |
559 ms |
37644 KB |
Output is correct |
59 |
Correct |
4 ms |
5708 KB |
Output is correct |
60 |
Correct |
4 ms |
5708 KB |
Output is correct |
61 |
Correct |
4 ms |
5708 KB |
Output is correct |
62 |
Correct |
857 ms |
51348 KB |
Output is correct |
63 |
Correct |
858 ms |
51296 KB |
Output is correct |
64 |
Correct |
818 ms |
50988 KB |
Output is correct |
65 |
Correct |
8 ms |
6348 KB |
Output is correct |
66 |
Correct |
15 ms |
7116 KB |
Output is correct |
67 |
Correct |
331 ms |
26288 KB |
Output is correct |
68 |
Correct |
582 ms |
36624 KB |
Output is correct |
69 |
Correct |
944 ms |
47036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5708 KB |
Output is correct |
2 |
Correct |
4 ms |
5708 KB |
Output is correct |
3 |
Correct |
4 ms |
5708 KB |
Output is correct |
4 |
Correct |
4 ms |
5708 KB |
Output is correct |
5 |
Correct |
4 ms |
5788 KB |
Output is correct |
6 |
Correct |
4 ms |
5792 KB |
Output is correct |
7 |
Correct |
4 ms |
5708 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
323 ms |
31624 KB |
Output is correct |
10 |
Correct |
19 ms |
8652 KB |
Output is correct |
11 |
Correct |
101 ms |
20236 KB |
Output is correct |
12 |
Correct |
27 ms |
10016 KB |
Output is correct |
13 |
Correct |
65 ms |
15804 KB |
Output is correct |
14 |
Correct |
5 ms |
5964 KB |
Output is correct |
15 |
Correct |
6 ms |
6220 KB |
Output is correct |
16 |
Correct |
324 ms |
31540 KB |
Output is correct |
17 |
Correct |
778 ms |
57924 KB |
Output is correct |
18 |
Correct |
771 ms |
58008 KB |
Output is correct |
19 |
Correct |
792 ms |
45572 KB |
Output is correct |
20 |
Correct |
725 ms |
36084 KB |
Output is correct |
21 |
Correct |
718 ms |
43808 KB |
Output is correct |
22 |
Correct |
4 ms |
5708 KB |
Output is correct |
23 |
Correct |
70 ms |
12184 KB |
Output is correct |
24 |
Correct |
34 ms |
8360 KB |
Output is correct |
25 |
Correct |
185 ms |
15036 KB |
Output is correct |
26 |
Correct |
383 ms |
21556 KB |
Output is correct |
27 |
Correct |
299 ms |
22552 KB |
Output is correct |
28 |
Correct |
437 ms |
27068 KB |
Output is correct |
29 |
Correct |
556 ms |
31252 KB |
Output is correct |
30 |
Correct |
729 ms |
34988 KB |
Output is correct |
31 |
Correct |
772 ms |
39428 KB |
Output is correct |
32 |
Correct |
839 ms |
44972 KB |
Output is correct |
33 |
Correct |
830 ms |
51216 KB |
Output is correct |
34 |
Correct |
10 ms |
6604 KB |
Output is correct |
35 |
Correct |
17 ms |
7144 KB |
Output is correct |
36 |
Correct |
338 ms |
25608 KB |
Output is correct |
37 |
Correct |
594 ms |
35732 KB |
Output is correct |
38 |
Correct |
929 ms |
45712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5708 KB |
Output is correct |
2 |
Correct |
4 ms |
5708 KB |
Output is correct |
3 |
Correct |
4 ms |
5708 KB |
Output is correct |
4 |
Correct |
4 ms |
5708 KB |
Output is correct |
5 |
Correct |
4 ms |
5788 KB |
Output is correct |
6 |
Correct |
4 ms |
5792 KB |
Output is correct |
7 |
Correct |
4 ms |
5708 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
323 ms |
31624 KB |
Output is correct |
10 |
Correct |
19 ms |
8652 KB |
Output is correct |
11 |
Correct |
101 ms |
20236 KB |
Output is correct |
12 |
Correct |
27 ms |
10016 KB |
Output is correct |
13 |
Correct |
65 ms |
15804 KB |
Output is correct |
14 |
Correct |
5 ms |
5964 KB |
Output is correct |
15 |
Correct |
6 ms |
6220 KB |
Output is correct |
16 |
Correct |
324 ms |
31540 KB |
Output is correct |
17 |
Incorrect |
4 ms |
5708 KB |
Tree @(3, 3) appears more than once: for edges on positions 1 and 2 |
18 |
Halted |
0 ms |
0 KB |
- |