#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vii vector<vi>
#define pi pair<int,int>
#define vp vector<pi>
vi d;
vi h;
int parent(int x){
if(d[x]==x)return x;
return d[x]=parent(d[x]);
}
void connect(int a, int b){
a=parent(a);
b=parent(b);
if(h[a]<h[b])swap(a,b);
if(h[a]==h[b])h[a]++;
d[b]=a;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
//bsmllah
int n=x.size();
d.resize(n);for(int i=0;i<n;i++)d[i]=i;
h.resize(n);
vi u;
vi v;
vi a;
vi b;
map<pi,int>f;
for(int i=0;i<n;i++){
f.insert(make_pair(pi(x[i],y[i]),i));
}
for(int i=0;i<n;i++){
auto itr=f.find(pi(x[i]+2,y[i]));
if(itr!=f.end()){
u.push_back(i);
v.push_back(itr->second);
a.push_back(x[i]+1);
b.push_back(y[i]+1);
connect(i,itr->second);
}
itr=f.find(pi(x[i],y[i]+2));
if(itr!=f.end()){
u.push_back(i);
v.push_back(itr->second);
a.push_back(x[i]+x[i]-3);
b.push_back(y[i]+1);
connect(i,itr->second);
}
}
for(int i=0;i<n;i++){
if(parent(d[i])!=parent(d[0]))return 0;
}
build(u,v,a,b);
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 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 |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
240 KB |
Output is correct |
9 |
Correct |
98 ms |
13912 KB |
Output is correct |
10 |
Correct |
7 ms |
1876 KB |
Output is correct |
11 |
Correct |
38 ms |
7756 KB |
Output is correct |
12 |
Correct |
10 ms |
2644 KB |
Output is correct |
13 |
Correct |
21 ms |
5168 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
98 ms |
13976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 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 |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
240 KB |
Output is correct |
9 |
Correct |
98 ms |
13912 KB |
Output is correct |
10 |
Correct |
7 ms |
1876 KB |
Output is correct |
11 |
Correct |
38 ms |
7756 KB |
Output is correct |
12 |
Correct |
10 ms |
2644 KB |
Output is correct |
13 |
Correct |
21 ms |
5168 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
98 ms |
13976 KB |
Output is correct |
17 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
321 ms |
32016 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
2 ms |
848 KB |
Output is correct |
27 |
Correct |
2 ms |
852 KB |
Output is correct |
28 |
Correct |
102 ms |
13356 KB |
Output is correct |
29 |
Correct |
159 ms |
19452 KB |
Output is correct |
30 |
Correct |
259 ms |
25828 KB |
Output is correct |
31 |
Correct |
322 ms |
32120 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
0 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
1 ms |
212 KB |
Output is correct |
43 |
Correct |
2 ms |
592 KB |
Output is correct |
44 |
Correct |
2 ms |
596 KB |
Output is correct |
45 |
Correct |
114 ms |
14060 KB |
Output is correct |
46 |
Correct |
184 ms |
20012 KB |
Output is correct |
47 |
Correct |
195 ms |
20004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 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 |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
240 KB |
Output is correct |
9 |
Correct |
98 ms |
13912 KB |
Output is correct |
10 |
Correct |
7 ms |
1876 KB |
Output is correct |
11 |
Correct |
38 ms |
7756 KB |
Output is correct |
12 |
Correct |
10 ms |
2644 KB |
Output is correct |
13 |
Correct |
21 ms |
5168 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
98 ms |
13976 KB |
Output is correct |
17 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
321 ms |
32016 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
2 ms |
848 KB |
Output is correct |
27 |
Correct |
2 ms |
852 KB |
Output is correct |
28 |
Correct |
102 ms |
13356 KB |
Output is correct |
29 |
Correct |
159 ms |
19452 KB |
Output is correct |
30 |
Correct |
259 ms |
25828 KB |
Output is correct |
31 |
Correct |
322 ms |
32120 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
0 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
1 ms |
212 KB |
Output is correct |
43 |
Correct |
2 ms |
592 KB |
Output is correct |
44 |
Correct |
2 ms |
596 KB |
Output is correct |
45 |
Correct |
114 ms |
14060 KB |
Output is correct |
46 |
Correct |
184 ms |
20012 KB |
Output is correct |
47 |
Correct |
195 ms |
20004 KB |
Output is correct |
48 |
Incorrect |
1 ms |
212 KB |
Tree (a[0], b[0]) = (9, 3) is not adjacent to edge between u[0]=0 @(6, 2) and v[0]=2 @(6, 4) |
49 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 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 |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
240 KB |
Output is correct |
9 |
Correct |
98 ms |
13912 KB |
Output is correct |
10 |
Correct |
7 ms |
1876 KB |
Output is correct |
11 |
Correct |
38 ms |
7756 KB |
Output is correct |
12 |
Correct |
10 ms |
2644 KB |
Output is correct |
13 |
Correct |
21 ms |
5168 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
98 ms |
13976 KB |
Output is correct |
17 |
Incorrect |
1 ms |
212 KB |
Tree (a[0], b[0]) = (399997, 3) is not adjacent to edge between u[0]=0 @(200000, 2) and v[0]=1 @(200000, 4) |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 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 |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
240 KB |
Output is correct |
9 |
Correct |
98 ms |
13912 KB |
Output is correct |
10 |
Correct |
7 ms |
1876 KB |
Output is correct |
11 |
Correct |
38 ms |
7756 KB |
Output is correct |
12 |
Correct |
10 ms |
2644 KB |
Output is correct |
13 |
Correct |
21 ms |
5168 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
98 ms |
13976 KB |
Output is correct |
17 |
Incorrect |
285 ms |
27280 KB |
Tree (a[1], b[1]) = (200001, 52499) is not adjacent to edge between u[1]=1 @(100002, 52498) and v[1]=117727 @(100002, 52500) |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 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 |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
240 KB |
Output is correct |
9 |
Correct |
98 ms |
13912 KB |
Output is correct |
10 |
Correct |
7 ms |
1876 KB |
Output is correct |
11 |
Correct |
38 ms |
7756 KB |
Output is correct |
12 |
Correct |
10 ms |
2644 KB |
Output is correct |
13 |
Correct |
21 ms |
5168 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
98 ms |
13976 KB |
Output is correct |
17 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
321 ms |
32016 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
2 ms |
848 KB |
Output is correct |
27 |
Correct |
2 ms |
852 KB |
Output is correct |
28 |
Correct |
102 ms |
13356 KB |
Output is correct |
29 |
Correct |
159 ms |
19452 KB |
Output is correct |
30 |
Correct |
259 ms |
25828 KB |
Output is correct |
31 |
Correct |
322 ms |
32120 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
0 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
212 KB |
Output is correct |
42 |
Correct |
1 ms |
212 KB |
Output is correct |
43 |
Correct |
2 ms |
592 KB |
Output is correct |
44 |
Correct |
2 ms |
596 KB |
Output is correct |
45 |
Correct |
114 ms |
14060 KB |
Output is correct |
46 |
Correct |
184 ms |
20012 KB |
Output is correct |
47 |
Correct |
195 ms |
20004 KB |
Output is correct |
48 |
Incorrect |
1 ms |
212 KB |
Tree (a[0], b[0]) = (9, 3) is not adjacent to edge between u[0]=0 @(6, 2) and v[0]=2 @(6, 4) |
49 |
Halted |
0 ms |
0 KB |
- |