#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
//void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b);
struct DSU{
vector<int> par;
int tot;
DSU(int n):tot(n){
par.resize(n);
iota(par.begin(), par.end(), 0);
}
int find(int node){
if (par[node]==node) return node;
return par[node]=find(par[node]);
}
bool merge(int a, int b){
a=find(a);
b=find(b);
if (a!=b) tot--;
else return false;
par[a]=b;
return true;
}
};
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
//subtasks 4..5
DSU dsu(n);
map<pair<int,int>,int> mp;
for (int i = 0; i < n; ++i)
{
mp[{x[i],y[i]}]=i;
}
vector<int> u;
vector<int> v;
vector<int> xa(n-1,-1);
vector<int> ya(n-1,-1);
vector<set<pair<int,int>>> arr;
map<pair<int,int>,set<int>> qu;
for (int i = 0; i < n; ++i)
{
if (mp.count({x[i],y[i]-2})){
if (dsu.merge(mp[{x[i],y[i]-2}],i)){
u.push_back(mp[{x[i],y[i]-2}]);
v.push_back(i);
arr.push_back(set<pair<int,int>>());
arr.back().insert({x[i]-1,y[i]-1});
arr.back().insert({x[i]+1,y[i]-1});
qu[{x[i]-1,y[i]-1}].insert((int)u.size()-1);
qu[{x[i]+1,y[i]-1}].insert((int)u.size()-1);
}
}
}
for (int i = 0; i < n; ++i)
{
if (mp.count({x[i]-2,y[i]})){
if (dsu.merge(mp[{x[i]-2,y[i]}],i)){
u.push_back(mp[{x[i]-2,y[i]}]);
v.push_back(i);
arr.push_back(set<pair<int,int>>());
arr.back().insert({x[i]-1,y[i]-1});
arr.back().insert({x[i]-1,y[i]+1});
qu[{x[i]-1,y[i]-1}].insert((int)u.size()-1);
qu[{x[i]-1,y[i]+1}].insert((int)u.size()-1);
}
}
}
if (dsu.tot!=1) return 0;
vector<pair<int,int>> iki;
queue<pair<int,int>> que;
int kal = n-1;
for (auto it : qu){
if (it.second.size()==1) que.push(it.first);
else iki.push_back(it.first);
}
set<pair<int,int>> lmao;
while (kal>0){
while (que.size() && (qu[que.front()].size()<1 || lmao.find(que.front())!=lmao.end())) que.pop();
if (!que.size()){
while (iki.size() && qu[iki.back()].size()<2) iki.pop_back();
while (iki.size()>1){
int it = *qu[iki.back()].begin();
arr[it].erase(iki.back());
qu[iki.back()].erase(it);
}
que.push(iki.back());
iki.pop_back();
else return 0;
}
if (!que.size()) return 0;
pair<int,int> pr = que.front();
que.pop();
int it = *qu[pr].begin();
if (xa[it]!=-1) continue;
kal--;
lmao.insert(pr);
xa[it]=pr.first, ya[it]=pr.second;
for (auto it2 : arr[it]){
if (qu[it2].find(it)!=qu[it2].end()) qu[it2].erase(it);
if (qu[it2].size()==1) {
que.push(it2);
}
}
while (arr[it].size()) arr[it].erase(arr[it].begin());
}
build(u,v,xa,ya);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:90:4: error: expected '}' before 'else'
90 | else return 0;
| ^~~~
parks.cpp:81:19: note: to match this '{'
81 | if (!que.size()){
| ^
parks.cpp:96:19: error: continue statement not within a loop
96 | if (xa[it]!=-1) continue;
| ^~~~~~~~
parks.cpp: At global scope:
parks.cpp:108:7: error: expected constructor, destructor, or type conversion before '(' token
108 | build(u,v,xa,ya);
| ^
parks.cpp:109:2: error: expected unqualified-id before 'return'
109 | return 1;
| ^~~~~~
parks.cpp:110:1: error: expected declaration before '}' token
110 | }
| ^
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:30:11: warning: control reaches end of non-void function [-Wreturn-type]
30 | DSU dsu(n);
| ^
