//Challenge: Accepted
#include "parks.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b) {
cout << a << " ", debug(b ...);
};
template<class T> void pary (T l, T r) {
while (l!= r) cout << *l << " ", l++;
cout << endl;
};
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct pnt{
int x, y, id;
pnt(){x = y = id = 0;}
pnt(int a, int b, int c){x = a, y = b, id = c;}
};
int par[maxn];
int find(int a) {
return a == par[a] ? a : par[a] = find(par[a]);
}
int num = 0;
bool Union (int a, int b) {
//debug(a, b);
a = find(a), b = find(b);
if (a == b) return false;
//debug(1);
num--;
par[find(a)] = find(b);
return true;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = x.size();
for (int i = 0;i < n;i++) par[i] = i;
num = n;
vector<pnt> a, b;
for (int i = 0;i < n;i++) {
if (x[i] == 2)a.push_back(pnt(y[i], x[i], i));
else b.push_back(pnt(y[i], x[i], i));
}
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
sort(a.begin(), a.end(), [&](pnt p, pnt q){return (p.x == q.x ? p.y < q.y : p.x < q.x);});
sort(b.begin(), b.end(), [&](pnt p, pnt q){return (p.x == q.x ? p.y < q.y : p.x < q.x);});
vector<int> u, v, ax, ay;
int id = 0;
for (int i = 0;i < a.size();i++) {
while (id < b.size() && b[id].x < a[i].x) id++;
if (i && a[i].x - a[i-1].x == 2) {
if (Union(a[i].id, a[i-1].id)) {
u.push_back(a[i].id), v.push_back(a[i-1].id);
ax.push_back(a[i].x - 1), ay.push_back(a[i].y - 1);
}
}
if (id < b.size() && a[i].x == b[id].x) {
if (Union(a[i].id, b[id].id)) {
u.push_back(a[i].id), v.push_back(b[id].id);
ax.push_back(a[i].x - 1), ay.push_back(a[i].y + 1);
}
}
}
for (int i = 1;i < b.size();i++) {
if (b[i].x - b[i-1].x == 2) {
if (Union(b[i].id, b[i-1].id)) {
u.push_back(b[i].id), v.push_back(b[i-1].id);
ax.push_back(b[i].x - 1), ay.push_back(b[i].y + 1);
}
}
}
if (num > 1) return 0;
build(u, v, ax, ay);
return 1;
}
/*
5
2 2
4 2
4 4
4 6
2 6
*/
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int i = 0;i < a.size();i++) {
| ~~^~~~~~~~~~
parks.cpp:59:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | while (id < b.size() && b[id].x < a[i].x) id++;
| ~~~^~~~~~~~~~
parks.cpp:66:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | if (id < b.size() && a[i].x == b[id].x) {
| ~~~^~~~~~~~~~
parks.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i = 1;i < b.size();i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Tree (a[0], b[0]) = (3, 1) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(2, 2) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Tree (a[0], b[0]) = (3, 1) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(2, 2) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Tree (a[0], b[0]) = (3, 1) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(2, 2) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Tree (a[0], b[0]) = (3, 1) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(2, 2) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Tree (a[0], b[0]) = (3, 1) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(2, 2) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Tree (a[0], b[0]) = (3, 1) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(2, 2) |
| 3 |
Halted |
0 ms |
0 KB |
- |
