#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,sse4.2")
#endif
#include <bits/stdc++.h>
#include "parks.h"
std::unordered_map<int, int> map[100001];
int N;
std::unordered_map<int, std::vector<int>> rely[100002];
std::vector<std::pair<int, int>> vld[200000];
std::pair<int, int> assigned[200000];
std::unordered_set<int> taken[100002];
time_t stop;
std::default_random_engine Rand(std::random_device{}());
bool shuffle = true;
bool Shuffle = false;
bool doomed(int x) {
for (auto a: vld[x]) if (!taken[a.first / 2].count(a.second)) return false;
return true;
}
bool cantake(std::pair<int, int> a, int n) {
for (auto x: rely[a.first / 2][a.second]) if (x > n && doomed(x)) return false;
return true;
}
#ifdef LOCAL
size_t called = 0;
#endif
bool backtrack(int n) {
#ifdef LOCAL
called++;
#endif
if (n == N - 1) return true;
if (clock() > stop) return false;
// if (Shuffle && vld[n].size() == 2 && Rand() % 2) {
// std::swap(vld[n][0], vld[n][1]);
// }
for (auto a: vld[n]) {
if (taken[a.first / 2].count(a.second)) continue;
taken[a.first / 2].insert(a.second);
if (!cantake(a, n)) {
taken[a.first / 2].erase(a.second);
continue;
}
if (backtrack(n + 1)) {
assigned[n] = a;
return true;
}
taken[a.first / 2].erase(a.second);
}
return false;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
stop = clock() + 3.4 * CLOCKS_PER_SEC;
N = (int) x.size();
if (N == 1) {
build({}, {}, {}, {});
return 1;
}
int maxx = x[0];
int minx = x[0];
int maxy = y[0];
int miny = y[0];
for (int i = 0; i < N; ++i) {
maxx = std::max(maxx, x[i]);
minx = std::min(minx, x[i]);
maxy = std::max(maxy, y[i]);
miny = std::min(miny, y[i]);
}
for (int i = 0; i < N; ++i) {
map[x[i] / 2][y[i]] = i;
}
while (true) {
std::vector<int> u, v, a, b;
bool seen[N];
for (int i = 0; i < N; ++i) {
seen[i] = false;
}
std::queue<int> bfs;
int start = 0;
if (shuffle) {
for (int i = 0; i < N; ++i) {
if (x[i] < x[start]) start = i;
if (x[i] == x[start] && y[i] < y[start]) start = i;
}
}
if (Shuffle) {
start = Rand() % N;
}
bfs.push(start);
seen[start] = true;
auto add = [&](int x, int y, std::vector<int> &data) {
if (x < 0 || x > 200000) return;
if (map[x / 2].count(y)) data.push_back(map[x / 2][y]);
};
auto edges = [&](int x, int y) {
std::vector<int> result;
add(x, y + 2, result);
add(x, y - 2, result);
add(x + 2, y, result);
add(x - 2, y, result);
if (Shuffle) {
std::shuffle(result.begin(), result.end(), Rand);
}
return result;
};
int rem = N - 1;
while (!bfs.empty()) {
auto next = bfs.front();
bfs.pop();
for (auto n: edges(x[next], y[next])) {
if (!seen[n]) {
seen[n] = true;
bfs.push(n);
rem--;
u.push_back(next);
v.push_back(n);
}
}
}
if (rem)
return 0;
std::function<std::vector<std::pair<int, int>>(int, int)> valid = [&x, &y, minx, maxx, miny, maxy](int u,
int v) -> std::vector<std::pair<int, int>> {
if (x[u] == x[v]) {
int _y = (y[u] + y[v]) / 2;
if (x[u] == minx) return {{minx - 1, _y}};
if (x[u] == maxx) return {{maxx + 1, _y}};
return {{x[u] + 1, _y},
{x[u] - 1, _y}};
} else {
int _x = (x[u] + x[v]) / 2;
if (y[u] == miny) return {{_x, miny - 1}};
if (y[u] == maxy) return {{_x, maxy + 1}};
return {{_x, y[u] + 1},
{_x, y[u] - 1}};
}
};
if (shuffle) {
std::vector<std::pair<int, int>> Edges;
for (int i = 0; i < N - 1; ++i) {
Edges.emplace_back(u[i], v[i]);
}
std::sort(Edges.begin(), Edges.end(), [&](std::pair<int, int> a, std::pair<int, int> b) {
int A = a.first;
int B = b.first;
if (x[A] == x[B]) return y[A] < y[B];
return x[A] < x[B];
});
for (int i = 0; i < N - 1; ++i) {
u[i] = Edges[i].first;
v[i] = Edges[i].second;
}
}
for (int i = 0; i < N - 1; ++i) {
vld[i] = valid(u[i], v[i]);
if (Shuffle && vld[i].size() == 2 && Rand() % 2) {
std::swap(vld[i][0], vld[i][1]);
}
}
for (int i = 0; i < N - 1; ++i) {
for (auto n: vld[i]) {
rely[n.first / 2][n.second].push_back(i);
}
}
if (shuffle && !Shuffle)
stop = clock() + CLOCKS_PER_SEC;
if (backtrack(0)) {
#ifdef LOCAL
printf("Called backtrack %ld times.\n", called);
called = 0;
#endif
for (int i = 0; i < N - 1; ++i) {
a.push_back(assigned[i].first);
b.push_back(assigned[i].second);
}
build(u, v, a, b);
return 1;
}
#ifdef LOCAL
printf("Called backtrack %ld times.\n", called);
called = 0;
#endif
for (auto _x: x) {
rely[(_x - 1) / 2].clear();
rely[(_x + 1) / 2].clear();
}
if (shuffle && !Shuffle) {
shuffle = false;
} else if (!(shuffle || Shuffle)) {
Shuffle = true;
} else {
shuffle = true;
}
#ifdef LOCAL
printf("Retrying...\n");
#endif
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
23132 KB |
Output is correct |
2 |
Correct |
6 ms |
23132 KB |
Output is correct |
3 |
Correct |
6 ms |
23132 KB |
Output is correct |
4 |
Correct |
6 ms |
23132 KB |
Output is correct |
5 |
Correct |
7 ms |
23132 KB |
Output is correct |
6 |
Correct |
7 ms |
23132 KB |
Output is correct |
7 |
Correct |
7 ms |
23132 KB |
Output is correct |
8 |
Correct |
7 ms |
23136 KB |
Output is correct |
9 |
Correct |
142 ms |
66568 KB |
Output is correct |
10 |
Correct |
19 ms |
27204 KB |
Output is correct |
11 |
Correct |
74 ms |
46184 KB |
Output is correct |
12 |
Correct |
25 ms |
29472 KB |
Output is correct |
13 |
Correct |
19 ms |
26148 KB |
Output is correct |
14 |
Correct |
7 ms |
23132 KB |
Output is correct |
15 |
Correct |
7 ms |
23132 KB |
Output is correct |
16 |
Correct |
146 ms |
66704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
23132 KB |
Output is correct |
2 |
Correct |
6 ms |
23132 KB |
Output is correct |
3 |
Correct |
6 ms |
23132 KB |
Output is correct |
4 |
Correct |
6 ms |
23132 KB |
Output is correct |
5 |
Correct |
7 ms |
23132 KB |
Output is correct |
6 |
Correct |
7 ms |
23132 KB |
Output is correct |
7 |
Correct |
7 ms |
23132 KB |
Output is correct |
8 |
Correct |
7 ms |
23136 KB |
Output is correct |
9 |
Correct |
142 ms |
66568 KB |
Output is correct |
10 |
Correct |
19 ms |
27204 KB |
Output is correct |
11 |
Correct |
74 ms |
46184 KB |
Output is correct |
12 |
Correct |
25 ms |
29472 KB |
Output is correct |
13 |
Correct |
19 ms |
26148 KB |
Output is correct |
14 |
Correct |
7 ms |
23132 KB |
Output is correct |
15 |
Correct |
7 ms |
23132 KB |
Output is correct |
16 |
Correct |
146 ms |
66704 KB |
Output is correct |
17 |
Correct |
6 ms |
23132 KB |
Output is correct |
18 |
Correct |
6 ms |
23132 KB |
Output is correct |
19 |
Correct |
6 ms |
23128 KB |
Output is correct |
20 |
Correct |
7 ms |
23132 KB |
Output is correct |
21 |
Correct |
7 ms |
23132 KB |
Output is correct |
22 |
Correct |
7 ms |
23132 KB |
Output is correct |
23 |
Correct |
320 ms |
108836 KB |
Output is correct |
24 |
Correct |
6 ms |
23132 KB |
Output is correct |
25 |
Correct |
8 ms |
23644 KB |
Output is correct |
26 |
Correct |
8 ms |
23132 KB |
Output is correct |
27 |
Correct |
8 ms |
23132 KB |
Output is correct |
28 |
Correct |
119 ms |
55728 KB |
Output is correct |
29 |
Correct |
180 ms |
73868 KB |
Output is correct |
30 |
Correct |
240 ms |
88240 KB |
Output is correct |
31 |
Correct |
305 ms |
108500 KB |
Output is correct |
32 |
Correct |
8 ms |
23128 KB |
Output is correct |
33 |
Correct |
7 ms |
23132 KB |
Output is correct |
34 |
Correct |
7 ms |
23132 KB |
Output is correct |
35 |
Correct |
7 ms |
22956 KB |
Output is correct |
36 |
Correct |
7 ms |
23132 KB |
Output is correct |
37 |
Correct |
6 ms |
23132 KB |
Output is correct |
38 |
Correct |
7 ms |
23128 KB |
Output is correct |
39 |
Correct |
6 ms |
23132 KB |
Output is correct |
40 |
Correct |
6 ms |
23132 KB |
Output is correct |
41 |
Correct |
7 ms |
23132 KB |
Output is correct |
42 |
Correct |
8 ms |
23132 KB |
Output is correct |
43 |
Correct |
7 ms |
23132 KB |
Output is correct |
44 |
Correct |
7 ms |
23132 KB |
Output is correct |
45 |
Correct |
169 ms |
68284 KB |
Output is correct |
46 |
Correct |
263 ms |
88852 KB |
Output is correct |
47 |
Correct |
266 ms |
88768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
23132 KB |
Output is correct |
2 |
Correct |
6 ms |
23132 KB |
Output is correct |
3 |
Correct |
6 ms |
23132 KB |
Output is correct |
4 |
Correct |
6 ms |
23132 KB |
Output is correct |
5 |
Correct |
7 ms |
23132 KB |
Output is correct |
6 |
Correct |
7 ms |
23132 KB |
Output is correct |
7 |
Correct |
7 ms |
23132 KB |
Output is correct |
8 |
Correct |
7 ms |
23136 KB |
Output is correct |
9 |
Correct |
142 ms |
66568 KB |
Output is correct |
10 |
Correct |
19 ms |
27204 KB |
Output is correct |
11 |
Correct |
74 ms |
46184 KB |
Output is correct |
12 |
Correct |
25 ms |
29472 KB |
Output is correct |
13 |
Correct |
19 ms |
26148 KB |
Output is correct |
14 |
Correct |
7 ms |
23132 KB |
Output is correct |
15 |
Correct |
7 ms |
23132 KB |
Output is correct |
16 |
Correct |
146 ms |
66704 KB |
Output is correct |
17 |
Correct |
6 ms |
23132 KB |
Output is correct |
18 |
Correct |
6 ms |
23132 KB |
Output is correct |
19 |
Correct |
6 ms |
23128 KB |
Output is correct |
20 |
Correct |
7 ms |
23132 KB |
Output is correct |
21 |
Correct |
7 ms |
23132 KB |
Output is correct |
22 |
Correct |
7 ms |
23132 KB |
Output is correct |
23 |
Correct |
320 ms |
108836 KB |
Output is correct |
24 |
Correct |
6 ms |
23132 KB |
Output is correct |
25 |
Correct |
8 ms |
23644 KB |
Output is correct |
26 |
Correct |
8 ms |
23132 KB |
Output is correct |
27 |
Correct |
8 ms |
23132 KB |
Output is correct |
28 |
Correct |
119 ms |
55728 KB |
Output is correct |
29 |
Correct |
180 ms |
73868 KB |
Output is correct |
30 |
Correct |
240 ms |
88240 KB |
Output is correct |
31 |
Correct |
305 ms |
108500 KB |
Output is correct |
32 |
Correct |
8 ms |
23128 KB |
Output is correct |
33 |
Correct |
7 ms |
23132 KB |
Output is correct |
34 |
Correct |
7 ms |
23132 KB |
Output is correct |
35 |
Correct |
7 ms |
22956 KB |
Output is correct |
36 |
Correct |
7 ms |
23132 KB |
Output is correct |
37 |
Correct |
6 ms |
23132 KB |
Output is correct |
38 |
Correct |
7 ms |
23128 KB |
Output is correct |
39 |
Correct |
6 ms |
23132 KB |
Output is correct |
40 |
Correct |
6 ms |
23132 KB |
Output is correct |
41 |
Correct |
7 ms |
23132 KB |
Output is correct |
42 |
Correct |
8 ms |
23132 KB |
Output is correct |
43 |
Correct |
7 ms |
23132 KB |
Output is correct |
44 |
Correct |
7 ms |
23132 KB |
Output is correct |
45 |
Correct |
169 ms |
68284 KB |
Output is correct |
46 |
Correct |
263 ms |
88852 KB |
Output is correct |
47 |
Correct |
266 ms |
88768 KB |
Output is correct |
48 |
Correct |
8 ms |
23132 KB |
Output is correct |
49 |
Correct |
6 ms |
23132 KB |
Output is correct |
50 |
Correct |
7 ms |
23132 KB |
Output is correct |
51 |
Correct |
7 ms |
23132 KB |
Output is correct |
52 |
Correct |
7 ms |
22964 KB |
Output is correct |
53 |
Correct |
8 ms |
23132 KB |
Output is correct |
54 |
Correct |
7 ms |
22960 KB |
Output is correct |
55 |
Correct |
316 ms |
105992 KB |
Output is correct |
56 |
Correct |
7 ms |
23384 KB |
Output is correct |
57 |
Correct |
75 ms |
23792 KB |
Output is correct |
58 |
Correct |
16 ms |
25692 KB |
Output is correct |
59 |
Correct |
9 ms |
23640 KB |
Output is correct |
60 |
Execution timed out |
3543 ms |
59860 KB |
Time limit exceeded |
61 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
23132 KB |
Output is correct |
2 |
Correct |
6 ms |
23132 KB |
Output is correct |
3 |
Correct |
6 ms |
23132 KB |
Output is correct |
4 |
Correct |
6 ms |
23132 KB |
Output is correct |
5 |
Correct |
7 ms |
23132 KB |
Output is correct |
6 |
Correct |
7 ms |
23132 KB |
Output is correct |
7 |
Correct |
7 ms |
23132 KB |
Output is correct |
8 |
Correct |
7 ms |
23136 KB |
Output is correct |
9 |
Correct |
142 ms |
66568 KB |
Output is correct |
10 |
Correct |
19 ms |
27204 KB |
Output is correct |
11 |
Correct |
74 ms |
46184 KB |
Output is correct |
12 |
Correct |
25 ms |
29472 KB |
Output is correct |
13 |
Correct |
19 ms |
26148 KB |
Output is correct |
14 |
Correct |
7 ms |
23132 KB |
Output is correct |
15 |
Correct |
7 ms |
23132 KB |
Output is correct |
16 |
Correct |
146 ms |
66704 KB |
Output is correct |
17 |
Correct |
7 ms |
23132 KB |
Output is correct |
18 |
Correct |
7 ms |
23128 KB |
Output is correct |
19 |
Correct |
7 ms |
23132 KB |
Output is correct |
20 |
Correct |
394 ms |
133756 KB |
Output is correct |
21 |
Correct |
328 ms |
117232 KB |
Output is correct |
22 |
Correct |
393 ms |
117252 KB |
Output is correct |
23 |
Correct |
311 ms |
109696 KB |
Output is correct |
24 |
Correct |
60 ms |
34388 KB |
Output is correct |
25 |
Correct |
59 ms |
34388 KB |
Output is correct |
26 |
Correct |
60 ms |
34384 KB |
Output is correct |
27 |
Correct |
351 ms |
122568 KB |
Output is correct |
28 |
Correct |
369 ms |
122468 KB |
Output is correct |
29 |
Correct |
368 ms |
124052 KB |
Output is correct |
30 |
Correct |
371 ms |
124112 KB |
Output is correct |
31 |
Correct |
7 ms |
23132 KB |
Output is correct |
32 |
Execution timed out |
3506 ms |
26756 KB |
Time limit exceeded |
33 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
23132 KB |
Output is correct |
2 |
Correct |
6 ms |
23132 KB |
Output is correct |
3 |
Correct |
6 ms |
23132 KB |
Output is correct |
4 |
Correct |
6 ms |
23132 KB |
Output is correct |
5 |
Correct |
7 ms |
23132 KB |
Output is correct |
6 |
Correct |
7 ms |
23132 KB |
Output is correct |
7 |
Correct |
7 ms |
23132 KB |
Output is correct |
8 |
Correct |
7 ms |
23136 KB |
Output is correct |
9 |
Correct |
142 ms |
66568 KB |
Output is correct |
10 |
Correct |
19 ms |
27204 KB |
Output is correct |
11 |
Correct |
74 ms |
46184 KB |
Output is correct |
12 |
Correct |
25 ms |
29472 KB |
Output is correct |
13 |
Correct |
19 ms |
26148 KB |
Output is correct |
14 |
Correct |
7 ms |
23132 KB |
Output is correct |
15 |
Correct |
7 ms |
23132 KB |
Output is correct |
16 |
Correct |
146 ms |
66704 KB |
Output is correct |
17 |
Correct |
365 ms |
121252 KB |
Output is correct |
18 |
Correct |
391 ms |
129872 KB |
Output is correct |
19 |
Correct |
364 ms |
117316 KB |
Output is correct |
20 |
Correct |
358 ms |
108988 KB |
Output is correct |
21 |
Correct |
355 ms |
110460 KB |
Output is correct |
22 |
Correct |
7 ms |
23384 KB |
Output is correct |
23 |
Execution timed out |
3573 ms |
30792 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
23132 KB |
Output is correct |
2 |
Correct |
6 ms |
23132 KB |
Output is correct |
3 |
Correct |
6 ms |
23132 KB |
Output is correct |
4 |
Correct |
6 ms |
23132 KB |
Output is correct |
5 |
Correct |
7 ms |
23132 KB |
Output is correct |
6 |
Correct |
7 ms |
23132 KB |
Output is correct |
7 |
Correct |
7 ms |
23132 KB |
Output is correct |
8 |
Correct |
7 ms |
23136 KB |
Output is correct |
9 |
Correct |
142 ms |
66568 KB |
Output is correct |
10 |
Correct |
19 ms |
27204 KB |
Output is correct |
11 |
Correct |
74 ms |
46184 KB |
Output is correct |
12 |
Correct |
25 ms |
29472 KB |
Output is correct |
13 |
Correct |
19 ms |
26148 KB |
Output is correct |
14 |
Correct |
7 ms |
23132 KB |
Output is correct |
15 |
Correct |
7 ms |
23132 KB |
Output is correct |
16 |
Correct |
146 ms |
66704 KB |
Output is correct |
17 |
Correct |
6 ms |
23132 KB |
Output is correct |
18 |
Correct |
6 ms |
23132 KB |
Output is correct |
19 |
Correct |
6 ms |
23128 KB |
Output is correct |
20 |
Correct |
7 ms |
23132 KB |
Output is correct |
21 |
Correct |
7 ms |
23132 KB |
Output is correct |
22 |
Correct |
7 ms |
23132 KB |
Output is correct |
23 |
Correct |
320 ms |
108836 KB |
Output is correct |
24 |
Correct |
6 ms |
23132 KB |
Output is correct |
25 |
Correct |
8 ms |
23644 KB |
Output is correct |
26 |
Correct |
8 ms |
23132 KB |
Output is correct |
27 |
Correct |
8 ms |
23132 KB |
Output is correct |
28 |
Correct |
119 ms |
55728 KB |
Output is correct |
29 |
Correct |
180 ms |
73868 KB |
Output is correct |
30 |
Correct |
240 ms |
88240 KB |
Output is correct |
31 |
Correct |
305 ms |
108500 KB |
Output is correct |
32 |
Correct |
8 ms |
23128 KB |
Output is correct |
33 |
Correct |
7 ms |
23132 KB |
Output is correct |
34 |
Correct |
7 ms |
23132 KB |
Output is correct |
35 |
Correct |
7 ms |
22956 KB |
Output is correct |
36 |
Correct |
7 ms |
23132 KB |
Output is correct |
37 |
Correct |
6 ms |
23132 KB |
Output is correct |
38 |
Correct |
7 ms |
23128 KB |
Output is correct |
39 |
Correct |
6 ms |
23132 KB |
Output is correct |
40 |
Correct |
6 ms |
23132 KB |
Output is correct |
41 |
Correct |
7 ms |
23132 KB |
Output is correct |
42 |
Correct |
8 ms |
23132 KB |
Output is correct |
43 |
Correct |
7 ms |
23132 KB |
Output is correct |
44 |
Correct |
7 ms |
23132 KB |
Output is correct |
45 |
Correct |
169 ms |
68284 KB |
Output is correct |
46 |
Correct |
263 ms |
88852 KB |
Output is correct |
47 |
Correct |
266 ms |
88768 KB |
Output is correct |
48 |
Correct |
8 ms |
23132 KB |
Output is correct |
49 |
Correct |
6 ms |
23132 KB |
Output is correct |
50 |
Correct |
7 ms |
23132 KB |
Output is correct |
51 |
Correct |
7 ms |
23132 KB |
Output is correct |
52 |
Correct |
7 ms |
22964 KB |
Output is correct |
53 |
Correct |
8 ms |
23132 KB |
Output is correct |
54 |
Correct |
7 ms |
22960 KB |
Output is correct |
55 |
Correct |
316 ms |
105992 KB |
Output is correct |
56 |
Correct |
7 ms |
23384 KB |
Output is correct |
57 |
Correct |
75 ms |
23792 KB |
Output is correct |
58 |
Correct |
16 ms |
25692 KB |
Output is correct |
59 |
Correct |
9 ms |
23640 KB |
Output is correct |
60 |
Execution timed out |
3543 ms |
59860 KB |
Time limit exceeded |
61 |
Halted |
0 ms |
0 KB |
- |