#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, bench;
// map<pii, vector<int>> candidate;
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;
// candidate[{X[u[i]] + 1, midY}].eb(i);
// candidate[{X[u[i]] - 1, midY}].eb(i);
// }
// else if (Y[u[i]] == Y[v[i]]) {
// int midX = X[u[i]] + X[v[i]] >> 1;
// candidate[{midX, Y[u[i]] + 1}].eb(i);
// candidate[{midX, Y[u[i]] - 1}].eb(i);
// }
// }
// for (auto [coord, vec] : candidate) {
// if (vec.size() >= 2) {
// for (auto x : vec) for (auto y : vec) {
// if (x < y) adj[x].eb(y);
// }
// }
// }
for (int i = 0; i < M; ++i) {
if (X[u[i]] == X[v[i]]) {
int midY = Y[u[i]] + Y[v[i]] >> 1;
if (min(Y[u[i]], Y[v[i]]) % 4 == 0) a[i] = X[u[i]] + 1;
else if (min(Y[u[i]], Y[v[i]]) % 4 == 2) a[i] = X[u[i]] - 1;
b[i] = midY;
bench[{a[i], b[i]}] = 1;
}
}
for (int i = 0; i < M; ++i) {
if (Y[u[i]] == Y[v[i]]) {
int midX = X[u[i]] + X[v[i]] >> 1;
a[i] = midX;
if (!bench[{midX, Y[i] + 1}]) b[i] = Y[i] + 1;
else if (!bench[{midX, Y[i] - 1}]) b[i] = Y[i] - 1;
}
}
return build(u, v, a, b), 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:83:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int midY = Y[u[i]] + Y[v[i]] >> 1;
parks.cpp:93:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
93 | int midX = X[u[i]] + X[v[i]] >> 1;
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5676 KB |
Output is correct |
2 |
Correct |
3 ms |
5708 KB |
Output is correct |
3 |
Correct |
3 ms |
5708 KB |
Output is correct |
4 |
Correct |
3 ms |
5708 KB |
Output is correct |
5 |
Correct |
3 ms |
5708 KB |
Output is correct |
6 |
Correct |
3 ms |
5708 KB |
Output is correct |
7 |
Correct |
3 ms |
5708 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
370 ms |
37144 KB |
Output is correct |
10 |
Correct |
24 ms |
9292 KB |
Output is correct |
11 |
Correct |
129 ms |
23180 KB |
Output is correct |
12 |
Correct |
34 ms |
10840 KB |
Output is correct |
13 |
Correct |
66 ms |
15420 KB |
Output is correct |
14 |
Correct |
4 ms |
5964 KB |
Output is correct |
15 |
Correct |
6 ms |
6092 KB |
Output is correct |
16 |
Correct |
351 ms |
37112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5676 KB |
Output is correct |
2 |
Correct |
3 ms |
5708 KB |
Output is correct |
3 |
Correct |
3 ms |
5708 KB |
Output is correct |
4 |
Correct |
3 ms |
5708 KB |
Output is correct |
5 |
Correct |
3 ms |
5708 KB |
Output is correct |
6 |
Correct |
3 ms |
5708 KB |
Output is correct |
7 |
Correct |
3 ms |
5708 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
370 ms |
37144 KB |
Output is correct |
10 |
Correct |
24 ms |
9292 KB |
Output is correct |
11 |
Correct |
129 ms |
23180 KB |
Output is correct |
12 |
Correct |
34 ms |
10840 KB |
Output is correct |
13 |
Correct |
66 ms |
15420 KB |
Output is correct |
14 |
Correct |
4 ms |
5964 KB |
Output is correct |
15 |
Correct |
6 ms |
6092 KB |
Output is correct |
16 |
Correct |
351 ms |
37112 KB |
Output is correct |
17 |
Correct |
4 ms |
5708 KB |
Output is correct |
18 |
Incorrect |
4 ms |
5708 KB |
Tree (a[1], b[1]) = (3, 7) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=2 @(2, 4) |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5676 KB |
Output is correct |
2 |
Correct |
3 ms |
5708 KB |
Output is correct |
3 |
Correct |
3 ms |
5708 KB |
Output is correct |
4 |
Correct |
3 ms |
5708 KB |
Output is correct |
5 |
Correct |
3 ms |
5708 KB |
Output is correct |
6 |
Correct |
3 ms |
5708 KB |
Output is correct |
7 |
Correct |
3 ms |
5708 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
370 ms |
37144 KB |
Output is correct |
10 |
Correct |
24 ms |
9292 KB |
Output is correct |
11 |
Correct |
129 ms |
23180 KB |
Output is correct |
12 |
Correct |
34 ms |
10840 KB |
Output is correct |
13 |
Correct |
66 ms |
15420 KB |
Output is correct |
14 |
Correct |
4 ms |
5964 KB |
Output is correct |
15 |
Correct |
6 ms |
6092 KB |
Output is correct |
16 |
Correct |
351 ms |
37112 KB |
Output is correct |
17 |
Correct |
4 ms |
5708 KB |
Output is correct |
18 |
Incorrect |
4 ms |
5708 KB |
Tree (a[1], b[1]) = (3, 7) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=2 @(2, 4) |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5676 KB |
Output is correct |
2 |
Correct |
3 ms |
5708 KB |
Output is correct |
3 |
Correct |
3 ms |
5708 KB |
Output is correct |
4 |
Correct |
3 ms |
5708 KB |
Output is correct |
5 |
Correct |
3 ms |
5708 KB |
Output is correct |
6 |
Correct |
3 ms |
5708 KB |
Output is correct |
7 |
Correct |
3 ms |
5708 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
370 ms |
37144 KB |
Output is correct |
10 |
Correct |
24 ms |
9292 KB |
Output is correct |
11 |
Correct |
129 ms |
23180 KB |
Output is correct |
12 |
Correct |
34 ms |
10840 KB |
Output is correct |
13 |
Correct |
66 ms |
15420 KB |
Output is correct |
14 |
Correct |
4 ms |
5964 KB |
Output is correct |
15 |
Correct |
6 ms |
6092 KB |
Output is correct |
16 |
Correct |
351 ms |
37112 KB |
Output is correct |
17 |
Incorrect |
4 ms |
5708 KB |
Tree (a[1], b[1]) = (199999, 5) is not adjacent to edge between u[1]=0 @(200000, 2) and v[1]=2 @(199998, 2) |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5676 KB |
Output is correct |
2 |
Correct |
3 ms |
5708 KB |
Output is correct |
3 |
Correct |
3 ms |
5708 KB |
Output is correct |
4 |
Correct |
3 ms |
5708 KB |
Output is correct |
5 |
Correct |
3 ms |
5708 KB |
Output is correct |
6 |
Correct |
3 ms |
5708 KB |
Output is correct |
7 |
Correct |
3 ms |
5708 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
370 ms |
37144 KB |
Output is correct |
10 |
Correct |
24 ms |
9292 KB |
Output is correct |
11 |
Correct |
129 ms |
23180 KB |
Output is correct |
12 |
Correct |
34 ms |
10840 KB |
Output is correct |
13 |
Correct |
66 ms |
15420 KB |
Output is correct |
14 |
Correct |
4 ms |
5964 KB |
Output is correct |
15 |
Correct |
6 ms |
6092 KB |
Output is correct |
16 |
Correct |
351 ms |
37112 KB |
Output is correct |
17 |
Incorrect |
876 ms |
67944 KB |
Tree (a[1], b[1]) = (82421, 52499) is not adjacent to edge between u[1]=0 @(82422, 100002) and v[1]=148989 @(82420, 100002) |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5676 KB |
Output is correct |
2 |
Correct |
3 ms |
5708 KB |
Output is correct |
3 |
Correct |
3 ms |
5708 KB |
Output is correct |
4 |
Correct |
3 ms |
5708 KB |
Output is correct |
5 |
Correct |
3 ms |
5708 KB |
Output is correct |
6 |
Correct |
3 ms |
5708 KB |
Output is correct |
7 |
Correct |
3 ms |
5708 KB |
Output is correct |
8 |
Correct |
4 ms |
5708 KB |
Output is correct |
9 |
Correct |
370 ms |
37144 KB |
Output is correct |
10 |
Correct |
24 ms |
9292 KB |
Output is correct |
11 |
Correct |
129 ms |
23180 KB |
Output is correct |
12 |
Correct |
34 ms |
10840 KB |
Output is correct |
13 |
Correct |
66 ms |
15420 KB |
Output is correct |
14 |
Correct |
4 ms |
5964 KB |
Output is correct |
15 |
Correct |
6 ms |
6092 KB |
Output is correct |
16 |
Correct |
351 ms |
37112 KB |
Output is correct |
17 |
Correct |
4 ms |
5708 KB |
Output is correct |
18 |
Incorrect |
4 ms |
5708 KB |
Tree (a[1], b[1]) = (3, 7) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=2 @(2, 4) |
19 |
Halted |
0 ms |
0 KB |
- |