#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<set<int>> graph(n + 1);
for (int e = 0; e < m; e++) {
int u = face1[e], v = face2[e];
graph[u].insert(v);
graph[v].insert(u);
}
for (int i = 0; i < n; i++) {
if (graph[i].size() & 1) {
graph[i].insert(n);
graph[n].insert(i);
}
}
vector<int> way;
function<void(int)> dfs = [&](int v) {
vector<int> que = {v};
while (que.size()) {
int u = que.back();
if (graph[u].empty()) {
way.push_back(u);
que.pop_back();
} else {
int b = *graph[u].begin();
graph[u].erase(b);
graph[b].erase(u);
que.push_back(b);
}
}
};
vector<int> que;
vector<int> in_queue(n + 1);
for (int i = n; i >= 0; i--) {
if (graph[i].empty()) {
continue;
}
way.clear();
dfs(i);
// debug(way)
//debug(graph)
for (int v : way) {
if (in_queue[v]) {
nodes.push_back({});
while (que.back() != v) {
nodes.back().push_back(que.back());
in_queue[que.back()] = 0;
que.pop_back();
}
nodes.back().push_back(v);
} else {
que.push_back(v);
in_queue[v] = 1;
}
}
// debug(i, que)
assert(que.size() == 1 && que[0] == i);
que.pop_back();
in_queue[i] = 0;
}
}
//debug(nodes)
int sz = nodes.size();
vector<vector<int>> edges;
{
map<pair<int, int>, int> cur;
for (int e = 0; e < m; e++) {
int u = face1[e], v = face2[e];
cur[make_pair(u, v)] = e;
cur[make_pair(v, u)] = e;
}
for (auto &p : nodes) {
edges.push_back({});
for (int i = 0; i < (int) p.size(); i++) {
int u = p[i], v = p[(i + 1) % p.size()];
if (cur.count(make_pair(u, v))) {
edges.back().push_back(cur[make_pair(u, v)]);
}
}
if (p.back() == n) {
p.pop_back();
}
}
}
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;
}
}
}
}
}
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;
}
}
}
/*auto build = [&] (vector<int> ru, vector<int> rv, vector<int> rx, vector<int> ry) {
dsu d(N);
int still_connected = N;
set<pair<int, int>> checker;
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]];
assert(checker.find({rx[i], ry[i]}) == checker.end());
checker.insert({rx[i], ry[i]});
if (x == X) {
assert(abs(rx[i] - X) == 1 && ry[i] == (Y + y) / 2);
} else {
assert(abs(ry[i] - Y) == 1 && rx[i] == (X + x) / 2);
}
still_connected -= d.unite(ru[i], rv[i]);
//cout << "" << x << " " << y << " " << X << " " << Y;
//cout << "\n" << rx[i] << " " << ry[i] << "\n";
}
assert(still_connected == 1);
};*/
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]);
int id = paired[e];
assert(~id);
rx.push_back(bench[id].first);
ry.push_back(bench[id].second);
}
build(ru, rv, rx, ry);
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 |
- |
