//Challenge: Accepted
#include "parks.h"
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <queue>
#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);
unordered_map<ll, vector<int> > ed;
unordered_map<int, vector<ll> > cor;
unordered_map<ll, int> mp;
struct pnt{
int x, y, id;
pnt(){x = y = id = 0;}
pnt(int a, int b, int c){x = a, y = b, id = c;}
};
ll ha(pii p) {
return ((ll)p.ff<<20) + p.ss;
}
pii getv(ll h) {
return {h>>20, h & ((1<<20) - 1)};
}
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 = 1;i <= n;i++) par[i] = i;
num = n;
vector<pnt> a;
for (int i = 0;i < n;i++) {
a.push_back(pnt(x[i], y[i], i+1));
mp[ha({x[i], y[i]})] = i+1;
}
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
vector<int> u, v, ax, ay;
int id = 0;
for (int i = 0;i < n;i++) {
pii p1 = {a[i].x + 2, a[i].y}, p2 = {a[i].x, a[i].y + 2};
int v1 = mp[ha(p1)], v2 = mp[ha(p2)];
if (v1) {
u.push_back(a[i].id-1), v.push_back(v1-1);
pii h1 = {a[i].x + 1, a[i].y + 1}, h2 = {a[i].x + 1, a[i].y - 1};
ed[ha(h1)].push_back(id), ed[ha(h2)].push_back(id);
cor[id].push_back(ha(h1)), cor[id].push_back(ha(h2));
id++;
}
if (v2) {
u.push_back(a[i].id-1), v.push_back(v2-1);
pii h1 = {a[i].x + 1, a[i].y + 1}, h2 = {a[i].x - 1, a[i].y + 1};
ed[ha(h1)].push_back(id), ed[ha(h2)].push_back(id);
cor[id].push_back(ha(h1)), cor[id].push_back(ha(h2));
id++;
}
}
//debug(111);
if (id != n - 1) return 0;
ax.resize(id), ay.resize(id);
for (int i = 0;i < id;i++) ax[i] = ay[i] = 0;
queue<ll> que;
for (auto i:ed) {
//debug(i.ff);
//pary(i.ss.begin(), i.ss.end());
if (i.ss.size() == 1) que.push(i.ff);
}
int cnt = 0;
//debug(id);
while (que.size() && cnt < id) {
ll h = que.front();
pii cur = getv(que.front());que.pop();
cnt++;
//debug(cur.ff, cur.ss);
if (ed[h].size() == 0) continue;
int ans = ed[h].back();
//debug(ans);
ax[ans] = cur.ff, ay[ans] = cur.ss;
ed[h].clear();
//debug(cur.ff, cur.ss, ans, h);
for (auto x:cor[ans]) {
auto it = find(ed[x].begin(), ed[x].end(), ans);
if (it != ed[x].end()) ed[x].erase(it);
if (ed[x].size() == 1) {
que.push(x);
}
}
}
//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);});
build(u, v, ax, ay);
return 1;
}
/*
5
2 2
4 2
4 4
4 6
2 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
a[0] = 0 is not an odd integer |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
a[0] = 0 is not an odd integer |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
a[0] = 0 is not an odd integer |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
a[0] = 0 is not an odd integer |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
a[0] = 0 is not an odd integer |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
a[0] = 0 is not an odd integer |
| 5 |
Halted |
0 ms |
0 KB |
- |
