#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> e;
int cc;
dsu(int n) {
cc=n;
e=vector<int> (n, -1);
}
int get(int a) {
if(e[a] < 0)return a;
return e[a] = get(e[a]);
}
bool unite(int a, int b) {
a=get(a), b=get(b);
if(a==b)return false;
cc--;
if(-e[a] > -e[b])swap(a, b);
e[b]+=e[a];
e[a]=b;
return true;
}
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
vector<vector<int>> p(7);
int n = x.size();
map<pair<int,int>, int> mp;
for(int i = 0;i<n;i++) {
mp[{x[i], y[i]}]=i;
p[x[i]].push_back(i);
}
dsu d(n);
vector<int> u, v;
for(int i= 0;i<7;i++) {
sort(p[i].begin(), p[i].end(), [&](int a, int b) {
return y[a] < y[b];
});
}
{
int i = 6;
for(int j = 1;j<(int)p[i].size();j++) {
if(y[p[i][j]] == y[p[i][j-1]] + 2){
if(d.unite(p[i][j], p[i][j-1])) {
v.push_back(p[i][j]);
u.push_back(p[i][j-1]);
}
}
}
}
{
int i = 2;
for(int j = 1;j<(int)p[i].size();j++) {
if(y[p[i][j]] == y[p[i][j-1]] + 2){
if(d.unite(p[i][j], p[i][j-1])) {
v.push_back(p[i][j]);
u.push_back(p[i][j-1]);
}
}
}
}
{
int i = 4;
for(int j = 1;j<(int)p[i].size();j++) {
if(y[p[i][j]] == y[p[i][j-1]] + 2){
if(d.unite(p[i][j], p[i][j-1])) {
v.push_back(p[i][j]);
u.push_back(p[i][j-1]);
}
}
}
}
{
for(int j:p[4]) {
if(mp.find({x[j]-2, y[j]}) != mp.end() and d.unite(j, mp[{x[j]-2, y[j]}])) {
u.push_back(mp[{x[j]-2, y[j]}]);
v.push_back(j);
}
}
for(int j:p[4]) {
if(mp.find({x[j]+2, y[j]}) != mp.end() and d.unite(j, mp[{x[j]+2, y[j]}])) {
v.push_back(mp[{x[j]+2, y[j]}]);
u.push_back(j);
}
}
}
// for(int i = 0;i<(int)v.size();i++) {
// cout << u[i] << " "<< v[i] << endl;
// }
vector<int> a, b;
if(d.cc != 1)return 0;
map<pair<int,int>, bool> used;
for(int j = 0;j<n-1;j++) {
if(x[u[j]] == x[v[j]]) {
if(x[u[j]] == 2) {
a.push_back(x[u[j]]-1);
b.push_back(y[u[j]]+1);
used[{x[u[j]]-1,y[u[j]]+1}]=1;
}
else if(x[u[j]] == 6) {
a.push_back(x[u[j]]+1);
b.push_back(y[u[j]]+1);
used[{x[u[j]]+1,y[u[j]]+1}]=1;
}
else if(x[u[j]] == 4) {
a.push_back(-1);
b.push_back(-1);
}
}
else if(x[u[j]] == 2) {
a.push_back(x[u[j]]+1);
b.push_back(y[u[j]]+1);
used[{x[u[j]]+1, y[u[j]]+1}]=1;
} else if(x[u[j]] == 4) {
a.push_back(x[u[j]]+1);
b.push_back(y[u[j]]-1);
used[{x[u[j]]+1, y[u[j]]-1}]=1;
}
}
for(int j = 0;j<n-1;j++) {
if(a[j] == -1) {
if(!used[{x[u[j]]-1, y[u[j]]+1}]) {
a[j] = x[u[j]]-1;
b[j] = y[u[j]]+1;
used[{x[u[j]]-1, y[u[j]]+1}]=1;
}
else if(!used[{x[u[j]]+1, y[u[j]]+1}]) {
a[j] = x[u[j]]+1;
b[j] = y[u[j]]+1;
used[{x[u[j]]+1, y[u[j]]+1}]=1;
}
else {
return 0;
}
}
}
build(u, v, a, b);
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
93 ms |
20008 KB |
Output is correct |
10 |
Correct |
6 ms |
2396 KB |
Output is correct |
11 |
Correct |
33 ms |
10896 KB |
Output is correct |
12 |
Correct |
8 ms |
3416 KB |
Output is correct |
13 |
Correct |
12 ms |
4780 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
2 ms |
600 KB |
Output is correct |
16 |
Correct |
92 ms |
20088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
93 ms |
20008 KB |
Output is correct |
10 |
Correct |
6 ms |
2396 KB |
Output is correct |
11 |
Correct |
33 ms |
10896 KB |
Output is correct |
12 |
Correct |
8 ms |
3416 KB |
Output is correct |
13 |
Correct |
12 ms |
4780 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
2 ms |
600 KB |
Output is correct |
16 |
Correct |
92 ms |
20088 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
600 KB |
Output is correct |
20 |
Correct |
0 ms |
344 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
222 ms |
39488 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
600 KB |
Output is correct |
27 |
Correct |
2 ms |
760 KB |
Output is correct |
28 |
Correct |
74 ms |
15940 KB |
Output is correct |
29 |
Correct |
119 ms |
23892 KB |
Output is correct |
30 |
Correct |
152 ms |
31616 KB |
Output is correct |
31 |
Correct |
212 ms |
39592 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
356 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
0 ms |
348 KB |
Output is correct |
43 |
Correct |
1 ms |
600 KB |
Output is correct |
44 |
Correct |
1 ms |
604 KB |
Output is correct |
45 |
Correct |
95 ms |
20012 KB |
Output is correct |
46 |
Correct |
153 ms |
28772 KB |
Output is correct |
47 |
Correct |
151 ms |
28776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
93 ms |
20008 KB |
Output is correct |
10 |
Correct |
6 ms |
2396 KB |
Output is correct |
11 |
Correct |
33 ms |
10896 KB |
Output is correct |
12 |
Correct |
8 ms |
3416 KB |
Output is correct |
13 |
Correct |
12 ms |
4780 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
2 ms |
600 KB |
Output is correct |
16 |
Correct |
92 ms |
20088 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
600 KB |
Output is correct |
20 |
Correct |
0 ms |
344 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
222 ms |
39488 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
600 KB |
Output is correct |
27 |
Correct |
2 ms |
760 KB |
Output is correct |
28 |
Correct |
74 ms |
15940 KB |
Output is correct |
29 |
Correct |
119 ms |
23892 KB |
Output is correct |
30 |
Correct |
152 ms |
31616 KB |
Output is correct |
31 |
Correct |
212 ms |
39592 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
356 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
0 ms |
348 KB |
Output is correct |
43 |
Correct |
1 ms |
600 KB |
Output is correct |
44 |
Correct |
1 ms |
604 KB |
Output is correct |
45 |
Correct |
95 ms |
20012 KB |
Output is correct |
46 |
Correct |
153 ms |
28772 KB |
Output is correct |
47 |
Correct |
151 ms |
28776 KB |
Output is correct |
48 |
Correct |
0 ms |
344 KB |
Output is correct |
49 |
Correct |
0 ms |
348 KB |
Output is correct |
50 |
Correct |
1 ms |
348 KB |
Output is correct |
51 |
Incorrect |
0 ms |
348 KB |
Solution announced impossible, but it is possible. |
52 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
93 ms |
20008 KB |
Output is correct |
10 |
Correct |
6 ms |
2396 KB |
Output is correct |
11 |
Correct |
33 ms |
10896 KB |
Output is correct |
12 |
Correct |
8 ms |
3416 KB |
Output is correct |
13 |
Correct |
12 ms |
4780 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
2 ms |
600 KB |
Output is correct |
16 |
Correct |
92 ms |
20088 KB |
Output is correct |
17 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
93 ms |
20008 KB |
Output is correct |
10 |
Correct |
6 ms |
2396 KB |
Output is correct |
11 |
Correct |
33 ms |
10896 KB |
Output is correct |
12 |
Correct |
8 ms |
3416 KB |
Output is correct |
13 |
Correct |
12 ms |
4780 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
2 ms |
600 KB |
Output is correct |
16 |
Correct |
92 ms |
20088 KB |
Output is correct |
17 |
Runtime error |
25 ms |
6748 KB |
Execution killed with signal 11 |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
93 ms |
20008 KB |
Output is correct |
10 |
Correct |
6 ms |
2396 KB |
Output is correct |
11 |
Correct |
33 ms |
10896 KB |
Output is correct |
12 |
Correct |
8 ms |
3416 KB |
Output is correct |
13 |
Correct |
12 ms |
4780 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
2 ms |
600 KB |
Output is correct |
16 |
Correct |
92 ms |
20088 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
600 KB |
Output is correct |
20 |
Correct |
0 ms |
344 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
222 ms |
39488 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
600 KB |
Output is correct |
27 |
Correct |
2 ms |
760 KB |
Output is correct |
28 |
Correct |
74 ms |
15940 KB |
Output is correct |
29 |
Correct |
119 ms |
23892 KB |
Output is correct |
30 |
Correct |
152 ms |
31616 KB |
Output is correct |
31 |
Correct |
212 ms |
39592 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
356 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
0 ms |
348 KB |
Output is correct |
43 |
Correct |
1 ms |
600 KB |
Output is correct |
44 |
Correct |
1 ms |
604 KB |
Output is correct |
45 |
Correct |
95 ms |
20012 KB |
Output is correct |
46 |
Correct |
153 ms |
28772 KB |
Output is correct |
47 |
Correct |
151 ms |
28776 KB |
Output is correct |
48 |
Correct |
0 ms |
344 KB |
Output is correct |
49 |
Correct |
0 ms |
348 KB |
Output is correct |
50 |
Correct |
1 ms |
348 KB |
Output is correct |
51 |
Incorrect |
0 ms |
348 KB |
Solution announced impossible, but it is possible. |
52 |
Halted |
0 ms |
0 KB |
- |