#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);
class dsu {
public:
vector<int> p;
int n;
dsu(){};
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
int construct_roads (vector<int> xvec, vector<int> yvec) {
int N = xvec.size();
map<pair<int, int>, int> to_v;
for (int i = 0; i < N; i++) {
to_v[make_pair(xvec[i], yvec[i])] = i;
}
auto get_v = [&](int X, int Y) {
if (to_v.count(make_pair(X, Y))) {
return to_v[make_pair(X, Y)];
}
return -1;
};
int n = 0;
vector<vector<int>> g;
map<pair<int, int>, int> to_face;
vector<pair<int, int>> bench;
auto get_face = [&](int X, int Y) {
if (to_face.count(make_pair(X, Y))) {
return to_face[make_pair(X, Y)];
}
bench.push_back({X, Y});
g.push_back({});
return to_face[make_pair(X, Y)] = n++;
};
int m = 0;
vector<int> node1, node2, face1, face2;
dsu fountain(N);
int is_connected = N;
auto make_edge = [&] (int x, int y, int X, int Y) {
int u = get_v(x, y), v = get_v(X, Y);
if (v == -1) {
return;
}
node1.push_back(u);
node2.push_back(v);
is_connected -= fountain.unite(u, v);
int f1, f2;
if (x == X) {
f1 = get_face(x + 1, (y + Y) / 2);
f2 = get_face(x - 1, (y + Y) / 2);
} else {
f1 = get_face((x + X) / 2, y + 1);
f2 = get_face((x + X) / 2, y - 1);
}
g[f1].push_back(m);
g[f2].push_back(m);
face1.push_back(f1);
face2.push_back(f2);
m++;
};
for (int i = 0; i < N; i++) {
int x = xvec[i], y = yvec[i];
make_edge(x, y, x + 2, y);
make_edge(x, y, x, y + 2);
}
if (is_connected > 1) {
return 0;
}
vector<int> removal(m);
vector<int> is_deg4(n);
for (int i = 0; i < n; i++) {
is_deg4[i] = g[i].size() == 4;
assert(g[i].size() <= 4 && g[i].size() != 3 && g[i].size() != 0);
}
vector<vector<int>> nodes;
vector<vector<int>> edges;
{
vector<vector<int>> gr(m);
for (int i = 0; i < n; i++) {
for (int j = 0; j + 1 < (int) g[i].size(); j += 2) {
int e1 = g[i][j], e2 = g[i][j + 1];
gr[e1].push_back(e2);
gr[e2].push_back(e1);
}
}
vector<int> used(m);
vector<int> way;
vector<int> path;
auto gen = [&] (int v, int e) {
way = {v};
path = {e};
used[e] = 1;
while (true) {
int new_v = face1[e] ^ face2[e] ^ v;
int new_e = -1;
for (int i : gr[e]) {
if ((face1[i] == new_v || face2[i] == new_v) && !used[i]) {
assert(new_e == -1);
new_e = i;
}
}
swap(v, new_v);
swap(e, new_e);
way.push_back(v);
if (e == -1) {
break;
}
path.push_back(e);
used[e] = 1;
}
};
vector<int> in_queue(n);
int iter = 0;
auto add = [&] () {
iter++;
int sz = way.size();
vector<int> que = {way[0]};
vector<int> stk;
in_queue[way[0]] = iter;
for (int i = 1; i < sz; i++) {
int v = way[i];
if (in_queue[v] == iter) {
nodes.push_back({v});
edges.push_back({path[i - 1]});
while (que.back() != v) {
nodes.back().push_back(que.back());
edges.back().push_back(stk.back());
in_queue[que.back()] = 0;
que.pop_back();
stk.pop_back();
}
} else {
que.push_back(v);
stk.push_back(path[i - 1]);
in_queue[v] = iter;
}
}
if (stk.size()) {
nodes.push_back(que);
edges.push_back(stk);
}
};
for (int e = 0; e < m; e++) {
if (gr[e].size() == 1) {
int u = face1[e];
if (g[u].size() % 2 == 0) {
u = face2[e];
}
gen(u, e);
add();
}
}
}
int sz = nodes.size();
vector<int> que;
vector<vector<int>> relaxed(n);
vector<int> was(sz);
for (int i = 0; i < sz; i++) {
for (int j : nodes[i]) {
relaxed[j].push_back(i);
}
bool ok = false;
for (int j : nodes[i]) {
if (!is_deg4[j]) {
ok = true;
}
}
if (ok) {
que.push_back(i);
was[i] = 1;
}
}
for (int b = 0; b < (int) que.size(); b++) {
int i = que[b];
for (int j = 0; j < (int) edges[i].size(); j++) {
int v = nodes[i][j], e = edges[i][j];
if (is_deg4[v]) {
removal[e] = 1;
is_deg4[v] = 0;
for (int t : relaxed[v]) {
if (!was[t]) {
que.push_back(t);
was[t] = 1;
}
}
}
}
}
/*debug(bench)
{
vector<pair<int, int>> bug;
for (int i = 0; i < m; i++) {
bug.push_back({face1[i], face2[i]});
}
debug(bug);
}
debug(removal);
for (int i = 0; i < m; i++) {
if (removal[i]) {
debug(face1[i], face2[i]);
}
}*/
assert((int) que.size() == sz);
vector<int> visited(n);
vector<int> parent(n);
vector<int> paired(m, -1);
int back_edge = -1;
int from = -1;
function<void(int, int)> dfs = [&](int v, int ed) {
parent[v] = ed;
visited[v] = 1;
paired[ed] = v;
for (int e : g[v]) {
if (removal[e] || e == ed) {
continue;
}
int u = face1[e] ^ face2[e] ^ v;
if (visited[u]) {
assert(back_edge == -1 || back_edge == e);
if (back_edge == e) {
continue;
}
back_edge = e;
from = u;
continue;
}
dfs(u, e);
}
};
for (int v = 0; v < n; v++) {
if (visited[v]) {
continue;
}
dfs(v, -1);
while(back_edge != -1) {
paired[back_edge] = from;
back_edge = parent[from];
if (back_edge != -1) {
from = face1[back_edge] ^ face2[back_edge] ^ from;
} else {
from = -1;
}
}
}
dsu d(N);
int still_connected = N;
/*auto build = [&] (vector<int> ru, vector<int> rv, vector<int> rx, vector<int> ry) {
int S = ru.size();
for (int i = 0; i < S; i++) {
int x = xvec[ru[i]], y = yvec[ru[i]], X = xvec[rv[i]], Y = yvec[rv[i]];
cout << "" << x << " " << y << " " << X << " " << Y;
cout << "\n" << rx[i] << " " << ry[i] << endl;
//cout << "Segment " << rx[i] << " " << ry[i] << " " << (x + X) / 2 << " " << (y + Y) / 2 << endl;
}
};*/
vector<int> ru, rv, rx, ry;
for (int e = 0; e < m; e++) {
if (removal[e]) {
continue;
}
assert(paired[e] != -1);
ru.push_back(node1[e]);
rv.push_back(node2[e]);
still_connected -= d.unite(node1[e], node2[e]);
int id = paired[e];
assert(~id);
rx.push_back(bench[id].first);
ry.push_back(bench[id].second);
}
build(ru, rv, rx, ry);
assert(still_connected == 1);
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
