#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "parks.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
//
//static void check(bool cond, string message) {
// if (!cond) {
// printf("%s\n", message.c_str());
// fclose(stdout);
// exit(0);
// }
//}
//
//static int n;
//static bool build_called;
//static int m;
//static vector<int> _u, _v, _a, _b;
//
//void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
// check(!build_called, "build is called more than once");
// build_called = true;
// m = u.size();
// check(int(v.size()) == m, "u.size() != v.size()");
// check(int(a.size()) == m, "u.size() != a.size()");
// check(int(b.size()) == m, "u.size() != b.size()");
// _u = u;
// _v = v;
// _a = a;
// _b = b;
//}
const int N = 2e5 + 10;
int par[N], sz[N];
int Find(int u) {
return (u == par[u] ? u : par[u] = Find(par[u]));
}
int Union(int u, int v) {
if ((u = Find(u)) == (v = Find(v))) return 0;
if (sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
return 1;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = x.size();
map <pair <int, int>, int> id;
for (int i = 0; i < n; ++i) id[{x[i], y[i]}] = i, par[i] = i, sz[i] = 1;
vector <tuple <int, int, int, int> > ans;
int cnt = 0;
auto addX = [&](int x, int y, int i, int j) {
if (Find(i) == Find(j)) return;
if (x + y & 2) ans.push_back({i, j, x - 1, y - 1});
else ans.push_back({i, j, x + 1, y - 1});
cnt += Union(i, j);
};
auto addY = [&](int x, int y, int i, int j) {
if (Find(i) == Find(j)) return;
if (x + y & 2) ans.push_back({i, j, x - 1, y + 1});
else ans.push_back({i, j, x - 1, y - 1});
cnt += Union(i, j);
};
for (int i = 1; i <= n; ++i) {
if (id.find({x[i], y[i] - 2}) != id.end()) addX(x[i], y[i], i, id[{x[i], y[i] - 2}]);
else addY(x[i], y[i], i, id[{x[i] - 2, y[i]}]);
}
if (cnt != n - 1) return 0;
vector <int> u, v, a, b;
for (auto [_u, _v, _a, _b]: ans)
u.push_back(_u), v.push_back(_v), a.push_back(_a), b.push_back(_b);
build(u, v, a, b);
return 1;
}
//int main() {
// assert(scanf("%d", &n) == 1);
// vector<int> x(n), y(n);
// for (int i = 0; i < n; i++) {
// assert(scanf("%d%d", &x[i], &y[i]) == 2);
// }
// fclose(stdin);
//
// build_called = false;
// const int possible = construct_roads(x, y);
//
// check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
// if (possible == 1) {
// check(build_called, "construct_roads() returned 1 without calling build()");
// } else {
// check(!build_called, "construct_roads() called build() but returned 0");
// }
//
// printf("%d\n", possible);
// if (possible == 1) {
// printf("%d\n", m);
// for (int j = 0; j < m; j++) {
// printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
// }
// }
// fclose(stdout);
// return 0;
//}
Compilation message
parks.cpp: In lambda function:
parks.cpp:64:15: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
64 | if (x + y & 2) ans.push_back({i, j, x - 1, y - 1});
| ~~^~~
parks.cpp: In lambda function:
parks.cpp:70:15: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
70 | if (x + y & 2) ans.push_back({i, j, x - 1, y + 1});
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Pair u[0]=1 @(2, 6) and v[0]=0 @(2, 2) does not form a valid edge (distance != 2) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Pair u[0]=1 @(2, 6) and v[0]=0 @(2, 2) does not form a valid edge (distance != 2) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Pair u[0]=1 @(2, 6) and v[0]=0 @(2, 2) does not form a valid edge (distance != 2) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Pair u[0]=1 @(2, 6) and v[0]=0 @(2, 2) does not form a valid edge (distance != 2) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Pair u[0]=1 @(2, 6) and v[0]=0 @(2, 2) does not form a valid edge (distance != 2) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Pair u[0]=1 @(2, 6) and v[0]=0 @(2, 2) does not form a valid edge (distance != 2) |
| 4 |
Halted |
0 ms |
0 KB |
- |
