#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
struct point {
int x,y,index;
};
bool dist(point x,point y){
if (((x.x - y.x)*(x.x - y.x)+(x.y-y.y)*(x.y - y.y))!=4)return false;
return true;
}
int binarysearch(int seg,int eq,int n,vector<point>arr){
int left = 0;
int right = n-1;
while(left<=right){
int mid = (left + right) >> 1;
if (arr[mid].x<seg)left= mid + 1;
else if (arr[mid].x>seg)right = mid-1;
else {
if (arr[mid].y<eq){
left=mid+1;
}
else if (arr[mid].y>eq){
right = mid-1;
}
else return mid;
}
}
return -1;
}
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) ;
int construct_roads(std::vector<int> x, std::vector<int> y) {
vector<point>arr;
int n = x.size();
bool ok=true;
for (int i = 0 ;i<n;++i){
if (x[i]!=x[0])ok=false;
arr.push_back({x[i],y[i],i});
}
vector<int>ansx,ansy,ansxi,ansyi;
if (ok){
sort(arr.begin(),arr.end(),[&](point a,point b){
return a.y<b.y;
});
for (int i = 1;i<n;++i){
if (dist(arr[i],arr[i-1])){
ansx.push_back(min(arr[i].x,arr[i-1].x) + 1);
ansy.push_back(min(arr[i].y,arr[i-1].y)+1);
ansxi.push_back(arr[i].index);
ansyi.push_back(arr[i-1].index);
}
else return 0;
}
build(ansxi,ansyi,ansx,ansy);
return 1;}
else{
vector<vector<int>>adj(n);
vector<vector<bool>>p(3,vector<bool>(1e5 + 5,false));
sort(arr.begin(),arr.end(),[&](point a,point b){
if (a.x==b.x)return a.y<b.y;
return a.x<b.x;
});
int i =1;
for (;i<n;++i){
if (arr[i].x!=2)break;
if (dist(arr[i],arr[i-1])){
ansx.push_back(min(arr[i].x,arr[i-1].x) - 1);
ansy.push_back(min(arr[i].y,arr[i-1].y) + 1);
ansxi.push_back(arr[i].index);
ansyi.push_back(arr[i-1].index);
adj[i].push_back(i-1);
adj[i-1].push_back(i);
p[ansx.back()/2][ansy.back()/2]=true;
}
}
int j = i;
for (;i<n;++i){
if (arr[i-1].x==2)continue;
if (dist(arr[i],arr[i-1])){
ansx.push_back(min(arr[i].x,arr[i-1].x) + 1);
ansy.push_back(min(arr[i].y,arr[i-1].y) + 1);
ansxi.push_back(arr[i].index);
ansyi.push_back(arr[i-1].index);
adj[i].push_back(i-1);
adj[i-1].push_back(i);
p[ansx.back()/2][ansy.back()/2]=true;
}
}
int left =j;
for (int k =0;k<j;++k){
int right = n-1;
while(left<=right){
int mid = (left + right)>>1;
if (arr[mid].y==arr[k].y){
int first1 = min(arr[k].x,arr[mid].x) + 1;
int second1 = min(arr[k].y,arr[mid].y) + 1;
int second2=min(arr[k].y,arr[mid].y) - 1;
if (!p[first1/2][second2/2]){
ansx.push_back(first1);
ansy.push_back(second2);
ansxi.push_back(arr[k].index);
ansyi.push_back(arr[mid].index);
adj[mid].push_back(k);
adj[k].push_back(mid);
p[ansx.back()/2][ansy.back()/2]=true;
}
else if (!p[first1/2][second1/2]){
ansx.push_back(first1);
ansy.push_back(second1);
ansxi.push_back(arr[k].index);
ansyi.push_back(arr[mid].index);
adj[mid].push_back(k);
adj[k].push_back(mid);
p[ansx.back()/2][ansy.back()/2]=true;
}
break;
}
else if (arr[mid].y<arr[k].y){
left=mid+1;
}
else right = mid-1;
}
}
vector<bool>visited(n,false);
queue<int>q;
q.push(0);
while(!q.empty()){
int u =q.front();
q.pop();
visited[u]=true;
for (auto x:adj[u]){
if (!visited[x]){
q.push(x);
visited[x]=true;}
}
}
for (auto x:visited){
if (!x)return 0;
}
build(ansxi,ansyi,ansx,ansy);
return 1;
}}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
69 ms |
8084 KB |
Output is correct |
10 |
Correct |
6 ms |
1176 KB |
Output is correct |
11 |
Correct |
33 ms |
4428 KB |
Output is correct |
12 |
Correct |
9 ms |
1448 KB |
Output is correct |
13 |
Correct |
11 ms |
2248 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
248 KB |
Output is correct |
16 |
Correct |
68 ms |
8084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
69 ms |
8084 KB |
Output is correct |
10 |
Correct |
6 ms |
1176 KB |
Output is correct |
11 |
Correct |
33 ms |
4428 KB |
Output is correct |
12 |
Correct |
9 ms |
1448 KB |
Output is correct |
13 |
Correct |
11 ms |
2248 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
248 KB |
Output is correct |
16 |
Correct |
68 ms |
8084 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
242 ms |
33752 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
2 ms |
540 KB |
Output is correct |
26 |
Correct |
3 ms |
588 KB |
Output is correct |
27 |
Correct |
3 ms |
716 KB |
Output is correct |
28 |
Correct |
93 ms |
12560 KB |
Output is correct |
29 |
Correct |
135 ms |
19920 KB |
Output is correct |
30 |
Correct |
185 ms |
24888 KB |
Output is correct |
31 |
Correct |
241 ms |
33772 KB |
Output is correct |
32 |
Correct |
1 ms |
204 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
332 KB |
Output is correct |
42 |
Correct |
1 ms |
332 KB |
Output is correct |
43 |
Correct |
2 ms |
460 KB |
Output is correct |
44 |
Correct |
2 ms |
588 KB |
Output is correct |
45 |
Correct |
88 ms |
13356 KB |
Output is correct |
46 |
Correct |
137 ms |
20236 KB |
Output is correct |
47 |
Correct |
130 ms |
20224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
69 ms |
8084 KB |
Output is correct |
10 |
Correct |
6 ms |
1176 KB |
Output is correct |
11 |
Correct |
33 ms |
4428 KB |
Output is correct |
12 |
Correct |
9 ms |
1448 KB |
Output is correct |
13 |
Correct |
11 ms |
2248 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
248 KB |
Output is correct |
16 |
Correct |
68 ms |
8084 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
242 ms |
33752 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
2 ms |
540 KB |
Output is correct |
26 |
Correct |
3 ms |
588 KB |
Output is correct |
27 |
Correct |
3 ms |
716 KB |
Output is correct |
28 |
Correct |
93 ms |
12560 KB |
Output is correct |
29 |
Correct |
135 ms |
19920 KB |
Output is correct |
30 |
Correct |
185 ms |
24888 KB |
Output is correct |
31 |
Correct |
241 ms |
33772 KB |
Output is correct |
32 |
Correct |
1 ms |
204 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
332 KB |
Output is correct |
42 |
Correct |
1 ms |
332 KB |
Output is correct |
43 |
Correct |
2 ms |
460 KB |
Output is correct |
44 |
Correct |
2 ms |
588 KB |
Output is correct |
45 |
Correct |
88 ms |
13356 KB |
Output is correct |
46 |
Correct |
137 ms |
20236 KB |
Output is correct |
47 |
Correct |
130 ms |
20224 KB |
Output is correct |
48 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
49 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
69 ms |
8084 KB |
Output is correct |
10 |
Correct |
6 ms |
1176 KB |
Output is correct |
11 |
Correct |
33 ms |
4428 KB |
Output is correct |
12 |
Correct |
9 ms |
1448 KB |
Output is correct |
13 |
Correct |
11 ms |
2248 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
248 KB |
Output is correct |
16 |
Correct |
68 ms |
8084 KB |
Output is correct |
17 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
69 ms |
8084 KB |
Output is correct |
10 |
Correct |
6 ms |
1176 KB |
Output is correct |
11 |
Correct |
33 ms |
4428 KB |
Output is correct |
12 |
Correct |
9 ms |
1448 KB |
Output is correct |
13 |
Correct |
11 ms |
2248 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
248 KB |
Output is correct |
16 |
Correct |
68 ms |
8084 KB |
Output is correct |
17 |
Runtime error |
97 ms |
25948 KB |
Execution killed with signal 11 |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
69 ms |
8084 KB |
Output is correct |
10 |
Correct |
6 ms |
1176 KB |
Output is correct |
11 |
Correct |
33 ms |
4428 KB |
Output is correct |
12 |
Correct |
9 ms |
1448 KB |
Output is correct |
13 |
Correct |
11 ms |
2248 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
248 KB |
Output is correct |
16 |
Correct |
68 ms |
8084 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
242 ms |
33752 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
2 ms |
540 KB |
Output is correct |
26 |
Correct |
3 ms |
588 KB |
Output is correct |
27 |
Correct |
3 ms |
716 KB |
Output is correct |
28 |
Correct |
93 ms |
12560 KB |
Output is correct |
29 |
Correct |
135 ms |
19920 KB |
Output is correct |
30 |
Correct |
185 ms |
24888 KB |
Output is correct |
31 |
Correct |
241 ms |
33772 KB |
Output is correct |
32 |
Correct |
1 ms |
204 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
332 KB |
Output is correct |
42 |
Correct |
1 ms |
332 KB |
Output is correct |
43 |
Correct |
2 ms |
460 KB |
Output is correct |
44 |
Correct |
2 ms |
588 KB |
Output is correct |
45 |
Correct |
88 ms |
13356 KB |
Output is correct |
46 |
Correct |
137 ms |
20236 KB |
Output is correct |
47 |
Correct |
130 ms |
20224 KB |
Output is correct |
48 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
49 |
Halted |
0 ms |
0 KB |
- |