This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> used;
void dfs(int v) {
used[v] = 1;
for (int u : g[v]) {
if (!used[u]) {
dfs(u);
}
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
map<pair<int, int>, int> byc;
int n = x.size();
for (int i = 0; i < n; i++) {
byc[{x[i], y[i]}] = i;
}
g.clear();
g.resize(n);
map<pair<int, int>, int> cnt;
auto add = [&](int i, int j) {
if (i < j) {
g[i].push_back(j);
g[j].push_back(i);
if (x[i] == x[j]) {
cnt[{x[i] + 1, (y[i] + y[j]) / 2}] += 1;
cnt[{x[i] - 1, (y[i] + y[j]) / 2}] += 1;
} else {
cnt[{(x[i] + x[j]) / 2, y[i] + 1}] += 1;
cnt[{(x[i] + x[j]) / 2, y[i] - 1}] += 1;
}
}
};
for (int i = 0; i < n; i++) {
pair<int, int> pp;
pp = {x[i] + 2, y[i]};
if (byc.count(pp)) {
add(i, byc[pp]);
}
pp = {x[i], y[i] + 2};
if (byc.count(pp)) {
add(i, byc[pp]);
}
pp = {x[i] - 2, y[i]};
if (byc.count(pp)) {
add(i, byc[pp]);
}
pp = {x[i], y[i] - 2};
if (byc.count(pp)) {
add(i, byc[pp]);
}
}
used.assign(n, 0);
dfs(0);
if (*min_element(used.begin(), used.end()) == 0) {
return 0;
}
vector<int> u, v, a, b;
for (auto [xy, _] : cnt) {
pair<int, int> RU, RD, LD, LU;
RU = RD = LD = LU = xy;
RU.first++, RU.second++;
RD.first++, RD.second--;
LU.first--, LU.second++;
LD.first--, LD.second--;
if ((xy.first + xy.second) % 4) {
// left right
if (byc.count(RU) && byc.count(RD)) {
u.push_back(byc[RU]);
v.push_back(byc[RD]);
a.push_back(xy.first);
b.push_back(xy.second);
} else if (byc.count(LU) && byc.count(LD)) {
u.push_back(byc[LU]);
v.push_back(byc[LD]);
a.push_back(xy.first);
b.push_back(xy.second);
}
} else {
if (byc.count(RU) && byc.count(LU)) {
u.push_back(byc[RU]);
v.push_back(byc[LU]);
a.push_back(xy.first);
b.push_back(xy.second);
} else if (byc.count(RD) && byc.count(LD)) {
u.push_back(byc[RD]);
v.push_back(byc[LD]);
a.push_back(xy.first);
b.push_back(xy.second);
}
}
}
build(u, v, a, b);
return 1;
}
# | 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... |