#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
map<pii, int> field;
vector<int> x, y, used;
vector<pii> e;
map<int, int> type;
int n;
void dfs(int v, int c) {
if (used[v])
return;
used[v] = 1;
int vx = x[v], vy = y[v];
pii t[4] = {{vx + 2, vy}, {vx - 2, vy}, {vx, vy + 2}, {vx, vy - 2}};
bool p0 = field.count(t[0]) && !used[field[t[0]]];
bool p1 = field.count(t[1]) && !used[field[t[1]]];
bool p2 = field.count(t[2]) && !used[field[t[2]]];
bool p3 = field.count(t[3]) && !used[field[t[3]]];
if (p0 && p1) {
int x = field[t[0]], y =field[t[1]];
type[e.size()] = 0; e.push_back({v, x});
dfs(x, 1);
type[e.size()] = 1; e.push_back({v, y});
dfs(y, 0);
} else if (p0) {
int x = field[t[0]];
type[e.size()] = c; e.push_back({v, x});
dfs(x, !c);
} else if (p1) {
int y = field[t[1]];
type[e.size()] = c; e.push_back({v, y});
dfs(y, !c);
}
if (p2) {
int u = field[t[2]];
e.push_back({v, u});
dfs(u, c);
}
if (p3) {
int u = field[t[3]];
e.push_back({v, u});
dfs(u, c);
}
}
int construct_roads(std::vector<int> X, std::vector<int> Y) {
n = X.size(), x = X, y = Y;
for (int i = 0; i < n; i++)
field[{x[i], y[i]}] = i;
used.resize(n, 0);
dfs(0, 0);
if (count(used.begin(), used.end(), 0))
return 0;
vector<int> a(e.size()), b(e.size());
for (int i = 0; i < e.size(); i++) {
if (type.count(i)) {
pii p = e[i];
pii v = {x[p.first], y[p.first]}, u = {x[p.second], y[p.second]};
if (type[i])
a[i] = (v.first + u.first) / 2, b[i] = v.first - 1;
else
a[i] = (v.first + u.first) / 2, b[i] = v.first + 1;
field[{a[i], b[i]}] = -1;
}
}
for (int i = 0; i < e.size(); i++) {
if (type.count(i)) {
pii p = e[i];
pii v = {x[p.first], y[p.first]}, u = {x[p.second], y[p.second]};
a[i] = v.first - 1, b[i] = (v.second + u.second) / 2;
if (field.count({a[i], b[i]}))
a[i] += 2;
if (field.count({a[i], b[i]}))
return 0;
}
}
vector<int> us, vs;
for (auto p : e)
us.push_back(p.first), vs.push_back(p.second);
build(us, vs, a, b);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int i = 0; i < e.size(); i++) {
| ~~^~~~~~~~~~
parks.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i = 0; i < e.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
a[0] = 0 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
a[0] = 0 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
a[0] = 0 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
a[0] = 0 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
a[0] = 0 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
a[0] = 0 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
