#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
int n,x[mxn],y[mxn],p[mxn],sz[mxn];
int ax[4]={1,1,-1,-1};
int ay[4]={-1,1,1,-1};
vector<pii>vt;
map<pii,int>mp;
int fnd(int u){
if(p[u]==u) return u;
return p[u]=fnd(p[u]);
}
void Union(int u,int v){
u=fnd(u);
v=fnd(v);
if(u!=v){
if(sz[u]>sz[v]) swap(u,v);
sz[u]+=sz[v];
p[v]=u;
}
}
int construct_roads(vector<int> xx, vector<int> yy) {
n=xx.size();
if(n==1){
build({},{},{},{});
return 1;
}
for(int i=0;i<n;i++){
vt.pb({xx[i],yy[i]});
mp[{xx[i],yy[i]}]=i+1;
x[i+1]=xx[i];
y[i+1]=yy[i];
}
//for(int i=1;i<=n;i++){
//if(!mp[{x[i],y[i]+2}]&&!mp[{x[i],y[i]-2}]&&!mp[{x[i]+2,y[i]}]&&!mp[{x[i]-2,y[i]}]) return 0;
//}
sort(all(vt));
//for(int i=1;i<n;i++){
//if(abs(vt[i].F-vt[i-1].F)>2||abs(vt[i].S-vt[i-1].S)>2) return 0;
//}
set<pii>st;
for(int i=1;i<=n;i++){
st.insert({x[i]-1,y[i]-1});
st.insert({x[i]+1,y[i]-1});
st.insert({x[i]-1,y[i]+1});
st.insert({x[i]+1,y[i]+1});
}
for(int i=1;i<=n;i++){
p[i]=i;
sz[i]=1;
}
vector<int>idxl,idxr,posl,posr;
int cnt=n-1;
int say=10;
while(cnt&&say--){
for(auto it=st.begin();it!=st.end();it++){
int l=it->F;
int r=it->S;
set<int>dif;
vector<int>idx;
//cout<<"OK"<<endl;
for(int i=0;i<4;i++){
int u=l+ax[i],v=r+ay[i];
int node=mp[{u,v}];
if(node>0&&!dif.count(fnd(node))){
dif.insert(fnd(node));
idx.pb(node);
}
}
//cout<<dif.size()<<endl;
if(dif.size()==1||dif.size()>2) continue;
int q=-1,q2=1;
for(int i=0;i<idx.size();i++){
for(int j=i+1;j<idx.size();j++){
if(abs(x[idx[i]]-x[idx[j]])+abs(y[idx[i]]-y[idx[j]])==2){
q=i,
q2=j;
break;
}
}
}
if(q==-1) continue;
idxl.pb(idx[q]-1);
idxr.pb(idx[q2]-1);
//cout<<idx[0]<<' '<<idx[1]<<endl;
posl.pb(l);
posr.pb(r);
Union(idx[q],idx[q2]);
cnt--;
}
//cnt--;
}
say=10;
while(cnt&&st.size()){
for(auto it=st.begin();it!=st.end();it++){
int l=it->F;
int r=it->S;
set<int>dif;
vector<int>idx;
//cout<<"OK"<<endl;
for(int i=0;i<4;i++){
int u=l+ax[i],v=r+ay[i];
int node=mp[{u,v}];
if(node>0&&!dif.count(fnd(node))){
dif.insert(fnd(node));
idx.pb(node);
}
}
//cout<<dif.size()<<endl;
if(dif.size()==1){
st.erase(it++);
continue;
}
int q=-1,q2=1;
for(int i=0;i<idx.size();i++){
for(int j=i+1;j<idx.size();j++){
if(abs(x[idx[i]]-x[idx[j]])+abs(y[idx[i]]-y[idx[j]])==2){
q=i,
q2=j;
break;
}
}
}
if(q==-1){
st.erase(it++);
continue;
}
idxl.pb(idx[q]-1);
idxr.pb(idx[q2]-1);
//cout<<idx[0]<<' '<<idx[1]<<endl;
posl.pb(l);
posr.pb(r);
Union(idx[q],idx[q2]);
cnt--;
if(dif.size()==2){
st.erase(it++);
}
}
//cnt--;
}
if(cnt) return 0;
build(idxl,idxr,posl,posr);
return 1;
}
/*
cd "c:\Users\User\Desktop\parks (4)\cpp\" ; if ($?) { g++ parks.cpp grader.cpp -o parks } ; if ($?) { .\a.exe }
5
4 4
4 6
6 4
4 2
2 4
*/
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:85:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=0;i<idx.size();i++){
| ~^~~~~~~~~~~
parks.cpp:86:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int j=i+1;j<idx.size();j++){
| ~^~~~~~~~~~~
parks.cpp:127:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i=0;i<idx.size();i++){
| ~^~~~~~~~~~~
parks.cpp:128:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int j=i+1;j<idx.size();j++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
3584 ms |
212 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
3584 ms |
212 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
3584 ms |
212 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
3584 ms |
212 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
3584 ms |
212 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
3584 ms |
212 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
