#include "parks.h"
#include<iostream>
#include<cmath>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
vector <int> v[200005],vx,vy,u2,c2,v2,a2,b2;
vector <pair<pair<int,int>,int> > v1;
set <pair<int,int> > s;
vector <pair<int,int> > c;
map <pair<int,int>,int> m;
bool comp(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b) {
return a.first.second<b.first.second;
}
int bio[200005],dx[4]={1,1,-1,-1},dy[4]={1,-1,1,-1},cnt;
void dfs(int x) {
bio[x]=1;
cnt+=1;
c2.push_back(x);
for(int i=0;i<v[x].size();i++) {
if(!bio[v[x][i]]) {
c.push_back(make_pair(x,v[x][i]));
dfs(v[x][i]);
}
}
}
int ok(int x,int y,int a,int b) {
if(vx[a]==vx[b] && abs(x-vx[a])==1 && y==(vy[a]+vy[b])/2) return 1;
if(vy[a]==vy[b] && abs(y-vy[a])==1 && x==(vx[a]+vx[b])/2) return 1;
return 0;
}
int construct_roads(std::vector<int> x,std::vector<int> y) {
vx=x;
vy=y;
int n=x.size(),minx=1e9,maxx=-1e9;
if(n==1) {
build({},{},{},{});
return 1;
}
for(int i=0;i<n;i++) {
v1.push_back(make_pair(make_pair(x[i],y[i]),i));
s.insert(make_pair(x[i]-1,y[i]-1));
s.insert(make_pair(x[i]+1,y[i]-1));
s.insert(make_pair(x[i]-1,y[i]+1));
s.insert(make_pair(x[i]+1,y[i]+1));
m[make_pair(x[i],y[i])]=i+1;
maxx=max(maxx,x[i]);
minx=min(minx,x[i]);
}
sort(v1.begin(),v1.end(),comp);
for(int i=0;i<v1.size();i++) {
for(int j=i+1;j<v1.size() && j-i<=20;j++) {
int x1=v1[i].first.first,y1=v1[i].first.second,x2=v1[j].first.first,y2=v1[j].first.second,i2=v1[i].second,j2=v1[j].second;
if((abs(x1-x2)==2 && y1==y2) || (abs(y1-y2)==2 && x1==x2)) {
v[i2].push_back(j2);
v[j2].push_back(i2);
u2.push_back(i2);
v2.push_back(j2);
//cout << i2 << " " << j2 << "\n";
}
}
}
if(!(maxx<=4 && minx>=2)) {
u2.clear();
v2.clear();
for(int i=0;i<n;i++) {
v[i].clear();
}
for(int i=0;i<n;i++) {
if(m[make_pair(x[i]+2,y[i])]) {
v[m[make_pair(x[i]+2,y[i])]-1].push_back(i);
u2.push_back(m[make_pair(x[i]+2,y[i])]-1);
v2.push_back(i);
}
if(m[make_pair(x[i],y[i]+2)]) {
v[m[make_pair(x[i],y[i]+2)]-1].push_back(i);
u2.push_back(m[make_pair(x[i],y[i]+2)]-1);
v2.push_back(i);
}
if(m[make_pair(x[i]-2,y[i])]) {
v[m[make_pair(x[i]-2,y[i])]-1].push_back(i);
u2.push_back(m[make_pair(x[i]-2,y[i])]-1);
v2.push_back(i);
}
if(m[make_pair(x[i],y[i]-2)]) {
v[m[make_pair(x[i],y[i]-2)]-1].push_back(i);
u2.push_back(m[make_pair(x[i],y[i]-2)]-1);
v2.push_back(i);
}
}
}
dfs(0);
//cout << cnt << "\n";
if(cnt<n) return 0;
if(minx>=2 && maxx<=4) {
for(int i=0;i<u2.size();i++) {
if(y[u2[i]]==y[v2[i]]) {
a2.push_back(3);
b2.push_back(y[v2[i]]-1);
}
else if(x[u2[i]]==4) {
a2.push_back(5);
b2.push_back(y[v2[i]]-1);
}
else {
a2.push_back(1);
b2.push_back(y[v2[i]]-1);
}
}
}
else {
u2.clear();
v2.clear();
for(int i=0;i<n-1;i++) {
a2.push_back(-1);
b2.push_back(-1);
u2.push_back(c[i].first);
v2.push_back(c[i].second);
}
for(int i=0;i<n-1;i++) {
for(int j=0;j<4;j++) {
if(s.find(make_pair(x[c2[i]]+dx[j],y[c2[i]]+dy[j]))!=s.end() && ok(x[c2[i]]+dx[j],y[c2[i]]+dy[j],u2[i],v2[i])) {
a2[i]=x[c2[i]]+dx[j];
b2[i]=y[c2[i]]+dy[j];
s.erase(make_pair(x[c2[i]]+dx[j],y[c2[i]]+dy[j]));
break;
}
if(s.find(make_pair(x[c2[i+1]]+dx[j],y[c2[i+1]]+dy[j]))!=s.end() && ok(x[c2[i+1]]+dx[j],y[c2[i+1]]+dy[j],u2[i],v2[i])) {
a2[i]=x[c2[i+1]]+dx[j];
b2[i]=y[c2[i+1]]+dy[j];
s.erase(make_pair(x[c2[i+1]]+dx[j],y[c2[i+1]]+dy[j]));
break;
}
}
}
/*cout << "\n\n";
for(int i=0;i<u2.size();i++) {
cout << u2[i] << " " << v2[i] << "\n";
}
cout << "\n";
for(int i=0;i<a2.size();i++) {
cout << a2[i] << " " << b2[i] << "\n";
}*/
}
build(u2,v2,a2,b2);
return 1;
}
Compilation message
parks.cpp: In function 'void dfs(int)':
parks.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i=0;i<v[x].size();i++) {
| ~^~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i=0;i<v1.size();i++) {
| ~^~~~~~~~~~
parks.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int j=i+1;j<v1.size() && j-i<=20;j++) {
| ~^~~~~~~~~~
parks.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i=0;i<u2.size();i++) {
| ~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4924 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4876 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
330 ms |
42552 KB |
Output is correct |
10 |
Correct |
20 ms |
8780 KB |
Output is correct |
11 |
Correct |
110 ms |
25316 KB |
Output is correct |
12 |
Correct |
31 ms |
10696 KB |
Output is correct |
13 |
Correct |
68 ms |
18172 KB |
Output is correct |
14 |
Correct |
5 ms |
5196 KB |
Output is correct |
15 |
Correct |
8 ms |
5452 KB |
Output is correct |
16 |
Correct |
334 ms |
39356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4924 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4876 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
330 ms |
42552 KB |
Output is correct |
10 |
Correct |
20 ms |
8780 KB |
Output is correct |
11 |
Correct |
110 ms |
25316 KB |
Output is correct |
12 |
Correct |
31 ms |
10696 KB |
Output is correct |
13 |
Correct |
68 ms |
18172 KB |
Output is correct |
14 |
Correct |
5 ms |
5196 KB |
Output is correct |
15 |
Correct |
8 ms |
5452 KB |
Output is correct |
16 |
Correct |
334 ms |
39356 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
4 ms |
4940 KB |
Output is correct |
19 |
Correct |
5 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
5 ms |
4940 KB |
Output is correct |
22 |
Correct |
3 ms |
4940 KB |
Output is correct |
23 |
Correct |
879 ms |
83128 KB |
Output is correct |
24 |
Correct |
4 ms |
4940 KB |
Output is correct |
25 |
Correct |
7 ms |
5452 KB |
Output is correct |
26 |
Correct |
9 ms |
5716 KB |
Output is correct |
27 |
Correct |
10 ms |
5836 KB |
Output is correct |
28 |
Correct |
325 ms |
36396 KB |
Output is correct |
29 |
Correct |
479 ms |
52044 KB |
Output is correct |
30 |
Correct |
678 ms |
67544 KB |
Output is correct |
31 |
Correct |
1016 ms |
83124 KB |
Output is correct |
32 |
Correct |
3 ms |
4940 KB |
Output is correct |
33 |
Correct |
3 ms |
4940 KB |
Output is correct |
34 |
Correct |
3 ms |
4940 KB |
Output is correct |
35 |
Correct |
3 ms |
4940 KB |
Output is correct |
36 |
Correct |
3 ms |
4940 KB |
Output is correct |
37 |
Correct |
3 ms |
4940 KB |
Output is correct |
38 |
Correct |
5 ms |
4940 KB |
Output is correct |
39 |
Correct |
3 ms |
4940 KB |
Output is correct |
40 |
Correct |
4 ms |
4940 KB |
Output is correct |
41 |
Correct |
4 ms |
4940 KB |
Output is correct |
42 |
Correct |
4 ms |
4940 KB |
Output is correct |
43 |
Correct |
7 ms |
5556 KB |
Output is correct |
44 |
Correct |
11 ms |
5708 KB |
Output is correct |
45 |
Correct |
383 ms |
40184 KB |
Output is correct |
46 |
Correct |
674 ms |
56536 KB |
Output is correct |
47 |
Correct |
635 ms |
56000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4924 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4876 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
330 ms |
42552 KB |
Output is correct |
10 |
Correct |
20 ms |
8780 KB |
Output is correct |
11 |
Correct |
110 ms |
25316 KB |
Output is correct |
12 |
Correct |
31 ms |
10696 KB |
Output is correct |
13 |
Correct |
68 ms |
18172 KB |
Output is correct |
14 |
Correct |
5 ms |
5196 KB |
Output is correct |
15 |
Correct |
8 ms |
5452 KB |
Output is correct |
16 |
Correct |
334 ms |
39356 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
4 ms |
4940 KB |
Output is correct |
19 |
Correct |
5 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
5 ms |
4940 KB |
Output is correct |
22 |
Correct |
3 ms |
4940 KB |
Output is correct |
23 |
Correct |
879 ms |
83128 KB |
Output is correct |
24 |
Correct |
4 ms |
4940 KB |
Output is correct |
25 |
Correct |
7 ms |
5452 KB |
Output is correct |
26 |
Correct |
9 ms |
5716 KB |
Output is correct |
27 |
Correct |
10 ms |
5836 KB |
Output is correct |
28 |
Correct |
325 ms |
36396 KB |
Output is correct |
29 |
Correct |
479 ms |
52044 KB |
Output is correct |
30 |
Correct |
678 ms |
67544 KB |
Output is correct |
31 |
Correct |
1016 ms |
83124 KB |
Output is correct |
32 |
Correct |
3 ms |
4940 KB |
Output is correct |
33 |
Correct |
3 ms |
4940 KB |
Output is correct |
34 |
Correct |
3 ms |
4940 KB |
Output is correct |
35 |
Correct |
3 ms |
4940 KB |
Output is correct |
36 |
Correct |
3 ms |
4940 KB |
Output is correct |
37 |
Correct |
3 ms |
4940 KB |
Output is correct |
38 |
Correct |
5 ms |
4940 KB |
Output is correct |
39 |
Correct |
3 ms |
4940 KB |
Output is correct |
40 |
Correct |
4 ms |
4940 KB |
Output is correct |
41 |
Correct |
4 ms |
4940 KB |
Output is correct |
42 |
Correct |
4 ms |
4940 KB |
Output is correct |
43 |
Correct |
7 ms |
5556 KB |
Output is correct |
44 |
Correct |
11 ms |
5708 KB |
Output is correct |
45 |
Correct |
383 ms |
40184 KB |
Output is correct |
46 |
Correct |
674 ms |
56536 KB |
Output is correct |
47 |
Correct |
635 ms |
56000 KB |
Output is correct |
48 |
Correct |
3 ms |
4940 KB |
Output is correct |
49 |
Correct |
3 ms |
4940 KB |
Output is correct |
50 |
Correct |
3 ms |
4940 KB |
Output is correct |
51 |
Correct |
3 ms |
4940 KB |
Output is correct |
52 |
Correct |
3 ms |
4980 KB |
Output is correct |
53 |
Correct |
3 ms |
4940 KB |
Output is correct |
54 |
Correct |
3 ms |
4940 KB |
Output is correct |
55 |
Incorrect |
1918 ms |
77624 KB |
Tree (a[67], b[67]) = (-1, -1) is not adjacent to edge between u[67]=185767 @(2, 94996) and v[67]=192671 @(4, 94996) |
56 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4924 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4876 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
330 ms |
42552 KB |
Output is correct |
10 |
Correct |
20 ms |
8780 KB |
Output is correct |
11 |
Correct |
110 ms |
25316 KB |
Output is correct |
12 |
Correct |
31 ms |
10696 KB |
Output is correct |
13 |
Correct |
68 ms |
18172 KB |
Output is correct |
14 |
Correct |
5 ms |
5196 KB |
Output is correct |
15 |
Correct |
8 ms |
5452 KB |
Output is correct |
16 |
Correct |
334 ms |
39356 KB |
Output is correct |
17 |
Correct |
4 ms |
4940 KB |
Output is correct |
18 |
Correct |
4 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
1833 ms |
96552 KB |
Output is correct |
21 |
Correct |
1978 ms |
93336 KB |
Output is correct |
22 |
Correct |
1773 ms |
91384 KB |
Output is correct |
23 |
Correct |
1473 ms |
88364 KB |
Output is correct |
24 |
Correct |
1387 ms |
87184 KB |
Output is correct |
25 |
Correct |
1971 ms |
66040 KB |
Output is correct |
26 |
Correct |
1841 ms |
66080 KB |
Output is correct |
27 |
Incorrect |
1806 ms |
79876 KB |
Tree (a[88844], b[88844]) = (-1, -1) is not adjacent to edge between u[88844]=105901 @(10, 2) and v[88844]=148789 @(10, 4) |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4924 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4876 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
330 ms |
42552 KB |
Output is correct |
10 |
Correct |
20 ms |
8780 KB |
Output is correct |
11 |
Correct |
110 ms |
25316 KB |
Output is correct |
12 |
Correct |
31 ms |
10696 KB |
Output is correct |
13 |
Correct |
68 ms |
18172 KB |
Output is correct |
14 |
Correct |
5 ms |
5196 KB |
Output is correct |
15 |
Correct |
8 ms |
5452 KB |
Output is correct |
16 |
Correct |
334 ms |
39356 KB |
Output is correct |
17 |
Correct |
1970 ms |
108304 KB |
Output is correct |
18 |
Correct |
1854 ms |
106928 KB |
Output is correct |
19 |
Correct |
1973 ms |
96656 KB |
Output is correct |
20 |
Incorrect |
2021 ms |
68136 KB |
Tree (a[89], b[89]) = (-1, -1) is not adjacent to edge between u[89]=92263 @(322, 866) and v[89]=154768 @(322, 868) |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4924 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4876 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
330 ms |
42552 KB |
Output is correct |
10 |
Correct |
20 ms |
8780 KB |
Output is correct |
11 |
Correct |
110 ms |
25316 KB |
Output is correct |
12 |
Correct |
31 ms |
10696 KB |
Output is correct |
13 |
Correct |
68 ms |
18172 KB |
Output is correct |
14 |
Correct |
5 ms |
5196 KB |
Output is correct |
15 |
Correct |
8 ms |
5452 KB |
Output is correct |
16 |
Correct |
334 ms |
39356 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
4 ms |
4940 KB |
Output is correct |
19 |
Correct |
5 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
5 ms |
4940 KB |
Output is correct |
22 |
Correct |
3 ms |
4940 KB |
Output is correct |
23 |
Correct |
879 ms |
83128 KB |
Output is correct |
24 |
Correct |
4 ms |
4940 KB |
Output is correct |
25 |
Correct |
7 ms |
5452 KB |
Output is correct |
26 |
Correct |
9 ms |
5716 KB |
Output is correct |
27 |
Correct |
10 ms |
5836 KB |
Output is correct |
28 |
Correct |
325 ms |
36396 KB |
Output is correct |
29 |
Correct |
479 ms |
52044 KB |
Output is correct |
30 |
Correct |
678 ms |
67544 KB |
Output is correct |
31 |
Correct |
1016 ms |
83124 KB |
Output is correct |
32 |
Correct |
3 ms |
4940 KB |
Output is correct |
33 |
Correct |
3 ms |
4940 KB |
Output is correct |
34 |
Correct |
3 ms |
4940 KB |
Output is correct |
35 |
Correct |
3 ms |
4940 KB |
Output is correct |
36 |
Correct |
3 ms |
4940 KB |
Output is correct |
37 |
Correct |
3 ms |
4940 KB |
Output is correct |
38 |
Correct |
5 ms |
4940 KB |
Output is correct |
39 |
Correct |
3 ms |
4940 KB |
Output is correct |
40 |
Correct |
4 ms |
4940 KB |
Output is correct |
41 |
Correct |
4 ms |
4940 KB |
Output is correct |
42 |
Correct |
4 ms |
4940 KB |
Output is correct |
43 |
Correct |
7 ms |
5556 KB |
Output is correct |
44 |
Correct |
11 ms |
5708 KB |
Output is correct |
45 |
Correct |
383 ms |
40184 KB |
Output is correct |
46 |
Correct |
674 ms |
56536 KB |
Output is correct |
47 |
Correct |
635 ms |
56000 KB |
Output is correct |
48 |
Correct |
3 ms |
4940 KB |
Output is correct |
49 |
Correct |
3 ms |
4940 KB |
Output is correct |
50 |
Correct |
3 ms |
4940 KB |
Output is correct |
51 |
Correct |
3 ms |
4940 KB |
Output is correct |
52 |
Correct |
3 ms |
4980 KB |
Output is correct |
53 |
Correct |
3 ms |
4940 KB |
Output is correct |
54 |
Correct |
3 ms |
4940 KB |
Output is correct |
55 |
Incorrect |
1918 ms |
77624 KB |
Tree (a[67], b[67]) = (-1, -1) is not adjacent to edge between u[67]=185767 @(2, 94996) and v[67]=192671 @(4, 94996) |
56 |
Halted |
0 ms |
0 KB |
- |