#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define x X
#define y Y
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 2e5;
const vector<pii > directions = {mp(-2, 0), mp(0, -2), mp(0, 2), mp(2, 0)};
bool check_possibility(int n, vector<int> x, vector<int> y) {
unordered_map<int, unordered_map<int, bool> > m;
unordered_map<int, unordered_map<int, int> > f;
for(int i = 0; i < n; i++) {
f[x[i]][y[i]] = i + 1;
}
queue<int> q;
q.push(0);
m[x[0]][y[0]] = true;
int cnt = 0;
while(!q.empty()) {
int cur = q.front();
q.pop();
cnt++;
for(pii dir : directions) {
pii new_point = mp(x[cur] + dir.fi, y[cur] + dir.se);
if(f[new_point.fi][new_point.se] && !m[new_point.fi][new_point.se]) {
m[new_point.fi][new_point.se] = true;
int new_id = f[new_point.fi][new_point.se] - 1;
q.push(new_id);
}
}
}
return (cnt == n);
}
struct fountain {
int x, y, id;
fountain() : x(0), y(0), id(-1) {}
fountain(int x_, int y_, int id_) :
x(x_), y(y_), id(id_) {}
};
int n;
vector<fountain > points;
vector<int> x;
vector<int> y;
unordered_map<int, unordered_map<int, int> > fountain_at;
unordered_map<int, unordered_map<int, bool> > bench_at;
unordered_map<int, unordered_map<int, bool> > road_at;
vector<int> ans_u;
vector<int> ans_v;
vector<int> ans_a;
vector<int> ans_b;
void build_road_bench(int road_u, int road_v, pii bench_pos) {
ans_u.pb(road_u);
ans_v.pb(road_v);
ans_a.pb(bench_pos.fi);
ans_b.pb(bench_pos.se);
bench_at[bench_pos.fi][bench_pos.se] = true;
road_at[(points[road_u].x + points[road_v].x) / 2][(points[road_u].y + points[road_v].y) / 2] = true;
}
vector<pii> get_bench_locations_pii(pii a, pii b) {
fountain f_a = fountain(a.fi, a.se, -1), f_b = fountain(b.fi, b.se, -1);
if(f_a.x == f_b.x) {
int new_y = (f_a.y + f_b.y) / 2;
a = mp(f_a.x + 1, new_y), b = mp(f_a.x - 1, new_y);
} else {
int new_x = (f_a.x + f_b.x) / 2;
a = mp(new_x, f_a.y + 1), b = mp(new_x, f_a.y - 1);
}
return {min(a, b), max(a, b)};
}
vector<pii> get_bench_locations(int a_idx, int b_idx) {
fountain f_a = points[a_idx], f_b = points[b_idx];
pii a, b;
if(f_a.x == f_b.x) {
int new_y = (f_a.y + f_b.y) / 2;
a = mp(f_a.x + 1, new_y), b = mp(f_a.x - 1, new_y);
} else {
int new_x = (f_a.x + f_b.x) / 2;
a = mp(new_x, f_a.y + 1), b = mp(new_x, f_a.y - 1);
}
return {min(a, b), max(a, b)};
}
int get_middle_of_intersection(int a_idx, int b_idx) {
pii a = mp(points[a_idx].x, points[a_idx].y);
pii b = mp(points[b_idx].x, points[b_idx].y);
int cnt = 0;
for(pii dir : directions) {
pii nei = mp(a.fi + dir.fi, a.se + dir.se);
if(fountain_at[nei.fi][nei.se]) {
cnt++;
}
}
if(cnt == 4) {
return a_idx;
}
cnt = 0;
for(pii dir : directions) {
pii nei = mp(b.fi + dir.fi, b.se + dir.se);
if(fountain_at[nei.fi][nei.se]) {
cnt++;
}
}
if(cnt == 4) {
return b_idx;
}
return -1;
}
pii get_bench_when_in_intersection(int a_idx, int b_idx) {
// a is the middle, b is a neighbour
fountain a = points[a_idx], b = points[b_idx];
if(b.x < a.x) {
return mp(a.x - 1, a.y + 1);
}
if(b.y < a.y) {
return mp(a.x - 1, a.y - 1);
}
if(b.y > a.y) {
return mp(a.x + 1, a.y + 1);
}
if(b.x > a.x) {
return mp(a.x + 1, a.y - 1);
}
}
pii orig;
unordered_map<int, unordered_map<int, bool> > not_bad;
bool bad_bench(pii bench, pii a, pii b) {
if(not_bad[bench.fi][bench.se]) {
return false;
}
if(a > b) {
swap(a, b);
}
vector<pii > v = {a, b};
for(pii dir : directions) {
pii other = mp(bench.fi + dir.fi, bench.se + dir.se);
vector<pii> corners = get_bench_locations_pii(bench, other);
if(corners != v) {
if(fountain_at[corners[0].fi][corners[0].se] &&
fountain_at[corners[1].fi][corners[1].se] &&
//bench_at[other.fi][other.se] &&
!road_at[(bench.fi + other.fi) / 2][(bench.se + other.se) / 2]) {
if(other == orig) {
not_bad[bench.fi][bench.se] = true;
return false;
}
if(bench_at[other.fi][other.se]) {
return true;
} else {
return bad_bench(other, corners[0], corners[1]);
}
}
}
}
not_bad[bench.fi][bench.se] = true;
return false;
}
void solve() {
unordered_map<int, unordered_map<int, bool> > vis;
queue<int> q;
q.push(0);
vis[x[0]][y[0]] = true;
while(!q.empty()) {
int cur = q.front();
q.pop();
for(pii dir : directions) {
pii new_point = mp(x[cur] + dir.fi, y[cur] + dir.se);
if(fountain_at[new_point.fi][new_point.se] && !vis[new_point.fi][new_point.se]) {
vis[new_point.fi][new_point.se] = true;
int new_id = fountain_at[new_point.fi][new_point.se] - 1;
q.push(new_id);
int mid = get_middle_of_intersection(cur, new_id);
if(mid != -1) {
build_road_bench(cur, new_id, get_bench_when_in_intersection(mid, cur ^ new_id ^ mid));
} else {
vector<pii> benches = get_bench_locations(cur, new_id);
orig = benches[0];
if(!bench_at[benches[0].fi][benches[0].se] && !bad_bench(benches[0], mp(points[cur].x, points[cur].y), mp(points[new_id].x, points[new_id].y))) {
build_road_bench(cur, new_id, benches[0]);
} else {
build_road_bench(cur, new_id, benches[1]);
}
}
}
}
}
//
}
#undef x
#undef y
int construct_roads(vector<int> x, vector<int> y) {
// edge case
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
// sample solution
/*vector<int> u, v, a, b;
u.push_back(0);
v.push_back(1);
a.push_back(x[0]+1);
b.push_back(y[0]-1);
build(u, v, a, b);*/
n = x.size();
if(!check_possibility(n, x, y)) {
return 0;
}
X = x;
Y = y;
points.assign(n, fountain());
for(int i = 0; i < n; i++) {
points[i] = fountain(x[i], y[i], i);
fountain_at[x[i]][y[i]] = i + 1;
}
solve();
// build solution
build(ans_u, ans_v, ans_a, ans_b);
return 1;
}
/*
5
4 4
4 6
6 4
4 2
2 4
*/
Compilation message
parks.cpp: In function 'std::pair<int, int> get_bench_when_in_intersection(int, int)':
parks.cpp:138:1: warning: control reaches end of non-void function [-Wreturn-type]
138 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
295 ms |
40824 KB |
Output is correct |
10 |
Correct |
18 ms |
3924 KB |
Output is correct |
11 |
Correct |
106 ms |
21264 KB |
Output is correct |
12 |
Correct |
28 ms |
6120 KB |
Output is correct |
13 |
Correct |
22 ms |
7136 KB |
Output is correct |
14 |
Correct |
2 ms |
340 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
271 ms |
40952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
295 ms |
40824 KB |
Output is correct |
10 |
Correct |
18 ms |
3924 KB |
Output is correct |
11 |
Correct |
106 ms |
21264 KB |
Output is correct |
12 |
Correct |
28 ms |
6120 KB |
Output is correct |
13 |
Correct |
22 ms |
7136 KB |
Output is correct |
14 |
Correct |
2 ms |
340 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
271 ms |
40952 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
595 ms |
72764 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
3 ms |
776 KB |
Output is correct |
26 |
Correct |
1 ms |
596 KB |
Output is correct |
27 |
Correct |
2 ms |
596 KB |
Output is correct |
28 |
Correct |
178 ms |
26640 KB |
Output is correct |
29 |
Correct |
405 ms |
47716 KB |
Output is correct |
30 |
Correct |
456 ms |
61740 KB |
Output is correct |
31 |
Correct |
595 ms |
72700 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
0 ms |
212 KB |
Output is correct |
43 |
Correct |
2 ms |
468 KB |
Output is correct |
44 |
Correct |
1 ms |
468 KB |
Output is correct |
45 |
Correct |
385 ms |
36392 KB |
Output is correct |
46 |
Correct |
598 ms |
53148 KB |
Output is correct |
47 |
Correct |
574 ms |
53372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
295 ms |
40824 KB |
Output is correct |
10 |
Correct |
18 ms |
3924 KB |
Output is correct |
11 |
Correct |
106 ms |
21264 KB |
Output is correct |
12 |
Correct |
28 ms |
6120 KB |
Output is correct |
13 |
Correct |
22 ms |
7136 KB |
Output is correct |
14 |
Correct |
2 ms |
340 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
271 ms |
40952 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
595 ms |
72764 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
3 ms |
776 KB |
Output is correct |
26 |
Correct |
1 ms |
596 KB |
Output is correct |
27 |
Correct |
2 ms |
596 KB |
Output is correct |
28 |
Correct |
178 ms |
26640 KB |
Output is correct |
29 |
Correct |
405 ms |
47716 KB |
Output is correct |
30 |
Correct |
456 ms |
61740 KB |
Output is correct |
31 |
Correct |
595 ms |
72700 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
0 ms |
212 KB |
Output is correct |
43 |
Correct |
2 ms |
468 KB |
Output is correct |
44 |
Correct |
1 ms |
468 KB |
Output is correct |
45 |
Correct |
385 ms |
36392 KB |
Output is correct |
46 |
Correct |
598 ms |
53148 KB |
Output is correct |
47 |
Correct |
574 ms |
53372 KB |
Output is correct |
48 |
Correct |
0 ms |
212 KB |
Output is correct |
49 |
Correct |
0 ms |
212 KB |
Output is correct |
50 |
Correct |
1 ms |
212 KB |
Output is correct |
51 |
Incorrect |
0 ms |
212 KB |
Tree @(5, 5) appears more than once: for edges on positions 1 and 4 |
52 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
295 ms |
40824 KB |
Output is correct |
10 |
Correct |
18 ms |
3924 KB |
Output is correct |
11 |
Correct |
106 ms |
21264 KB |
Output is correct |
12 |
Correct |
28 ms |
6120 KB |
Output is correct |
13 |
Correct |
22 ms |
7136 KB |
Output is correct |
14 |
Correct |
2 ms |
340 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
271 ms |
40952 KB |
Output is correct |
17 |
Correct |
0 ms |
252 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Execution timed out |
3559 ms |
185284 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
295 ms |
40824 KB |
Output is correct |
10 |
Correct |
18 ms |
3924 KB |
Output is correct |
11 |
Correct |
106 ms |
21264 KB |
Output is correct |
12 |
Correct |
28 ms |
6120 KB |
Output is correct |
13 |
Correct |
22 ms |
7136 KB |
Output is correct |
14 |
Correct |
2 ms |
340 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
271 ms |
40952 KB |
Output is correct |
17 |
Correct |
951 ms |
123544 KB |
Output is correct |
18 |
Correct |
1020 ms |
123600 KB |
Output is correct |
19 |
Execution timed out |
3580 ms |
136724 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
295 ms |
40824 KB |
Output is correct |
10 |
Correct |
18 ms |
3924 KB |
Output is correct |
11 |
Correct |
106 ms |
21264 KB |
Output is correct |
12 |
Correct |
28 ms |
6120 KB |
Output is correct |
13 |
Correct |
22 ms |
7136 KB |
Output is correct |
14 |
Correct |
2 ms |
340 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
271 ms |
40952 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
595 ms |
72764 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
3 ms |
776 KB |
Output is correct |
26 |
Correct |
1 ms |
596 KB |
Output is correct |
27 |
Correct |
2 ms |
596 KB |
Output is correct |
28 |
Correct |
178 ms |
26640 KB |
Output is correct |
29 |
Correct |
405 ms |
47716 KB |
Output is correct |
30 |
Correct |
456 ms |
61740 KB |
Output is correct |
31 |
Correct |
595 ms |
72700 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
0 ms |
212 KB |
Output is correct |
43 |
Correct |
2 ms |
468 KB |
Output is correct |
44 |
Correct |
1 ms |
468 KB |
Output is correct |
45 |
Correct |
385 ms |
36392 KB |
Output is correct |
46 |
Correct |
598 ms |
53148 KB |
Output is correct |
47 |
Correct |
574 ms |
53372 KB |
Output is correct |
48 |
Correct |
0 ms |
212 KB |
Output is correct |
49 |
Correct |
0 ms |
212 KB |
Output is correct |
50 |
Correct |
1 ms |
212 KB |
Output is correct |
51 |
Incorrect |
0 ms |
212 KB |
Tree @(5, 5) appears more than once: for edges on positions 1 and 4 |
52 |
Halted |
0 ms |
0 KB |
- |