#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 2e5+10;
int N;
struct DSU{
int dsu[mxn];
DSU(){
iota(dsu,dsu+mxn,0);
}
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void onion(int a,int b){
dsu[root(a)] = root(b);
}
};
DSU dsu;
struct DINIC{
struct E{
int t,f,c;
E(int tt = 0,int cc = 0,int ff = 0):t(tt),c(cc),f(ff){}
};
vector<int> lvl,ptr;
vector<vector<int>> paths;
vector<E> e;
DINIC(int n = 0){
lvl = vector<int>(n,0);
ptr = vector<int>(n,0);
paths.resize(n);
e.clear();
}
void add_edge(int a,int b,int c,int d = 0){
paths[a].push_back(e.size());
e.push_back(E(b,c,0));
paths[b].push_back(e.size());
e.push_back(E(a,d,0));
return;
}
queue<int> q;
bool bfs(int s,int t){
fill(lvl.begin(),lvl.end(),-1);
fill(ptr.begin(),ptr.end(),0);
lvl[s] = 0;
q.push(s);
while(!q.empty()){
auto now = q.front();
q.pop();
for(int i = 0;i<paths[now].size();i++){
int eid = paths[now][i];
if(e[eid].f == e[eid].c||lvl[e[eid].t] != -1)continue;
lvl[e[eid].t] = lvl[now]+1;
q.push(e[eid].t);
}
}
return lvl[t] != -1;
}
int dfs(int now,int t,int fl){
if(now == t)return fl;
for(int &i = ptr[now];i<paths[now].size();i++){
int eid = paths[now][i];
if(e[eid].f == e[eid].c)continue;
int nxt = e[eid].t;
int re = 0;
if(re = dfs(nxt,t,min(fl,e[eid].c-e[eid].f))){
e[eid].f += re;
e[eid^1].f -= re;
return re;
}
}
return 0;
}
int flow(int s,int t){
int ans = 0;
while(bfs(s,t)){
int re = 0;
while(re = dfs(s,t,INT_MAX))ans += re;
}
return ans;
}
};
vector<int> ans[4];
void addans(int s,int e,int x,int y){
dsu.onion(s,e);
ans[0].push_back(s);
ans[1].push_back(e);
ans[2].push_back(x);
ans[3].push_back(y);
return;
}
map<pii,int> mp;
vector<pii> edges;
vector<pii> all;
DINIC g;
void check(int a,int b){
if(dsu.root(a) == dsu.root(b))return;
edges.push_back(pii(a,b));
dsu.onion(a,b);
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++){
pii pos = pii(x[i],y[i]);
if(mp.find(pii(pos.fs-2,pos.sc)) != mp.end())check(mp[pii(pos.fs-2,pos.sc)],i);
if(mp.find(pii(pos.fs+2,pos.sc)) != mp.end())check(mp[pii(pos.fs+2,pos.sc)],i);
if(mp.find(pii(pos.fs,pos.sc-2)) != mp.end())check(mp[pii(pos.fs,pos.sc-2)],i);
if(mp.find(pii(pos.fs,pos.sc+2)) != mp.end())check(mp[pii(pos.fs,pos.sc+2)],i);
mp[pos] = i;
}
if(edges.size() != N-1)return 0;
for(int i = 0;i<edges.size();i++){
auto [s,e] = edges[i];
if(x[s]>x[e])swap(s,e);
if(x[s] == x[e]&&y[s]>y[e])swap(s,e);
if(x[s] == x[e]){
all.push_back(pii(x[s]-1,(y[s]+y[e])>>1));
all.push_back(pii(x[s]+1,(y[s]+y[e])>>1));
}
else if(y[s] == y[e]){
all.push_back(pii((x[s]+x[e])>>1,y[s]-1));
all.push_back(pii((x[s]+x[e])>>1,y[s]+1));
}
}
assert(all.size()<1e6);
//cerr<<"EDGES: ";for(auto [s,e]:edges)cerr<<s<<' '<<e<<endl;
sort(all.begin(),all.end());all.erase(unique(all.begin(),all.end()),all.end());
g = DINIC(all.size()+edges.size()+2);
int s = all.size()+edges.size();int t = s+1;
for(int i = 0;i<edges.size();i++){
g.add_edge(s,i,1);
}
for(int i = 0;i<all.size();i++){
g.add_edge(edges.size()+i,t,1);
}
for(int i = 0;i<edges.size();i++){
auto [s,e] = edges[i];
if(x[s] == x[e]){
int p = lower_bound(all.begin(),all.end(),pii(x[s]-1,(y[s]+y[e])>>1))-all.begin();
g.add_edge(i,p+edges.size(),1);
p = lower_bound(all.begin(),all.end(),pii(x[s]+1,(y[s]+y[e])>>1))-all.begin();
g.add_edge(i,p+edges.size(),1);
}
else if(y[s] == y[e]){
int p = lower_bound(all.begin(),all.end(),pii((x[s]+x[e])>>1,y[s]-1))-all.begin();
g.add_edge(i,p+edges.size(),1);
p = lower_bound(all.begin(),all.end(),pii((x[s]+x[e])>>1,y[s]+1))-all.begin();
g.add_edge(i,p+edges.size(),1);
}
}
sleep(1);
int re = g.flow(s,t);
if(re != N-1)return 0;
for(int i = 0;i<edges.size();i++){
for(int j = 0;j<g.paths[i].size();j++){
int eid = g.paths[i][j];
int nxt = g.e[eid].t;
if(g.e[eid].f == 1){
addans(edges[i].fs,edges[i].sc,all[nxt-edges.size()].fs,all[nxt-edges.size()].sc);
}
}
}
build(ans[0],ans[1],ans[2],ans[3]);
return 1;
}
Compilation message
parks.cpp: In constructor 'DINIC::E::E(int, int, int)':
parks.cpp:29:11: warning: 'DINIC::E::c' will be initialized after [-Wreorder]
29 | int t,f,c;
| ^
parks.cpp:29:9: warning: 'int DINIC::E::f' [-Wreorder]
29 | int t,f,c;
| ^
parks.cpp:30:3: warning: when initialized here [-Wreorder]
30 | E(int tt = 0,int cc = 0,int ff = 0):t(tt),c(cc),f(ff){}
| ^
parks.cpp: In member function 'bool DINIC::bfs(int, int)':
parks.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i = 0;i<paths[now].size();i++){
| ~^~~~~~~~~~~~~~~~~~
parks.cpp: In member function 'int DINIC::dfs(int, int, int)':
parks.cpp:68:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int &i = ptr[now];i<paths[now].size();i++){
| ~^~~~~~~~~~~~~~~~~~
parks.cpp:73:10: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
73 | if(re = dfs(nxt,t,min(fl,e[eid].c-e[eid].f))){
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
parks.cpp: In member function 'int DINIC::flow(int, int)':
parks.cpp:85:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
85 | while(re = dfs(s,t,INT_MAX))ans += re;
| ~~~^~~~~~~~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:129:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
129 | if(edges.size() != N-1)return 0;
| ~~~~~~~~~~~~~^~~~~~
parks.cpp:130:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int i = 0;i<edges.size();i++){
| ~^~~~~~~~~~~~~
parks.cpp:148:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for(int i = 0;i<edges.size();i++){
| ~^~~~~~~~~~~~~
parks.cpp:151:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for(int i = 0;i<all.size();i++){
| ~^~~~~~~~~~~
parks.cpp:154:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for(int i = 0;i<edges.size();i++){
| ~^~~~~~~~~~~~~
parks.cpp:169:2: error: 'sleep' was not declared in this scope
169 | sleep(1);
| ^~~~~
parks.cpp:172:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for(int i = 0;i<edges.size();i++){
| ~^~~~~~~~~~~~~
parks.cpp:173:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | for(int j = 0;j<g.paths[i].size();j++){
| ~^~~~~~~~~~~~~~~~~~
