#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);
struct Road
{
pair<int, int> u, v, bench;
int u_idx, v_idx, idx;
int o;
Road() {
u = v = bench = {-1, -1};
u_idx = v_idx = idx = o = -1;
}
Road(const pii& a, const pii& b, int a_idx, int b_idx, int j) : u(a), v(b), u_idx(a_idx), v_idx(b_idx), idx(j) {
bench = {-1, -1};
if(u > v) {
swap(u, v);
swap(u_idx, v_idx);
}
// assert(u.first == v.first or u.second == v.second);
if(u.first == v.first) { // vertical
o = 0;
}
else { // horizontal
o = 1;
}
}
bool operator<(const Road& other) const {
return make_pair(u, v) < make_pair(other.u, other.v);
}
friend ostream& operator<<(ostream& os, const Road& r) {
os << r.u_idx << " -> " << r.v_idx << " : " << r.u << " --> " << r.v;
return os;
}
};
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
// vector<pii> points(n);
// for(int i = 0; i < n; ++i) {
// points[i] = {x[i], y[i]};
// }
vector<bool> vis(n);
map<pair<int, int>, int> mp;
for(int i = 0; i < n; ++i) {
mp[{x[i], y[i]}] = i;
}
const int dx[] = {0, +2, 0, -2},
dy[] = {+2, 0, -2, 0};
vector<Road> roads;
auto road_dfs = [&](auto&& dfs, int i, int j) -> void
{
const int idx = mp[{i, j}];
if(vis[idx]) {
return;
}
vis[idx] = true;
for(int d = 0; d < 4; ++d) {
const int ii = i + dx[d], jj = j + dy[d];
auto it = mp.find({ii, jj});
if(it != mp.end() and !vis[it->second]) {
roads.push_back(Road({i,j}, {ii,jj}, idx, it->second, roads.size()));
dfs(dfs, ii, jj);
}
}
};
road_dfs(road_dfs, x[0], y[0]);
// assert((int)roads.size() < n);
if((int)roads.size() != n - 1) {
return 0;
}
sort(roads.begin(), roads.end());
map<pair<int, int>, int> taken;
bool ok = true;
for(int i = 0; i < (int)roads.size(); ++i) {
const Road& r = roads[i];
array<int, 2> co{(r.u.first + r.v.first)/2, (r.u.second + r.v.second) / 2};
co[r.o ^ 1] -= 1;
if(!taken.count({co[0], co[1]})) {
taken[{co[0], co[1]}] = true;
roads[i].bench = {co[0], co[1]};
continue;
}
co[r.o ^ 1] += 2;
if(!taken.count({co[0], co[1]})) {
taken[{co[0], co[1]}] = true;
roads[i].bench = {co[0], co[1]};
}
else {
ok = false;
break;
}
}
if(!ok) {
assert(false);
roads.assign(n, Road());
taken.clear();
auto road_dfs2 = [&](auto&& dfs, int i, int j) -> void
{
const int idx = mp[{i, j}];
if(vis[idx]) {
return;
}
vis[idx] = true;
for(int d = 0; d < 4; ++d) {
const int ii = i + dx[d], jj = j + dy[d];
auto it = mp.find({ii, jj});
if(it != mp.end() and !vis[it->second]) {
roads.push_back(Road({i,j}, {ii,jj}, idx, it->second, roads.size()));
dfs(dfs, ii, jj);
}
}
};
road_dfs2(road_dfs2, x[0], y[0]);
sort(roads.begin(), roads.end(),[&](const Road& a, const Road& b) { return make_pair(a.v, a.u) < make_pair(b.v, b.u); });
for(int i = 0; i < (int)roads.size(); ++i) {
const Road& r = roads[i];
array<int, 2> co{(r.u.first + r.v.first)/2, (r.u.second + r.v.second) / 2};
co[r.o ^ 1] -= 1;
if(!taken.count({co[0], co[1]})) {
taken[{co[0], co[1]}] = true;
roads[i].bench = {co[0], co[1]};
continue;
}
co[r.o ^ 1] += 2;
if(!taken.count({co[0], co[1]})) {
taken[{co[0], co[1]}] = true;
roads[i].bench = {co[0], co[1]};
}
else {
return 0;
}
}
}
const int m = roads.size();
vector<int> ansu(m), ansv(m), ansa(m), ansb(m);
for(int i = 0; i < m; ++i) {
ansu[roads[i].idx] = roads[i].u_idx;
ansv[roads[i].idx] = roads[i].v_idx;
ansa[roads[i].idx] = roads[i].bench.first;
ansb[roads[i].idx] = roads[i].bench.second;
}
build(ansu, ansv, ansa, ansb);
return 1;
}
template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
os << "[";
for(size_t i = 0; i + 1 < N; ++i) {
os << a[i] << ", ";
}
if(N > 0)
os << a[N - 1];
os << "]";
return os;
}
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
os << "(" << p.first << ", " << p.second << ") ";
return os;
}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
os << '[';
for(auto x : v)
os << x << ", ";
os << "] ";
return os;
}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
os << "{";
for(auto x : s)
os << x << ", ";
os << "} ";
return os;
}
//
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) {
os << "{";
for(auto x : s)
os << x << ", ";
os << "} ";
return os;
}
/*
5
4 4
4 6
6 4
4 2
2 4
6
4 4
4 6
6 4
4 2
2 4
2 6
2
2 2
4 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
a[0] = 2 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
a[0] = 2 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
a[0] = 2 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
a[0] = 2 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
a[0] = 2 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
a[0] = 2 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
