#include "parks.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+5;
int a[N],b[N],par[N],sz[N],n;
vector<int> c[N];
vector<int> adj[N];
bool cmp(int x,int y){
return a[x]<a[y];
}
int getpar(int x){
if (x==par[x]) return x;
return par[x]=getpar(par[x]);
}
void link(int x,int y){
x=getpar(x);
y=getpar(y);
if (x==y) return;
if (sz[x]>sz[y]) swap(x,y);
sz[y]+=sz[x];
par[x]=y;
return;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
n=x.size();
for (int i=0;i<n;i++){
par[i]=i;
sz[i]=1;
a[i]=x[i];
b[i]=y[i];
c[y[i]].pb(i);
}
vector<int> U,V,s;
for (int i=0;i<N;i+=2) sort(c[i].begin(),c[i].end(),cmp);
for (int i=0;i<N;i+=2){
for (int j=0;j<int(c[i].size())-1;j++){
if (a[c[i][j+1]]-a[c[i][j]]==2){
link(c[i][j],c[i][j+1]);
U.pb(c[i][j]);
V.pb(c[i][j+1]);
s.pb(0);
adj[c[i][j]].pb(U.size()-1);
adj[c[i][j+1]].pb(U.size()-1);
}
}
}
for (int i=N-1;i>=0;i--){
for (int j=0;j<int(c[i].size());j++){
int l=0,r=int(c[i+2].size())-1,mid,idx=-1;
while (l<=r){
mid=(l+r)/2;
if (a[c[i+2][mid]]==a[c[i][j]]){
idx=mid;
break;
}
if (a[c[i+2][mid]]>a[c[i][j]]) r=mid-1;
else l=mid+1;
}
if (idx!=-1){
link(c[i][j],c[i+2][idx]);
V.pb(c[i][j]);
U.pb(c[i+2][idx]);
s.pb(2);
adj[c[i][j]].pb(U.size()-1);
adj[c[i+2][idx]].pb(U.size()-1);
}
}
}
if (sz[getpar(0)]!=n) return 0;
for (int i=0;i<U.size();i++){
if (s[i]!=2) continue;
int l=2,r=2,idxl=-1,idxr=-1;
for (auto u:adj[V[i]]){
int to=U[u];
if (to==V[i]) to=V[u];
if (a[to]==a[V[i]]) continue;
if (a[to]>a[V[i]] && s[u]==0) r=0,idxr=u;
if (a[to]<a[V[i]] && s[u]==0) l=0,idxl=u;
}
cout<<l<<' '<<r<<endl;
for (auto u:adj[U[i]]){
int to=U[u];
if (to==U[i]) to=V[u];
if (a[to]==a[U[i]]) continue;
if (a[to]>a[U[i]] && s[u]==1) r=1,idxr=u;
if (a[to]<a[U[i]] && s[u]==1) l=1,idxl=u;
}
cout<<U[i]<<' '<<V[i]<<' '<<l<<' '<<r<<' '<<idxl<<' '<<idxr<<endl;
if (l==2 || r==2){
//cout<<"c1"<<endl;
if (r==2) s[i]=3;
continue;
}
if (l==1){
s[idxr]=1;
s[i]=3;
//cout<<"c2"<<endl;
continue;
}
if (r==1){
//cout<<"c3"<<endl;
s[idxl]=1;
continue;
}
s[idxr]=1;
s[i]=3;
}
vector<int> d,e;
for (int i=0;i<U.size();i++){
if (s[i]==0){
d.pb(a[U[i]]+1);
e.pb(b[U[i]]+1);
continue;
}
if (s[i]==1){
d.pb(a[U[i]]+1);
e.pb(b[U[i]]-1);
continue;
}
if (s[i]==2){
d.pb(a[U[i]]-1);
e.pb(b[U[i]]-1);
continue;
}
d.pb(a[U[i]]+1);
e.pb(b[U[i]]-1);
continue;
}
build(U,V,d,e);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i=0;i<U.size();i++){
| ~^~~~~~~~~
parks.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for (int i=0;i<U.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12892 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12892 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12892 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12892 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12892 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12892 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
