#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define st first
#define nd second
#define ll long long
#define LL node * 2
#define RR node * 2 + 1
#define N 300005
const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;
int par[N], sz[N], TOT;
pii rev[N];
int find(int node){
if (par[node] == node) return node;
return par[node] = find(par[node]);
}
void uni(int a, int b){
a = find(a), b = find(b);
if (a == b) return;
TOT--;
if (sz[a] < sz[b]) swap(a, b);
par[b] = a;
sz[a] += b;
}
int construct_roads(vector<int> x, vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
map<pii ,int> ind;
int n = x.size();
for (int i = 0; i < n; i++){
ind[{x[i], y[i]}] = i;
sz[i] = 1, par[i] = i;
}
vector<pii> dir = {{0, -2}, {-2, 0}, {0, 2}, {2, 0}};
vector<pii> edges, b1, b2;
map<pii, int> cnt;
map<pii, set<int>> rev2;
int cntr = 0;
for (int i = 0; i < n; i++){
int a = x[i], b = y[i];
for (auto k : dir){
int c = a + k.st, d = b + k.nd;
if (ind.count({c, d}) && ind[{c, d}] > i){
int g = (a + c) / 2, h = (b + d) / 2;
pii f1, f2;
if (b == d){
f1 = {g, h + 1};
f2 = {g, h - 1};
}
else{
f1 = {g + 1, h};
f2 = {g - 1, h};
}
edges.pb({i, ind[{c, d}]});
b1.pb(f1);
b2.pb(f2);
rev2[f1].insert(cntr);
rev2[f2].insert(cntr);
cnt[f1]++;
cnt[f2]++;
cntr++;
}
}
}
queue<int> q;
for (int i = 0; i < n; i++){
if (cnt[b1[i]] == 1 || cnt[b2[i]] == 1) q.push(i);
}
vector<int> u, v, a, b;
set<int> undone;
for (int i = 0; i < cntr; i++) undone.insert(i);
TOT = n;
while(TOT > 1){
while(!q.empty()){
int top = q.front();
q.pop();
undone.erase(top);
pii todo = {-1, -1};
if (cnt[b1[top]] == 1) todo = b1[top];
else if (cnt[b2[top]] == 1) todo = b2[top];
if (todo.st == -1) continue;
a.pb(todo.st), b.pb(todo.nd);
vector<pii> V = {b1[top], b2[top]};
for (auto i : V){
cnt[i]--;
rev2[i].erase(top);
if (rev2[i].size()){
q.push(*rev2[i].begin());
}
}
u.pb(edges[top].st);
v.pb(edges[top].nd);
uni(edges[top].st, edges[top].nd);
}
if (TOT == 1) break;
vector<int> del;
for (auto i : undone){
if (find(edges[i].st) == find(edges[i].nd)) del.pb(i);
else if (cnt[b1[i]] == 0 && cnt[b2[i]] == 0) del.pb(i);
}
for (auto i : del) undone.erase(i);
if (undone.empty()) break;
int tmp = *undone.begin();
cnt[b1[tmp]] = 1;
q.push(tmp);
}
if (TOT == 1){
build(u, v, a, b);
return 1;
}
return 0;
}
/*
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;
}
int main() {
fileio();
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;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Runtime error |
2 ms |
4700 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Runtime error |
2 ms |
4700 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Runtime error |
2 ms |
4700 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Runtime error |
2 ms |
4700 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Runtime error |
2 ms |
4700 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Runtime error |
2 ms |
4700 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
