#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
//void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b);
struct DSU{
vector<int> par;
int tot;
DSU(int n):tot(n){
par.resize(n);
iota(par.begin(), par.end(), 0);
}
int find(int node){
if (par[node]==node) return node;
return par[node]=find(par[node]);
}
bool merge(int a, int b){
a=find(a);
b=find(b);
if (a!=b) tot--;
else return false;
par[a]=b;
return true;
}
};
int construct_roads(vector<int> x, vector<int> y) {
bool subtask2 = true;
bool subtask3 = true;
bool subtask5 = true;
int n = x.size();
map<pair<int,int>,int> mp;
for (int i = 0; i < n; i++){
mp[{x[i],y[i]}]=i;
if (x[i]<2 || x[i]>4) subtask2=false;
if (x[i]<2 || x[i]>6) subtask3=false;
}
if (subtask2){
DSU dsu(n);
vector<int> u;
vector<int> v;
vector<int> xa;
vector<int> ya;
for (int i = 0; i < n; ++i)
{
if (mp.count({x[i]-2,y[i]})){
if (dsu.merge(i,mp[{x[i]-2,y[i]}])){
u.push_back(mp[{x[i]-2,y[i]}]);
v.push_back(i);
xa.push_back(x[i]-1);
ya.push_back(y[i]-1);
}
}
if (mp.count({x[i],y[i]-2})){
if (dsu.merge(i,mp[{x[i],y[i]-2}])){
u.push_back(mp[{x[i],y[i]-2}]);
v.push_back(i);
if (x[i]==2) xa.push_back(x[i]-1);
else xa.push_back(x[i]+1);
ya.push_back(y[i]-1);
}
}
}
if (dsu.tot==1) return build(u,v,xa,ya),1;
return 0;
}
else return cout<<"WA"<<endl,0;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:27:10: warning: variable 'subtask3' set but not used [-Wunused-but-set-variable]
27 | bool subtask3 = true;
| ^~~~~~~~
parks.cpp:28:10: warning: unused variable 'subtask5' [-Wunused-variable]
28 | bool subtask5 = true;
| ^~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
432 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
95 ms |
14228 KB |
Output is correct |
10 |
Correct |
5 ms |
1880 KB |
Output is correct |
11 |
Correct |
32 ms |
7940 KB |
Output is correct |
12 |
Correct |
8 ms |
2652 KB |
Output is correct |
13 |
Correct |
20 ms |
5336 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
89 ms |
14268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
432 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
95 ms |
14228 KB |
Output is correct |
10 |
Correct |
5 ms |
1880 KB |
Output is correct |
11 |
Correct |
32 ms |
7940 KB |
Output is correct |
12 |
Correct |
8 ms |
2652 KB |
Output is correct |
13 |
Correct |
20 ms |
5336 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
89 ms |
14268 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
258 ms |
26408 KB |
Output is correct |
24 |
Correct |
0 ms |
344 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
2 ms |
604 KB |
Output is correct |
27 |
Correct |
2 ms |
604 KB |
Output is correct |
28 |
Correct |
87 ms |
10844 KB |
Output is correct |
29 |
Correct |
133 ms |
15936 KB |
Output is correct |
30 |
Correct |
183 ms |
21164 KB |
Output is correct |
31 |
Correct |
256 ms |
26412 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 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 |
604 KB |
Output is correct |
44 |
Correct |
2 ms |
604 KB |
Output is correct |
45 |
Correct |
99 ms |
13332 KB |
Output is correct |
46 |
Correct |
154 ms |
19112 KB |
Output is correct |
47 |
Correct |
153 ms |
19180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
432 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
95 ms |
14228 KB |
Output is correct |
10 |
Correct |
5 ms |
1880 KB |
Output is correct |
11 |
Correct |
32 ms |
7940 KB |
Output is correct |
12 |
Correct |
8 ms |
2652 KB |
Output is correct |
13 |
Correct |
20 ms |
5336 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
89 ms |
14268 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
258 ms |
26408 KB |
Output is correct |
24 |
Correct |
0 ms |
344 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
2 ms |
604 KB |
Output is correct |
27 |
Correct |
2 ms |
604 KB |
Output is correct |
28 |
Correct |
87 ms |
10844 KB |
Output is correct |
29 |
Correct |
133 ms |
15936 KB |
Output is correct |
30 |
Correct |
183 ms |
21164 KB |
Output is correct |
31 |
Correct |
256 ms |
26412 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 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 |
604 KB |
Output is correct |
44 |
Correct |
2 ms |
604 KB |
Output is correct |
45 |
Correct |
99 ms |
13332 KB |
Output is correct |
46 |
Correct |
154 ms |
19112 KB |
Output is correct |
47 |
Correct |
153 ms |
19180 KB |
Output is correct |
48 |
Incorrect |
0 ms |
344 KB |
Possible tampering with the output |
49 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
432 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
95 ms |
14228 KB |
Output is correct |
10 |
Correct |
5 ms |
1880 KB |
Output is correct |
11 |
Correct |
32 ms |
7940 KB |
Output is correct |
12 |
Correct |
8 ms |
2652 KB |
Output is correct |
13 |
Correct |
20 ms |
5336 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
89 ms |
14268 KB |
Output is correct |
17 |
Incorrect |
0 ms |
432 KB |
Possible tampering with the output |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
432 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
95 ms |
14228 KB |
Output is correct |
10 |
Correct |
5 ms |
1880 KB |
Output is correct |
11 |
Correct |
32 ms |
7940 KB |
Output is correct |
12 |
Correct |
8 ms |
2652 KB |
Output is correct |
13 |
Correct |
20 ms |
5336 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
89 ms |
14268 KB |
Output is correct |
17 |
Incorrect |
84 ms |
18108 KB |
Possible tampering with the output |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
432 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
95 ms |
14228 KB |
Output is correct |
10 |
Correct |
5 ms |
1880 KB |
Output is correct |
11 |
Correct |
32 ms |
7940 KB |
Output is correct |
12 |
Correct |
8 ms |
2652 KB |
Output is correct |
13 |
Correct |
20 ms |
5336 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
89 ms |
14268 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
258 ms |
26408 KB |
Output is correct |
24 |
Correct |
0 ms |
344 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
2 ms |
604 KB |
Output is correct |
27 |
Correct |
2 ms |
604 KB |
Output is correct |
28 |
Correct |
87 ms |
10844 KB |
Output is correct |
29 |
Correct |
133 ms |
15936 KB |
Output is correct |
30 |
Correct |
183 ms |
21164 KB |
Output is correct |
31 |
Correct |
256 ms |
26412 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 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 |
604 KB |
Output is correct |
44 |
Correct |
2 ms |
604 KB |
Output is correct |
45 |
Correct |
99 ms |
13332 KB |
Output is correct |
46 |
Correct |
154 ms |
19112 KB |
Output is correct |
47 |
Correct |
153 ms |
19180 KB |
Output is correct |
48 |
Incorrect |
0 ms |
344 KB |
Possible tampering with the output |
49 |
Halted |
0 ms |
0 KB |
- |