#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
const int MAXN = 6e5+7;
vector <int> graph[MAXN];
int N, RN, BN, degree[MAXN], parent[MAXN];
bool used[MAXN];
int link[MAXN], saizu[MAXN];
int x[MAXN], y[MAXN];
int numOfCycles;
pii roads[MAXN];
vector <pii> benches;
int find(int n) {
if (n == link[n]) return n;
return link[n] = find(link[n]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (saizu[a] < saizu[b]) swap(a, b);
saizu[a] += saizu[b];
link[b] = a;
}
bool same(int a, int b) {
return find(a) == find(b);
}
void dfs(int v) {
used[v] = 1;
for (auto to : graph[v]) {
if (!used[to]) {
dfs(to);
}
}
}
void dfs2(int v, int p) {
used[v] = 1;
for (auto to : graph[v]) {
if (used[to]) {
numOfCycles++;
}
else {
dfs2(to, v);
}
}
}
void dfs3(int v, int p) {
parent[v] = p;
used[v] = 1;
for (auto to : graph[v]) {
if (used[to]) continue;
degree[v]++;
dfs3(to, v);
}
}
int construct_roads(vector<int> X, vector<int> Y) {
N = sz(X);
if (N == 1) {
build({}, {}, {}, {});
return 1;
}
for (int i = 0; i < N; i++) {
link[i] = i;
saizu[i] = 1;
x[i] = X[i];
y[i] = Y[i];
}
X.clear(); Y.clear();
//***************** get roads and benches *****************
vector <pair <pii, int>> tmp;
vector <pii> edges;
set <pii> tmpBenches;
for (int i = 0; i < N; i++) {
tmp.pb(mp(mp(x[i], y[i]), i));
}
sort(all(tmp));
for (int i = 0; i < N; i++) {
auto it = lb(all(tmp), mp(mp(x[i]-2, y[i]), 0));
if (it != tmp.end() && (*it).first == mp(x[i]-2, y[i])) {
edges.pb(mp(i, (*it).second));
}
it = lb(all(tmp), mp(mp(x[i]+2, y[i]), 0));
if (it != tmp.end() && (*it).first == mp(x[i]+2, y[i])) {
edges.pb(mp(i, (*it).second));
}
it = lb(all(tmp), mp(mp(x[i], y[i]-2), 0));
if (it != tmp.end() && (*it).first == mp(x[i], y[i]-2)) {
edges.pb(mp(i, (*it).second));
}
it = lb(all(tmp), mp(mp(x[i], y[i]+2), 0));
if (it != tmp.end() && (*it).first == mp(x[i], y[i]+2)) {
edges.pb(mp(i, (*it).second));
}
}
for (auto &to : edges) {
if (mp(x[to.first], y[to.first]) > mp(x[to.second], y[to.second])) {
swap(to.first, to.second);
}
if (!same(to.first, to.second)) {
unite(to.first, to.second);
graph[to.first].pb(to.second);
graph[to.second].pb(to.first);
roads[RN++] = mp(to.first, to.second);
if (x[to.first] == x[to.second]) {
tmpBenches.insert(mp(x[to.first]-1, y[to.first]+1));
tmpBenches.insert(mp(x[to.first]+1, y[to.first]+1));
}
else {
tmpBenches.insert(mp(x[to.first]+1, y[to.first]+1));
tmpBenches.insert(mp(x[to.first]+1, y[to.first]-1));
}
}
}
for (auto to : tmpBenches) {
benches.pb(to);
}
BN = sz(benches);
//***************** get roads and benches *****************
//***************** check if connected *****************
dfs(0);
bool flag = 1;
for (int i = 0; i < N; i++) {
if (!used[i]) {
flag = 0;
break;
}
}
if (!flag) {
return 0;
}
for (int i = 0; i < RN+BN; i++) {
link[i] = i;
saizu[i] = 1;
used[i] = 0;
graph[i].clear();
}
edges.clear();
//***************** check if connected *****************
//***************** create a new graph *****************
for (int i = 0; i < RN; i++) {
auto a = roads[i].first, b = roads[i].second;
if (x[a] == x[b]) {
auto it = lb(all(benches), mp(x[a]-1, y[a]+1))-benches.begin();
edges.pb(mp(i, it+RN));
it = lb(all(benches), mp(x[a]+1, y[a]+1))-benches.begin();
edges.pb(mp(i, it+RN));
}
else {
auto it = lb(all(benches), mp(x[a]+1, y[a]-1))-benches.begin();
edges.pb(mp(i, it+RN));
it = lb(all(benches), mp(x[a]+1, y[a]+1))-benches.begin();
edges.pb(mp(i, it+RN));
}
}
for (auto to : edges) {
graph[to.first].pb(to.second);
graph[to.second].pb(to.first);
}
for (int i = 0; i < RN; i++) {
if (!used[i]) {
numOfCycles = 0;
dfs2(i, i);
if (numOfCycles > 1) {
return 0;
}
}
}
for (int i = 0; i < RN+BN; i++) {
used[i] = 0;
graph[i].clear();
}
for (auto to : edges) {
if (!same(to.first, to.second)) {
unite(to.first, to.second);
graph[to.first].pb(to.second);
graph[to.second].pb(to.first);
}
}
for (int i = 0; i < RN; i++) {
if (!used[i] && sz(graph[i]) == 1) {
dfs3(i, i);
}
}
for (int i = 0; i < RN; i++) {
if (!used[i]) {
dfs3(i, i);
}
}
for (int i = 0; i < RN+BN; i++) {
used[i] = 0;
}
//***************** create a new graph *****************
//***************** get the answer *****************
vector <int> _u, _v, _x, _y;
queue <int> K;
for (int i = RN; i < RN+BN; i++) {
if (!degree[i]) {
K.push(i);
}
}
while (!K.empty()) {
auto v = K.front(); K.pop();
if (!used[v] && !used[parent[v]]) {
used[v] = 1;
used[parent[v]] = 1;
_u.pb(roads[parent[v]].first);
_v.pb(roads[parent[v]].second);
_x.pb(benches[v-RN].first);
_y.pb(benches[v-RN].second);
v = parent[parent[v]];
if (v >= RN) {
degree[v]--;
if (!used[v] && !degree[v]) {
K.push(v);
}
}
}
}
build(_u, _v, _x, _y);
//***************** get the answer *****************
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14284 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
14352 KB |
Solution announced impossible, but it is possible. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14284 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
14352 KB |
Solution announced impossible, but it is possible. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14284 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
14352 KB |
Solution announced impossible, but it is possible. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14284 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
14352 KB |
Solution announced impossible, but it is possible. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14284 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
14352 KB |
Solution announced impossible, but it is possible. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14284 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
14352 KB |
Solution announced impossible, but it is possible. |
| 3 |
Halted |
0 ms |
0 KB |
- |
