#include "parks.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb empalce_back
using namespace std;
map <pair<pii, pii> , int> mp;
map <pii, bool> mark;
map <pii, int> ind;
const int nmax = 200001;
vector <int> p(nmax);
vector <int> sz(nmax);
vector <int> u, v;
vector <int> a, b;
vector <int> x, y;
vector <bool> used(nmax);
void make_set(int v){
p[v] = v;
sz[v] = 1;
}
int find_set(int v){
return p[v] == v ? v : p[v] = find_set(p[v]);
}
void union_sets(int a, int b){
if(find_set(a) == find_set(b)) return;
mp[{{x[a - 1], y[a - 1]}, {x[b - 1], y[b -1]}}] = u.size() + 1;
mp[{{x[b - 1], y[b - 1]}, {x[a - 1], y[a - 1]}}] = u.size() + 1;
u.pb(a - 1);
v.pb(b - 1);
a = find_set(a);
b = find_set(b);
if(sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
pii mark_vertical_line(int ind){
ind--;
//cout << ind << ' ';
pair <pii, pii> seg = {{x[u[ind]],y[u[ind]]}, {x[v[ind]], y[v[ind]]}};
pii A = {seg.f.f - 1, seg.f.s / 2 + seg.s.s / 2};
if(!mark[A]){
mark[A] = true;
return A;
}
A.f += 2;
mark[A] = true;
return A;
}
pii mark_horizontal_line(int ind){
ind--;
pair <pii, pii> seg = {{x[u[ind]],y[u[ind]]}, {x[v[ind]], y[v[ind]]}};
pii A = {seg.f.f / 2 + seg.s.f / 2, seg.f.s - 1};
if(!mark[A]){
mark[A] = true;
return A;
}
A.s += 2;
mark[A] = true;
return A;
}
int construct_roads(std::vector<int> X, std::vector<int> Y) {
x = X, y = Y;
int n = x.size();
for(int i = 0; i < n; i++){
ind[{x[i], y[i]}] = i + 1;
}
for(int i= 1; i <= n; i++)
make_set(i);
for(int i = 0; i < n; i++){
if(ind[{x[i], y[i] - 2}])
union_sets(ind[{x[i], y[i] - 2}], i + 1);
if(ind[{x[i], y[i] + 2}])
union_sets(ind[{x[i], y[i] + 2}], i + 1);
}
for(int i = 0; i < n; i++){
if(ind[{x[i] + 2, y[i]}])
union_sets(ind[{x[i] + 2, y[i]}], i + 1);
if(ind[{x[i] - 2, y[i]}])
union_sets(ind[{x[i] - 2, y[i]}], i + 1);
}
int cnt = 0;
for(int i = 1; i <= n; i++){
if(find_set(i) == i) cnt++;
}
if(cnt > 1) return 0;
a.resize(u.size());
b.resize(v.size());
for(int i = 0; i < u.size(); i++){
cout << u[i] << ' ' << v[i] << "\n";
}
set <int> st;
for(int i = 1; i <= u.size(); i++)
st.insert(i);
while(!st.empty()){
int s = *st.begin();
st.erase(st.begin());
// cout << s << "\n";
bool ind = true;
while(s){
used[s] = true;
st.erase(s);
pii B;
if(x[u[s - 1]] == x[v[s - 1]]){
B = mark_vertical_line(s);
a[s - 1] = B.f, b[s -1] = B.s;
s = 0;
}
else{
B = mark_horizontal_line(s);
a[s - 1] = B.f, b[s - 1] = B.s;
s = 0;
}
// cout << B.f << ' ' << B.s << "\n";
pii pos[] = {{B.f - 1, B.s - 1}, {B.f + 1, B.s - 1}, {B.f - 1, B.s + 1}, {B.f + 1, B.s + 1}};
for(int i = 0; i < 4; i++){
for(int j = i + 1; j < 4; j++){
int o = mp[{pos[i], pos[j]}];
if(o && !used[o]){
s = o;
break;
}
}
}
}
}
build(u, v, a, b);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 0; i < u.size(); i++){
| ~~^~~~~~~~~~
parks.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int i = 1; i <= u.size(); i++)
| ~~^~~~~~~~~~~
parks.cpp:109:14: warning: unused variable 'ind' [-Wunused-variable]
109 | bool ind = true;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
1876 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
1876 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
1876 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
1876 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
1876 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
1876 KB |
Possible tampering with the output |
| 3 |
Halted |
0 ms |
0 KB |
- |
