#include "parks.h"
#include <bits/stdc++.h>
constexpr int X = 4;
constexpr int Y = 2E5;
int pos[X + 1][Y + 1];
int construct_roads(std::vector<int> x_in, std::vector<int> y_in) {
int n = x_in.size();
{
int max = *std::max_element(x_in.begin(), x_in.end());
assert(max <= X);
}
for (int i = 0; i < n; i++) {
pos[x_in[i]][y_in[i]] = i + 1;
}
std::vector<int> v, u;
std::vector<int> a, b;
for (int y = 2; y + 2 <= Y; y += 2) {
if (pos[2][y] != 0 && pos[2][y + 2] != 0) {
v.push_back(pos[2][y]);
u.push_back(pos[2][y + 2]);
a.push_back(1);
b.push_back(y + 1);
}
}
for (int y = 2; y + 2 <= Y; y += 2) {
if (pos[4][y] != 0 && pos[4][y + 2] != 0) {
v.push_back(pos[4][y]);
u.push_back(pos[4][y + 2]);
a.push_back(5);
b.push_back(y + 1);
}
}
for (int y = 2; y <= Y; y += 2) {
if (pos[2][y] != 0 && pos[4][y] != 0) {
v.push_back(pos[2][y]);
u.push_back(pos[4][y]);
a.push_back(3);
b.push_back(y + 1);
}
}
std::vector<std::vector<int>> adj(n + 1);
for (int i = 0; i < v.size(); i++) {
adj[v[i]].push_back(i);
adj[u[i]].push_back(i);
}
std::vector<bool> vis(n + 1);
auto dfs = [&](auto self, int x) -> void {
vis[x] = true;
for (int i : adj[x]) {
int y = v[i] ^ u[i] ^ x;
if (!vis[y]) {
self(self, y);
}
}
};
dfs(dfs, 1);
if (std::count(vis.begin(), vis.end(), true) == n) {
for (int &x : v) x--;
for (int &y : u) y--;
build(v, u, a, b);
return 1;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |