#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 2e5 + 10;
int n, x[maxn], y[maxn], dsu[maxn], cntedge[maxn], cntdot[maxn<<1], a[maxn], b[maxn];
vector<int> numx[maxn], numy[maxn];
vector<pair<pii,int>> p;
vector<pii> edge;
vector<pii> dot;
vector<int> gedge[maxn], gdot[maxn<<1];
bool markedge[maxn];
bool markdot[maxn];
set<pii> st;
int getdsu(int v){
return (dsu[v] < 0? v: dsu[v] = getdsu(dsu[v]));
}
bool merge(int u, int v){
if ((u = getdsu(u)) == (v = getdsu(v))) return false;
dsu[u] = v;
return true;
}
pair<pii,pii> getdot(int u, int v){
//debug(x[u], x[v], y[u], y[v]);
if (x[u] == x[v]) return {{x[u]-1, (y[u]+y[v])/2}, {x[u]+1, (y[u]+y[v])/2}};
return {{(x[u]+x[v])/2, y[u]-1}, {(x[u]+x[v])/2, y[u]+1}};
}
void rmdot(int idx){
for (auto x: gdot[idx]){
if (!markedge[x]){
st.erase({cntedge[x], x});
cntedge[x]--;
st.insert({cntedge[x], x});
}
}
}
void rmedge(int idx){
for (auto x: gedge[idx]){
if (!markdot[x]){
st.erase({cntdot[x], x});
cntdot[x]--;
st.insert({cntdot[x], x});
}
}
}
int construct_roads(std::vector<int> X, std::vector<int> Y) {
memset(dsu, -1, sizeof dsu);
n = X.size();
for (int i = 0; i < n; i++){
x[i] = X[i];
y[i] = Y[i];
p.push_back({{X[i], Y[i]}, i});
numx[X[i]].push_back(Y[i]);
numy[Y[i]].push_back(X[i]);
}
sort(all(p));
for (int i = 0; i < maxn; i++){
sort(all(numx[i]));
for (int j = 1; j < numx[i].size(); j++){
if (numx[i][j-1] + 2 == numx[i][j]){
int u = (*lower_bound(all(p), MP(MP(i, numx[i][j-1]), 0))).S;
int v = (*lower_bound(all(p), MP(MP(i, numx[i][j]), 0))).S;
if (merge(u, v)) edge.push_back({u, v});
}
}
sort(all(numy[i]));
for (int j = 1; j < numy[i].size(); j++){
if (numy[i][j-1] + 2 == numy[i][j]){
int u = (*lower_bound(all(p), MP(MP(numy[i][j-1], i), 0))).S;
int v = (*lower_bound(all(p), MP(MP(numy[i][j], i), 0))).S;
if (merge(u, v)) edge.push_back({u, v});
}
}
}
if (edge.size() != n-1) return 0;
for (int i = 0; i < n-1; i++){
pair<pii,pii> tmp = getdot(edge[i].F, edge[i].S);
//debug(edge[i].F, edge[i].S, tmp.F.F, tmp.F.S, tmp.S.F, tmp.S.S);
dot.push_back(tmp.F);
dot.push_back(tmp.S);
}
sort(all(dot));
dot.resize(distance(dot.begin(), unique(all(dot))));
for (int i = 0; i < n-1; i++){
cntedge[i] = 2;
pair<pii,pii> tmp = getdot(edge[i].F, edge[i].S);
int idx = lower_bound(all(dot), tmp.F) - dot.begin();
gdot[idx].push_back(i);
gedge[i].push_back(idx);
cntdot[idx]++;
idx = lower_bound(all(dot), tmp.S) - dot.begin();
gdot[idx].push_back(i);
gedge[i].push_back(idx);
cntdot[idx]++;
}
for (int i = 0; i < n-1; i++){
st.insert({cntedge[i], i});
}
for (int i = 0; i < dot.size(); i++){
st.insert({cntdot[i], n+i});
}
while(!st.empty()){
pii v = *st.begin();
st.erase(st.begin());
// debug(v.F, v.S);
if (v.F == 0){
assert(v.S >= n);
continue;
}
if (v.S > n){
v.S -= n;
markdot[v.S] = true;
for (auto x: gdot[v.S]){
if (!markedge[x]){
// debug(x, v.S);
markedge[x] = true;
a[x] = dot[v.S].F;
b[x] = dot[v.S].S;
st.erase({cntedge[x], x});
rmdot(v.S);
rmedge(x);
break;
}
}
}
else{
markedge[v.S] = true;
for (auto x: gedge[v.S]){
if (!markdot[x]){
// debug(v.S, x);
markdot[x] = true;
a[v.S] = dot[x].F;
b[v.S] = dot[x].S;
st.erase({cntdot[x], x});
rmdot(x);
rmedge(v.S);
break;
}
}
}
}
vector<int> U, V, A, B;
for (int i = 0; i < n-1; i++){
U.push_back(edge[i].F);
V.push_back(edge[i].S);
A.push_back(a[i]);
B.push_back(b[i]);
}
build(U, V, A, B);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int j = 1; j < numx[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~
parks.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int j = 1; j < numy[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~
parks.cpp:100: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]
100 | if (edge.size() != n-1) return 0;
| ~~~~~~~~~~~~^~~~~~
parks.cpp:124: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]
124 | for (int i = 0; i < dot.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
24532 KB |
Output is correct |
| 2 |
Runtime error |
33 ms |
49612 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
24532 KB |
Output is correct |
| 2 |
Runtime error |
33 ms |
49612 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
24532 KB |
Output is correct |
| 2 |
Runtime error |
33 ms |
49612 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
24532 KB |
Output is correct |
| 2 |
Runtime error |
33 ms |
49612 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
24532 KB |
Output is correct |
| 2 |
Runtime error |
33 ms |
49612 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
24532 KB |
Output is correct |
| 2 |
Runtime error |
33 ms |
49612 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
