#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 20;
vector<int> adj[maxn * 3];
bool flag[maxn * 3];
map<pair<int, int>, int> even_id;
map<pair<int, int>, int> odd_id;
vector<pair<int, int>> odds;
vector<pair<int, int>> roads;
int node_cnt;
int road_cnt;
vector<int> path;
int get_even_id(int x, int y) {
auto it = even_id.find(make_pair(x, y));
if (it == even_id.end()) {
return -1;
}
else {
return it->second;
}
}
int get_odd_id(int x, int y) {
auto it = odd_id.find(make_pair(x, y));
if (it != odd_id.end()) {
return it->second;
}
else {
odds.emplace_back(x, y);
return odd_id[make_pair(x, y)] = node_cnt++;
}
}
void add_edge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void dfs(int u) {
flag[u] = true;
path.push_back(u);
for (auto v: adj[u]) {
if (!flag[v]) {
dfs(v);
}
}
}
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
for (int i = 0; i < n; i++) {
even_id[make_pair(x[i], y[i])] = i;
}
for (int u = 0; u < n; u++) {
int v = get_even_id(x[u] + 2, y[u]);
if (v != -1) {
roads.emplace_back(u, v);
add_edge(u, v);
}
v = get_even_id(x[u], y[u] + 2);
if (v != -1) {
roads.emplace_back(u, v);
add_edge(u, v);
}
}
dfs(0);
for (int i = 0; i < n; i++) {
if (!flag[i]) {
return 0;
}
}
for (int i = 0; i < n; i++) {
adj[i].clear();
}
bool sub2 = true;
for (int i = 0; i < n; i++) {
sub2 &= x[i] <= 4;
}
if (sub2) {
vector<int> _u, _v, a, b;
for (int i = 0; i < road_cnt; i++) {
int u = roads[i].first;
int v = roads[i].second;
_u.push_back(u);
_v.push_back(v);
if (y[u] == y[v]) {
a.push_back(x[u] + 1);
b.push_back(y[v] + 1);
}
else if (x[u] == 2) {
a.push_back(x[u] - 1);
b.push_back(y[v] + 1);
}
else {
a.push_back(x[u] + 1);
b.push_back(y[v] + 1);
}
}
build(_u, _v, a, b);
return 1;
}
road_cnt = roads.size();
node_cnt = road_cnt;
for (int i = 0; i < road_cnt; i++) {
int u = roads[i].first;
int v = roads[i].second;
if (y[u] == y[v]) {
add_edge(i, get_odd_id(x[u] + 1, y[u] - 1));
add_edge(i, get_odd_id(x[u] + 1, y[u] + 1));
}
else {
add_edge(i, get_odd_id(x[u] - 1, y[u] + 1));
add_edge(i, get_odd_id(x[u] + 1, y[u] + 1));
}
}
vector<int> u, v, a, b;
for (int i = 0; i < node_cnt; i++) {
flag[i] = false;
}
for (int iter = 0; iter < 2; iter++) {
for (int i = road_cnt; i < node_cnt; i++) {
if (!flag[i] && (iter == 1 || (int)adj[i].size() == 1)) {
path.clear();
dfs(i);
for (int j = 0; j + 1 < (int)path.size(); j += 2) {
u.push_back(roads[path[j + 1]].first);
v.push_back(roads[path[j + 1]].second);
a.push_back(odds[path[j] - road_cnt].first);
b.push_back(odds[path[j] - road_cnt].second);
}
}
}
}
build(u, v, a, b);
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
14292 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
14292 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
14292 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
14292 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
14292 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
14292 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
