#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int N, par[maxn];
int find_leader(int v)
{
return (v == par[v]) ? v : (par[v] = find_leader(par[v]));
}
bool unite(int v, int u)
{
v = find_leader(v);
u = find_leader(u);
if (v == u)
return false;
par[u] = v;
return true;
}
struct edge
{
int v, u, a, b;
pair < pair < int, int >, pair < int, int > > db;
};
vector < edge > edges;
map < pair < int, int >, int > mp;
map < pair < int, int >, set < int > > pos;
void add_edge(pair < int, int > p, pair < int, int > q, int i, int j)
{
edge cur;
cur.v = i;
cur.u = j;
edges.push_back(cur);
if (p.first > q.first)
swap(p, q);
if (p.second > q.second)
swap(p, q);
pair < int, int > curd;
if (p.first == q.first)
{
pos[make_pair(p.first - 1, p.second + 1)].insert((int)edges.size() - 1);
pos[ {p.first + 1,p.second + 1}].insert((int)edges.size() - 1);
edges.back().db = {{p.first - 1, p.second + 1}, {p.first + 1, p.second + 1}};
}
else
{
pos[ {p.first + 1,p.second - 1}].insert((int)edges.size() - 1);
pos[ {p.first + 1, p.second + 1}].insert((int)edges.size() - 1);
edges.back().db = {{p.first + 1, p.second + 1}, {p.first + 1, p.second - 1}};
}
}
vector < int > from, to, cx, cy;
int construct_roads(std::vector<int> x, std::vector<int> y)
{
N = x.size();
for (int i = 0; i < N; i ++)
{
par[i] = i;
mp[ {x[i], y[i]}] = i + 1;
}
for (int i = 0; i < N; i ++)
{
for (int dx = -2; dx <= 2; dx ++)
{
if (abs(dx) < 2)
continue;
pair < int, int > nb = {x[i], y[i]};
nb.first += dx;
if (mp[nb] != 0)
{
if (unite(mp[nb] - 1, i))
{
add_edge({x[i], y[i]}, nb, i, mp[nb] - 1);
}
}
nb.first -= dx;
nb.second += dx;
if (mp[nb] != 0)
{
if (unite(mp[nb] - 1, i))
{
add_edge({x[i], y[i]}, nb, i, mp[nb] - 1);
}
}
}
}
/**for (int i = 0; i < edges.size(); i ++)
{
cout << edges[i].v << " " << edges[i].u << " " << edges[i].db.first.first << " " << edges[i].db.first.second << " " << edges[i].db.second.first << " " << edges[i].db.second.second << endl;
//if (pos[edges[i].db])
}*/
set < pair < int, int > > q[5];
for (pair < pair < int, int >, set < int > > cur : pos)
{
q[cur.second.size()].insert(cur.first);
}
for (int step = 0; step < edges.size(); step ++)
{
int pt = 1;
while(q[pt].empty())
{
/// cout << "pt " << pt << endl;
pt ++;
}
pair < int, int > cur = *q[pt].begin();
int index = *pos[cur].begin();
edges[index].a = cur.first;
edges[index].b = cur.second;
pair < int, int > d1 = edges[index].db.first;
pair < int, int > d2 = edges[index].db.second;
if (pos[d1].find(index) != pos[d1].end())
{
q[pos[d1].size()].erase(d1);
pos[d1].erase(index);
if (d1 != cur)
q[pos[d1].size()].insert(d1);
}
if (pos[d2].find(index) != pos[d2].end())
{
q[pos[d2].size()].erase(d2);
pos[d2].erase(index);
if (d2 != cur)
q[pos[d2].size()].insert(d2);
}
}
from.resize(edges.size());
to.resize(edges.size());
cx.resize(edges.size());
cy.resize(edges.size());
for (int i = 0; i < edges.size(); i ++)
{
from[i] = edges[i].v;
to[i] = edges[i].u;
cx[i] = edges[i].a;
cy[i] = edges[i].b;
}
build(from, to, cx, cy);
/**for (int i = 0; i < edges.size(); i ++)
{
cout << edges[i].v << " " << edges[i].u << endl;
}*/
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:110:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (int step = 0; step < edges.size(); step ++)
| ~~~~~^~~~~~~~~~~~~~
parks.cpp:153:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for (int i = 0; i < edges.size(); i ++)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
