#include <bits/stdc++.h>
#include "parks.h"
#define pb push_back
#define f first
#define s second
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef long double ld;
const ll oo = 1e9;
const ld eps = (ld)1 / oo;
const ll N = 2e5 + 100;
const ll M = 1e6;
const int step[4][2] = {{0, 2}, {0, -2}, {2, 0}, {-2, 0}};
vector <pair<int, int> > ans;
int mrk[N];
map <int, int> mp[N];
map <int, int> mp1[N];
pair<int, int> coord[N];
void Rec(int x)
{
for (int i = 0; i < 4; i++)
{
int x1 = coord[x].f + step[i][0];
int y1 = coord[x].s + step[i][1];
if (mp[x1][y1] != 0)
{
int nm = mp[x1][y1] - 1;
if (!mrk[nm])
{
ans.pb({x, nm});
mrk[nm] = 1;
Rec(nm);
}
}
}
}
//void build(vector <int> u, vector <int> v, vector <int> a, vector <int> b)
//{
// for (int i = 0; i < u.size(); i++) cout << u[i] << " " << v[i] << " " << a[i] << " " << b[i] << endl;
//}
set <pair<int, pair<int, int> > > ms;
int construct_roads (vector<int> x, vector<int> y) {
std::vector<int> u, v, a, b;
int n = x.size();
for (int i = 0; i < n; i++) coord[i] = {x[i], y[i]};
for (int i = 0; i < n; i++) mp[x[i]][y[i]] = i + 1;
mrk[0] = 1;
Rec(0);
if (ans.size() != n - 1) return 0;
a.resize(n - 1);
b.resize(n - 1);
u.resize(n - 1);
v.resize(n - 1);
for (int i = 0; i < N; i++) mp[i].clear();
for (int i = 0; i < n - 1; i++)
{
int x1 = (x[ans[i].f] + x[ans[i].s]) / 2;
int y1 = (y[ans[i].f] + y[ans[i].s]) / 2;
for (int j = 0; j < 4; j++)
{
int x2 = x1 + step[j][0] / 2;
int y2 = y1 + step[j][1] / 2;
if ((x2 & 1) && (y2 & 1))
{
if (mp[x2][y2] != 0)
{
ms.erase({mp[x2][y2], {x2, y2}});
}
mp[x2][y2]++;
ms.insert({mp[x2][y2], {x2, y2}});
}
}
mp1[x1][y1] = i + 1;
}
while (!ms.empty())
{
pair<int, pair<int, int> > c = *ms.begin();
ms.erase(ms.begin());
if (c.f == 0) continue;
int x1 = c.s.f, y1 = c.s.s;
mp[x1][y1] = 0;
for (int i = 0; i < 4; i++)
{
int x2 = x1 + step[i][0] / 2;
int y2 = y1 + step[i][1] / 2;
if (mp1[x2][y2] != 0)
{
int nom = mp1[x2][y2] - 1;
a[nom] = x1;
b[nom] = y1;
mp1[x2][y2] = 0;
for (int j = 0; j < 4; j++)
{
int x3 = x2 + step[j][0] / 2;
int y3 = y2 + step[j][1] / 2;
if ((x3 & 1) && (y3 & 1))
{
if (mp[x3][y3] != 0)
{
ms.erase({mp[x3][y3], {x3, y3}});
mp[x3][y3]--;
ms.insert({mp[x3][y3], {x3, y3}});
}
}
}
break;
}
}
}
for (int i = 0; i < n; i++)
if (a[i] == 0 || b[i] == 0) return 0;
for (int i = 0; i < n - 1; i++)
{
u[i] = ans[i].f;
v[i] = ans[i].s;
}
build(u, v, a, b);
return 1;
}
/*
1
4
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
*/
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:60:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
60 | if (ans.size() != n - 1) return 0;
| ~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
38476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
38476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
38476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
38476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
38476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
38476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
