#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
typedef long double ld;
const ld eps = 1e-8;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const ll inf = 1e18;
const ll mod = 1e9 + 7;
#include "parks.h"
vector<vector<int>> g;
vector<int> u, v, a, b;
vector<int> used;
void dfs(int ver) {
used[ver] = 1;
for (auto nod : g[ver]) {
if (!used[nod]) {
u.push_back(ver);
v.push_back(nod);
dfs(nod);
}
}
}
int construct_roads(vector<int> x, vector<int> y) {
bool fir = 1, sec = 1, thi = 1;
int n = x.size();
for (int i = 0; i < n; i++) {
if (x[i] != 2)
fir = 0;
}
map<pair<int, int>, int> mp;
for (int i = 0; i < n; i++) {
mp[{x[i], y[i]}] = i;
}
g.resize(n);
for (int i = 0; i < n; i++) {
if (mp.find({x[i] - 2, y[i]}) != mp.end()) {
g[i].push_back(mp[{x[i] - 2, y[i]}]);
}
if (mp.find({x[i] + 2, y[i]}) != mp.end()) {
g[i].push_back(mp[{x[i] + 2, y[i]}]);
}
if (mp.find({x[i], y[i] - 2}) != mp.end()) {
g[i].push_back(mp[{x[i], y[i] - 2}]);
}
if (mp.find({x[i], y[i] + 2}) != mp.end()) {
g[i].push_back(mp[{x[i], y[i] + 2}]);
}
}
used.resize(n);
dfs(0);
bool ch = 1;
for (int i = 0; i < n; i++) {
if (!used[i])
ch = 0;
}
if (!ch)
return 0;
map<pair<int, int>, int> bench;
map<pair<int, int>, set<int>> want;
set<vector<int>> ben;
for (int i = 0; i < v.size(); i++) {
if (x[v[i]] == x[u[i]]) {
want[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}].insert(i);
want[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}].insert(i);
bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}]++;
bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}]++;
} else {
want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}].insert(i);
want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}].insert(i);
bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}]++;
bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}]++;
}
}
for (auto [pa, cnt] : bench) {
ben.insert({cnt, pa.fi, pa.se});
}
a.resize(n - 1);
b.resize(n - 1);
while(!ben.empty()) {
auto cur = *ben.begin();
int i = *want[{cur[1], cur[2]}].begin();
if (cur[0] > 1)
while(1)
a[i] = cur[1];
b[i] = cur[2];
if (x[v[i]] == x[u[i]]) {
want[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}].erase(i);
want[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}].erase(i);
ben.erase({bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] + 1,(y[v[i]] + y[u[i]]) / 2});
ben.erase({bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2});
bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}]--;
bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}]--;
if (bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}] > 0) {
ben.insert({bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] + 1,(y[v[i]] + y[u[i]]) / 2});
}
if (bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}] > 0) {
ben.insert({bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2});
}
} else {
want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}].erase(i);
want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}].erase(i);
ben.erase({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}],(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1 });
ben.erase({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}], (x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1});
bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}]--;
bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}]--;
if ( bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}] > 0) {
ben.insert({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}],(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1 });
}
if (bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}] > 0) {
ben.insert({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}], (x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1});
}
}
}
build(u, v, a, b);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
parks.cpp:34:10: warning: variable 'fir' set but not used [-Wunused-but-set-variable]
34 | bool fir = 1, sec = 1, thi = 1;
| ^~~
parks.cpp:34:19: warning: unused variable 'sec' [-Wunused-variable]
34 | bool fir = 1, sec = 1, thi = 1;
| ^~~
parks.cpp:34:28: warning: unused variable 'thi' [-Wunused-variable]
34 | bool fir = 1, sec = 1, thi = 1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
a[0] = 0 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
a[0] = 0 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
a[0] = 0 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
a[0] = 0 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
a[0] = 0 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
a[0] = 0 is not an odd integer |
| 3 |
Halted |
0 ms |
0 KB |
- |
