#include<bits/stdc++.h>
#include "parks.h"
#define mk make_pair
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,PI,cc,dd,cnt,CNT,bo[1000009];
pair <int, int> p[200009],P[1000009];
vector <pair <int, int> > X[200009],Y[200009];
vector <int> U,V,A,B;
map <int, int> m[200009],M[200009];
set <pair <int, pair <int, int> > > s;
set <pair <int, pair <int, int> > >::iterator it;
vector <int> v[1000009];
pair <int, int> id[1000009];
void DONE(){
s.erase(s.lower_bound(make_pair(M[cc][dd],make_pair(cc,dd))));
M[cc][dd]--;
s.insert(mk(M[cc][dd],mk(cc,dd)));
}
void chk(int q, int w){
if(m[q][w]==0) return;
i=m[q][w];c=P[i].first;d=P[i].second;
U.push_back(c);V.push_back(d);A.push_back(zx);B.push_back(xc);
if(p[c].first==p[d].first){
cc=p[c].first-1;dd=(p[c].second+p[d].second)/2;
DONE();
cc=p[c].first+1;dd=(p[c].second+p[d].second)/2;
DONE();
}else{
cc=(p[c].first+p[d].first)/2;dd=p[c].second-1;
DONE();
cc=(p[c].first+p[d].first)/2;dd=p[c].second+1;
DONE();
}
m[q][w]=0;
}
void DOO(){
if(M[cc][dd]!=0){
s.erase(s.lower_bound(make_pair(M[cc][dd],make_pair(cc,dd))));
}
M[cc][dd]++;
s.insert(make_pair(M[cc][dd],make_pair(cc,dd)));
}
void CHK(int q, int w){
if(m[q][w]==0) return;
v[m[q][w]].push_back(cnt);
v[cnt].push_back(m[q][w]);
}
void dfs(int q, int w){
bo[q]=1;
if(q<=PI){
c=P[q].first;d=P[q].second;
U.push_back(c);V.push_back(d);A.push_back(id[w].first);B.push_back(id[w].second);
}
for(vector <int>::iterator tt=v[q].begin(); tt!=v[q].end(); tt++){
if(bo[(*tt)]==1) continue;
dfs((*tt),q);
}
}
int msh[200009],zm[200009];
int fnd(int q){
if(msh[q]==0) return q; else return msh[q]=fnd(msh[q]);
}
void mrg(int q, int w){
q=fnd(q);w=fnd(w);if(q==w) return;if(zm[q]<zm[q]) swap(q,w);
msh[w]=q;if(zm[q]==zm[w]) zm[q]++;
}
bool check(){
set <int> st;
for(i=1; i<=PI; i++){
mrg(P[i].first,P[i].second);
}
for(i=1; i<=a; i++) st.insert(fnd(i));
if(st.size()==1) return 1; else return 0;
}
int construct_roads(std::vector<int> Xx, std::vector<int> Yy) {
a=Xx.size();
for(i=1; i<=a; i++){
p[i].first=Xx[i-1];p[i].second=Yy[i-1];
}
for(i=1; i<=a; i++){
X[p[i].first].push_back(make_pair(p[i].second,i));
Y[p[i].second].push_back(make_pair(p[i].first,i));
}
for(i=2; i<=200000; i+=2){
sort(X[i].begin(),X[i].end());
sort(Y[i].begin(),Y[i].end());
e=X[i].size();
for(j=0; j<e-1; j++){
if(X[i][j].first+2<X[i][j+1].first) continue;
//cout<<i<<" "<<X[i][j].first<<" X "<<X[i][j+1].first<<endl;
c=X[i][j].second;d=X[i][j+1].second;
PI++;
P[PI].first=c;P[PI].second=d;
}
e=Y[i].size();
for(j=0; j<e-1; j++){
if(Y[i][j].first+2<Y[i][j+1].first) continue;
//cout<<i<<" "<<Y[i][j].first<<" Y "<<Y[i][j+1].first<<endl;
c=Y[i][j].second;d=Y[i][j+1].second;
PI++;
P[PI].first=c;P[PI].second=d;
}
}
if(check()==0){
return 0;
}
/*cout<<PI<<endl;
for(i=1; i<=PI; i++){
c=P[i].first;d=P[i].second;
cout<<p[c].first<<" "<<p[c].second<<" "<<p[d].first<<" "<<p[d].second<<endl;
}
exit(0);*/
for(i=1; i<=PI; i++){
c=P[i].first;d=P[i].second;
m[(p[c].first+p[d].first)/2][(p[c].second+p[d].second)/2]=i;
if(p[c].first==p[d].first){
cc=p[c].first-1;dd=(p[c].second+p[d].second)/2;
DOO();
cc=p[c].first+1;dd=(p[c].second+p[d].second)/2;
DOO();
}else{
cc=(p[c].first+p[d].first)/2;dd=p[c].second-1;
DOO();
cc=(p[c].first+p[d].first)/2;dd=p[c].second+1;
DOO();
}
}
while(s.size()){
it=s.begin();
if((*it).first>=2) break;
if((*it).first==0){
s.erase(it);continue;
}
int ca=(*it).second.first,da=(*it).second.second;
zx=ca;xc=da;
chk(ca-1,da);chk(ca+1,da);chk(ca,da-1);chk(ca,da+1);
}
/*cout<<U.size()<<endl;
for(i=0; i<U.size(); i++){
cout<<U[i]<<" "<<V[i]<<" "<<A[i]<<" "<<B[i]<<endl;
}
exit(0);*/
cnt=PI+1;
for(it=s.begin(); it!=s.end(); it++){
cnt++;id[cnt]=(*it).second;
CHK((*it).second.first-1,(*it).second.second);
CHK((*it).second.first+1,(*it).second.second);
CHK((*it).second.first,(*it).second.second-1);
CHK((*it).second.first,(*it).second.second+1);
}
for(i=PI+1; i<=cnt; i++){
if(bo[i]!=0) continue;
dfs(i,0);
}
build(U,V,A,B);
return 1;
}
Compilation message
parks.cpp: In function 'void mrg(int, int)':
parks.cpp:67:44: warning: self-comparison always evaluates to false [-Wtautological-compare]
67 | q=fnd(q);w=fnd(w);if(q==w) return;if(zm[q]<zm[q]) swap(q,w);
| ~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
51924 KB |
Output is correct |
| 2 |
Incorrect |
28 ms |
51908 KB |
Integer parameter [name=v[j]] equals to 2, violates the range [0, 1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
51924 KB |
Output is correct |
| 2 |
Incorrect |
28 ms |
51908 KB |
Integer parameter [name=v[j]] equals to 2, violates the range [0, 1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
51924 KB |
Output is correct |
| 2 |
Incorrect |
28 ms |
51908 KB |
Integer parameter [name=v[j]] equals to 2, violates the range [0, 1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
51924 KB |
Output is correct |
| 2 |
Incorrect |
28 ms |
51908 KB |
Integer parameter [name=v[j]] equals to 2, violates the range [0, 1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
51924 KB |
Output is correct |
| 2 |
Incorrect |
28 ms |
51908 KB |
Integer parameter [name=v[j]] equals to 2, violates the range [0, 1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
51924 KB |
Output is correct |
| 2 |
Incorrect |
28 ms |
51908 KB |
Integer parameter [name=v[j]] equals to 2, violates the range [0, 1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
