#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define pb push_back
#include "parks.h"
struct dsu {
int D[3][2];
dsu() {
D[0][0] = 0;
D[0][1] = 0;
D[1][0] = 0;
D[1][1] = 0;
D[2][0] = 0;
D[2][1] = 0;
}
void join(int x1,int x2,int y1,int y2) {
x1 = x1 / 2 - 1;x2 = x2 / 2 - 1;
y1 /= 2;y2 /= 2;
int m = min(D[x1][y1], D[x2][y2]);
int M = min(D[x1][y1], D[x2][y2]);
for (int i = 0;i < 3;i++) {
for (int j = 0;j < 2;j++) {
if (D[i][j] == M) D[i][j] = m;
}
}
}
bool conn() {
return !(D[0][0] | D[0][1] | D[1][0] | D[1][1] | D[2][0] | D[2][1]);
}
};
struct eg {
int x1;int y1;
int x2;int y2;
int b1;int b2;
eg(int a, int b, int c, int d) {
x1 = a;y1 = b;x2 = c;y2 = d;b1 = -1;b2 = 1;
}
eg(int a1, int a2, int x3, int x4, int x5, int x6) {
x1 = a1;y1 = a2;x2 = x3;y2 = x4;b1 = x5;b2 = x6;
}
void out() {
}
};
eg add(eg v, int y) {
//cout << "adding " << y << endl;
v.y1 += y;v.y2 += y;v.b2 += y;
return v;
}
bool abmissible(eg e, int x) {
return (max(abs(x - e.x1), abs(x - e.x2))) == 1;
}
vector<eg> transition(int bm1, int bm2, int twoban) {
vector<eg> v;
if ((bm1 == 2) && (bm2 == 7)) {
v.pb(eg(4, 0, 4, 2, 5, 1));
v.pb(eg(2, 2, 4, 2, 3, 1));
v.pb(eg(4, 2, 6, 2, 5, 3));
return v;
}
if ((bm1 & bm2) == 0) return v;
if (bm1 & bm2 & 1) v.pb(eg(2, 0, 2, 2));
if (bm1 & bm2 & 2) v.pb(eg(4, 0, 4, 2));
if (bm1 & bm2 & 4) v.pb(eg(6, 0, 6, 2));
if ((bm2 & 3) == 3) v.pb(eg(2, 2, 4, 2));
if ((bm2 & 6) == 6) v.pb(eg(4, 2, 6, 2));
int vc = 0;
if (bm2 & 1) vc++;
if (bm2 & 2) vc++;
if (bm2 & 4) vc++;
for (auto i:v) i.out();
for (int i = 0;i < (1 << v.size());i++) {
int vk = (!!(i & 1)) + (!!(i & 2)) + (!!(i & 4)) + (!!(i & 8)) + (!!(i & 16));
if (vk != vc) continue;
vector<eg> sim;
for (int j = 0;j < v.size();j++) {
if (i & (1 << j)) sim.pb(v[j]);
}
dsu d;
for (auto e : sim) {
d.join(e.x1, e.x2, e.y1, e.y2);
}
if (!d.conn()) continue;
for (int j = 0;j < 64;j++) {
int c1 = j % 4, c2 = (j % 16) / 4, c3 = j / 16;
if (c1 == c2) continue;
if (c1 == c3) continue;
if (c3 == c2) continue;
if (twoban) {
if ((c1 == 2) || (c2 == 2) || (c3 == 2)) continue;
}
c1 = c1 * 2 + 1;
c2 = c2 * 2 + 1;
c3 = c3 * 2 + 1;
if (!abmissible(sim[0], c1)) continue;
if (vk > 1) { if (!abmissible(sim[1], c2)) continue; }
if (vk > 2) { if (!abmissible(sim[2], c3)) continue; }
sim[0].b1 = c1;if (vk == 1) return sim;
sim[1].b1 = c2;if (vk == 2) return sim;
sim[2].b1 = c3;
return sim;
}
}
return vector<eg>();
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int m = 1e9, M = -1e9;
for (auto i : y) m = min(i, m);
for (auto i : y) M = max(i, M);
vi stk((M - m + 2) / 2);
for (int i = 0;i < x.size();i++) {
stk[(y[i] - m) / 2] |= (1 << (x[i] / 2 - 1));
}
for (auto i : stk) {
if (!i) return 0;
}
vector<eg> vek;
if (stk[0] == 5) {
int ext = 0;
for (int i = 0;i < stk.size();i++) {
if (stk[i] == 7) {
for (int j = 0;j < i;j++) {
vek.push_back(eg(2, m + 2 * j, 2, m + 2 * j + 2, 1, m + 2 * j + 1));
vek.push_back(eg(6, m + 2 * j, 6, m + 2 * j + 2, 7, m + 2 * j + 1));
}
m += 2 * i;
vi st2;
ext = 1;
for (int j = i;j < stk.size();j++) st2.push_back(stk[j]);
stk = st2;
continue;
}
else if (stk[i] != 5) return 0;
}
if (!ext) return 0;
}
if ((stk[0]) & 3 == 3) vek.push_back(eg(2, m, 4, m, 3, m - 1));
if ((stk[0]) & 6 == 6) vek.push_back(eg(6, m, 4, m, 5, m - 1));
int past = 0;
for (int i = 0;i < stk.size() - 1;i++) {
vector<eg> v2 = transition(stk[i], stk[i + 1], past);
if ((stk[i] == 2) && (stk[i + 1] == 7)) past = 1;
if (v2.empty()) return 0;
for (auto k : v2) {
vek.pb(add(k, i * 2 + m));
}
}
map<pii, int> mpi;
for (int i = 0;i < x.size();i++) {
mpi[pii(x[i], y[i])] = i;
}
vi u, v, a, b;
for (auto i : vek) {
i.out();
int u1 = mpi[pii(i.x1, i.y1)];
int v1 = mpi[pii(i.x2, i.y2)];
u.pb(u1);v.pb(v1);
a.pb(i.b1);b.pb(i.b2);
}
build(u, v, a, b);
return 1;
}
Compilation message
parks.cpp: In function 'std::vector<eg> transition(int, int, int)':
parks.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<eg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int j = 0;j < v.size();j++) {
| ~~^~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int i = 0;i < x.size();i++) {
| ~~^~~~~~~~~~
parks.cpp:129:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (int i = 0;i < stk.size();i++) {
| ~~^~~~~~~~~~~~
parks.cpp:138:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for (int j = i;j < stk.size();j++) st2.push_back(stk[j]);
| ~~^~~~~~~~~~~~
parks.cpp:146:22: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
146 | if ((stk[0]) & 3 == 3) vek.push_back(eg(2, m, 4, m, 3, m - 1));
| ~~^~~~
parks.cpp:147:22: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
147 | if ((stk[0]) & 6 == 6) vek.push_back(eg(6, m, 4, m, 5, m - 1));
| ~~^~~~
parks.cpp:149:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for (int i = 0;i < stk.size() - 1;i++) {
| ~~^~~~~~~~~~~~~~~~
parks.cpp:158:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for (int i = 0;i < x.size();i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Pair u[0]=0 @(2, 2) and v[0]=0 @(2, 2) does not form a valid edge (distance != 2) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Pair u[0]=0 @(2, 2) and v[0]=0 @(2, 2) does not form a valid edge (distance != 2) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Pair u[0]=0 @(2, 2) and v[0]=0 @(2, 2) does not form a valid edge (distance != 2) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Pair u[0]=0 @(2, 2) and v[0]=0 @(2, 2) does not form a valid edge (distance != 2) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Pair u[0]=0 @(2, 2) and v[0]=0 @(2, 2) does not form a valid edge (distance != 2) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Pair u[0]=0 @(2, 2) and v[0]=0 @(2, 2) does not form a valid edge (distance != 2) |
| 2 |
Halted |
0 ms |
0 KB |
- |
