#include "parks.h"
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
vector <int> v[200005],u2,v2,a2,b2;
vector <pair<pair<int,int>,int> > v1;
bool comp(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b) {
return a.first.second<b.first.second;
}
int bio[200005],cnt;
void dfs(int x) {
bio[x]=1;
cnt+=1;
for(int i=0;i<v[x].size();i++) {
if(!bio[v[x][i]]) dfs(v[x][i]);
}
}
int construct_roads(std::vector<int> x,std::vector<int> y) {
int n=x.size();
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));
}
sort(v1.begin(),v1.end(),comp);
for(int i=0;i<v1.size();i++) {
for(int j=i+1;j<v1.size() && j-i<=3;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);
}
}
}
dfs(0);
//cout << cnt << "\n";
if(cnt<n) return 0;
for(int i=0;i<u2.size();i++) {
if(x[u2[i]]==x[v2[i]]) {
a2.push_back(x[u2[i]]-1);
b2.push_back(3);
}
else if(y[u2[i]]==4) {
a2.push_back(x[v2[i]]-1);
b2.push_back(5);
}
else {
a2.push_back(x[v2[i]]-1);
b2.push_back(1);
}
}
/*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:15:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(int i=0;i<v[x].size();i++) {
| ~^~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:29: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]
29 | for(int i=0;i<v1.size();i++) {
| ~^~~~~~~~~~
parks.cpp:30: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]
30 | for(int j=i+1;j<v1.size() && j-i<=3;j++) {
| ~^~~~~~~~~~
parks.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=0;i<u2.size();i++) {
| ~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Incorrect |
4 ms |
4940 KB |
Tree (a[1], b[1]) = (1, 3) is not adjacent to edge between u[1]=1 @(2, 4) and v[1]=2 @(2, 6) |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Incorrect |
4 ms |
4940 KB |
Tree (a[1], b[1]) = (1, 3) is not adjacent to edge between u[1]=1 @(2, 4) and v[1]=2 @(2, 6) |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Incorrect |
4 ms |
4940 KB |
Tree (a[1], b[1]) = (1, 3) is not adjacent to edge between u[1]=1 @(2, 4) and v[1]=2 @(2, 6) |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Incorrect |
4 ms |
4940 KB |
Tree (a[1], b[1]) = (1, 3) is not adjacent to edge between u[1]=1 @(2, 4) and v[1]=2 @(2, 6) |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Incorrect |
4 ms |
4940 KB |
Tree (a[1], b[1]) = (1, 3) is not adjacent to edge between u[1]=1 @(2, 4) and v[1]=2 @(2, 6) |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Incorrect |
4 ms |
4940 KB |
Tree (a[1], b[1]) = (1, 3) is not adjacent to edge between u[1]=1 @(2, 4) and v[1]=2 @(2, 6) |
5 |
Halted |
0 ms |
0 KB |
- |