#include<bits/stdc++.h>
#include "parks.h"
#define MAXN 200007
using namespace std;
struct bench{
int from,to;
int a,b;
};
int L,M,R;
int n,dsu[MAXN],up[MAXN],down[MAXN],curr;
vector< pair<int,int> > l,m,r;
vector<bench> sol;
vector<int> A,B,C,D;
int root(int x){
if(dsu[x]==x)return x;
dsu[x]=root(dsu[x]);
return dsu[x];
}
void mergev(int x,int y){
dsu[root(x)]=root(y);
}
int construct_roads(vector<int> x,vector<int> y){
n=int(x.size());
for(int i=0;i<n;i++){
dsu[i]=i;
if(x[i]==2){
l.push_back({y[i],i});
down[y[i]]=i+1;
}
if(x[i]==4)m.push_back({y[i],i});
if(x[i]==6){
r.push_back({y[i],i});
up[y[i]]=i+1;
}
}
sort(l.begin(),l.end());
sort(m.begin(),m.end());
sort(r.begin(),r.end());
L=int(l.size()); M=int(m.size()); R=int(r.size());
for(int i=0;i<L-1;i++){
if(l[i].first+2==l[i+1].first){
mergev(l[i].second,l[i+1].second);
sol.push_back({l[i].second,l[i+1].second,1,l[i].first+1});
}
}
for(int i=0;i<R-1;i++){
if(r[i].first+2==r[i+1].first){
mergev(r[i].second,r[i+1].second);
sol.push_back({r[i].second,r[i+1].second,7,r[i].first+1});
}
}
for(int i=0;i<M-1;i++){
if(m[i].first+2==m[i+1].first){
mergev(m[i].second,m[i+1].second);
if(m[i].first%4==0)sol.push_back({m[i].second,m[i+1].second,3,m[i].first+1});
if(m[i].first%4==2)sol.push_back({m[i].second,m[i+1].second,5,m[i].first+1});
}
}
for(int i=0;i<M;i++){
if(down[m[i].first]!=0){
curr=down[m[i].first]-1;
if(root(curr)==root(m[i].second))continue;
mergev(curr,m[i].second);
if(m[i].first%4==0)sol.push_back({curr,m[i].second,3,m[i].first-1});
if(m[i].first%4==2)sol.push_back({curr,m[i].second,3,m[i].first+1});
}
}
for(int i=0;i<M;i++){
if(up[m[i].first]!=0){
curr=up[m[i].first]-1;
if(root(curr)==root(m[i].second))continue;
mergev(curr,m[i].second);
if(m[i].first%4==0)sol.push_back({m[i].second,curr,5,m[i].first+1});
if(m[i].first%4==2)sol.push_back({m[i].second,curr,5,m[i].first-1});
}
}
for(int i=0;i<n;i++){
if(root(i)!=root(0))return 0;
}
return 0;
for(int i=0;i<sol.size();i++){
A.push_back(sol[i].from);
B.push_back(sol[i].to);
C.push_back(sol[i].a);
D.push_back(sol[i].b);
}
build(A,B,C,D);
}
/*
int main(){
construct_roads({4, 4, 6, 4, 2}, {4, 6, 4, 2, 4});
}
*/
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:100:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bench>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int i=0;i<sol.size();i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Solution announced impossible, but it is possible. |
| 2 |
Halted |
0 ms |
0 KB |
- |
