#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int dsu[200010],L,R;
vector <int> g[200010],match1,match2,dist;
int prt(int n){
if (dsu[n]==n) return n;
return dsu[n]=prt(dsu[n]);
}
void unn(int u,int v){
dsu[prt(u)]=dsu[prt(v)];
}
map <pair <int,int>,int> mp;
vector <pair <int,int> > vmp;
int gt(int u,int v){
if (mp.find({u,v})==mp.end()){
mp[{u,v}]=mp.size()+1;
vmp.push_back({u,v});
}
return mp[{u,v}];
}
void bfs(){
dist.clear();
for (int i=0; i<L; i++) dist.push_back(-1);
queue <int> q;
for (int i=0; i<L; i++){
if (match1[i]==-1){
dist[i]=0;
q.push(i);
}
}
while (!q.empty()){
int tp=q.front(); q.pop();
for (int i:g[tp]){
if (match2[i]!=-1&&dist[match2[i]]==-1){
dist[match2[i]]=dist[tp]+1;
q.push(match2[i]);
}
}
}
}
int dfs(int cur){
for (int i:g[cur]){
if (match2[i]==-1){
match1[cur]=i;
match2[i]=cur;
return 1;
}
}
for (int i:g[cur]){
if (dist[match2[i]]==dist[cur]+1&&dfs(match2[i])){
match1[cur]=i;
match2[i]=cur;
return 1;
}
}
return 0;
}
bool cmp(pair <pair <int,int>,int> u,pair <pair <int,int>,int> v){
if (u.first.second!=v.first.second) return u.first.second<v.first.second;
return u.first.first<v.first.first;
}
int construct_roads(vector <int> x,vector <int> y){
int n=x.size();
pair <pair <int,int>,int> a[n];
for (int i=0; i<n; i++) a[i]={{x[i],y[i]},i};
pair <int,int> cpy[n];
for (int i=0; i<n; i++) cpy[i]={x[i],y[i]};
sort(a,a+n);
for (int i=0; i<n; i++) dsu[i]=i;
vector <int> u,v,A,B;
int cnt=0;
vmp.push_back({-1,-1});
vector <pair <int,int> > hor,ver;
for (int i=1; i<n; i++){
if (a[i-1].first.first==a[i].first.first&&a[i-1].first.second+2==a[i].first.second){
ver.push_back({a[i-1].second,a[i].second});
}
}
sort(a,a+n,cmp);
for (int i=1; i<n; i++){
if (a[i-1].first.first+2==a[i].first.first&&a[i-1].first.second==a[i].first.second){
hor.push_back({a[i-1].second,a[i].second});
}
}
int cnt=0;
for (int iters=0; iters<n; iters++){
if (hor.size()>iters&&prt(hor[iters].first)!=prt(hor[iters].second)){
u.push_back(hor[iters].first);
v.push_back(hor[iters].second);
unn(hor[iters].first,hor[iters].second);
int tp=gt(cpy[hor[iters].first].first-1,cpy[hor[iters].first].second+1);
g[cnt].push_back(tp);
tp=gt(cpy[hor[iters].first].first+1,cpy[hor[iters].first].second+1);
g[cnt].push_back(tp);
cnt++;
}
if (ver.size()>iters&&prt(ver[iters].first)!=prt(ver[iters].second)){
u.push_back(ver[iters].first);
v.push_back(ver[iters].second);
unn(ver[iters].first,ver[iters].second);
int tp=gt(cpy[ver[iters].first].first-1,cpy[ver[iters].first].second+1);
g[cnt].push_back(tp);
tp=gt(cpy[ver[iters].first].first+1,cpy[ver[iters].first].second+1);
g[cnt].push_back(tp);
cnt++;
}
if (hor.size()>iters+1&&prt(hor.back().first)!=prt(hor.back().second)){
u.push_back(hor.back().first);
v.push_back(hor.back().second);
unn(hor.back().first,hor.back().second);
int tp=gt(cpy[hor.back().first].first-1,cpy[hor.back().first].second+1);
g[cnt].push_back(tp);
tp=gt(cpy[hor.back().first].first+1,cpy[hor.back().first].second+1);
g[cnt].push_back(tp);
cnt++;
hor.pop_back();
}
if (ver.size()>iters+1&&prt(ver.back().first)!=prt(ver.back().second)){
u.push_back(ver.back().first);
v.push_back(ver.back().second);
unn(ver.back().first,ver.back().second);
int tp=gt(cpy[ver.back().first].first-1,cpy[ver.back().first].second+1);
g[cnt].push_back(tp);
tp=gt(cpy[ver.back().first].first+1,cpy[ver.back().first].second+1);
g[cnt].push_back(tp);
cnt++;
ver.pop_back();
}
}
for (int i=1; i<n; i++){
if (prt(a[i].second)!=prt(a[0].second)) return 0;
}
for (int i=0; i<n-1; i++) match1.push_back(-1);
for (int i=0; i<=vmp.size(); i++) match2.push_back(-1);
L=match1.size(); R=match2.size();
int flo=0;
while (1){
bfs();
int aug=0;
for (int i=0; i<L; i++){
if (match1[i]==-1) aug+=dfs(i);
}
if (!aug) break;
flo+=aug;
}
if (flo!=L) return 0;
for (int i=0; i<L; i++){
int tp=match1[i];
A.push_back(vmp[tp].first);
B.push_back(vmp[tp].second);
}
build(u,v,A,B);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:86:9: error: redeclaration of 'int cnt'
86 | int cnt=0;
| ^~~
parks.cpp:72:9: note: 'int cnt' previously declared here
72 | int cnt=0;
| ^~~
parks.cpp:88:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
88 | if (hor.size()>iters&&prt(hor[iters].first)!=prt(hor[iters].second)){
| ~~~~~~~~~~^~~~~~
parks.cpp:98:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
98 | if (ver.size()>iters&&prt(ver[iters].first)!=prt(ver[iters].second)){
| ~~~~~~~~~~^~~~~~
parks.cpp:108:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
108 | if (hor.size()>iters+1&&prt(hor.back().first)!=prt(hor.back().second)){
| ~~~~~~~~~~^~~~~~~~
parks.cpp:119:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
119 | if (ver.size()>iters+1&&prt(ver.back().first)!=prt(ver.back().second)){
| ~~~~~~~~~~^~~~~~~~
parks.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for (int i=0; i<=vmp.size(); i++) match2.push_back(-1);
| ~^~~~~~~~~~~~
