#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
const int N = 3e5+100;
struct Dsu{
vi p, s;
void init(int n){
p.resize(n);
s.resize(n,1);
for(int i = 0; i < n; ++i) p[i]=i;
}
int find(int v){
if(p[v]==v) return v;
return p[v]=find(p[v]);
}
void merge(int a, int b){
a=find(a);b=find(b);
if(a!=b){
if(s[a]>s[b]) swap(a,b);
p[a] = b;
s[b] += s[a];
}
}
};
int arr[4][2] = {{2, 0}, {-2, 0}, {0, 2}, {0, -2}};
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
std::vector<int> U, V, a, b;
// u.push_back(0);
// v.push_back(1);
// a.push_back(x[0]+1);
// b.push_back(y[0]-1);
vector<array<int, 4>> g;
int n = x.size();
Dsu d; d.init(n);
map<pair<int, int>, int> m;
map<pair<int, int>, int> used;
for(int i = 0; i < n; ++i){
m[{x[i], y[i]}] = i + 1;
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < 4; ++j){
int nx = x[i] + arr[j][0];
int ny = y[i] + arr[j][1];
if(m.find({nx, ny}) != m.end()){
int id = m[{nx, ny}];
if(id > i) continue;
int yy = y[i] + ny >> 1;
int xx = x[i] + nx >> 1;
int X = x[i], Y = y[i];
// cout << X << ' ' << Y << ' ' << nx << ' ' << ny << '\n';
if(nx < X) swap(X, nx), swap(Y, ny);
if(ny < Y) swap(X, nx), swap(Y, ny);
if(abs(nx - X) == 2){
if((X/2+Y/2) % 2){
g.pb({xx, Y - 1, i + 1, id});
}else{
g.pb({xx, Y + 1, i + 1, id});
}
}else{
if((X/2 + Y/2) % 2 == 0){
g.pb({X - 1, yy, i + 1, id});
}else{
g.pb({X + 1, yy, i + 1, id});
}
}
}
}
}
sort(all(g));
for(int i = 0; i < g.size(); ++i){
int u = g[i][2], v = g[i][3];
if(d.find(u) != d.find(v) && used[{g[i][0], g[i][1]}] == 0){
d.merge(u, v);
U.pb(u - 1);
V.pb(v - 1);
a.pb(g[i][0]);
b.pb(g[i][1]);
used[{g[i][0], g[i][1]}] = 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:61:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int yy = y[i] + ny >> 1;
parks.cpp:62:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
62 | int xx = x[i] + nx >> 1;
parks.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i = 0; i < g.size(); ++i){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
