#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
const int nax = 200000;
vector<int>g[nax];
bool vis[nax];
int par[nax], sz[nax];
void trav(int v) {
vis[v] = 1;
for(int u : g[v]) if(!vis[u]) {
trav(u);
}
}
int find(int v) {
return par[v] = (v==par[v]) ? v : find(par[v]);
}
void unite(int u, int v) {
u = find(u), v = find(v);
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
par[v] = u;
}
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
map<pair<int,int>, int>ft;
for(int i=0; i<n; ++i) {
ft[{x[i], y[i]}] = i;
}
int dx[] = {2, -2, 0, 0};
int dy[] = {0, 0, 2, -2};
vector<int>u, v, a, b;
map<pair<int,int>, int>ben;
for(int i=0; i<n; ++i) {
par[i] = i, sz[i] = 1;
}
for(int i=0; i<n; ++i) {
for(int j=0; j<4; ++j) {
int nx = x[i] + dx[j], ny = y[i] + dy[j];
if(ft.count(make_pair(nx, ny))) {
if(find(i) == find(ft[{nx, ny}])) continue;
if(j < 2) { //horizontal
if((x[i] + nx >> 1) < 4) {
if(!ben.count(make_pair(x[i] + nx >> 1, ny - 1))) {
ben[{x[i] + nx >> 1, ny - 1}] = 1;
a.push_back(x[i] + nx >> 1);
b.push_back(ny - 1);
} else if(!ben.count(make_pair(x[i] + nx >> 1, ny + 1))) {
ben[{x[i] + nx >> 1, ny + 1}] = 1;
a.push_back(x[i] + nx >> 1);
b.push_back(ny + 1);
} else assert(0);
} else {
if(!ben.count(make_pair(x[i] + nx >> 1, ny + 1))) {
ben[{x[i] + nx >> 1, ny + 1}] = 1;
a.push_back(x[i] + nx >> 1);
b.push_back(ny + 1);
} else if(!ben.count(make_pair(x[i] + nx >> 1, ny - 1))) {
ben[{x[i] + nx >> 1, ny - 1}] = 1;
a.push_back(x[i] + nx >> 1);
b.push_back(ny - 1);
} else assert(0);
}
} else { //vertical
if(x[i]==2) {
a.push_back(x[i] - 1);
b.push_back(y[i] + ny >> 1);
} else if(x[i]==6) {
a.push_back(x[i] + 1);
b.push_back(y[i] + ny >> 1);
} else {
continue;
}
}
g[i].push_back(ft[{nx, ny}]);
unite(i, ft[{nx, ny}]);
u.push_back(i);
v.push_back(ft[{nx, ny}]);
}
}
}
for(int i=0; i<n; ++i) {
for(int j=2; j<4; ++j) {
int nx = x[i] + dx[j], ny = y[i] + dy[j];
if(ft.count(make_pair(nx, ny))) {
if(find(i) == find(ft[{nx, ny}])) continue;
g[i].push_back(ft[{nx, ny}]);
unite(i, ft[{nx, ny}]);
u.push_back(i);
v.push_back(ft[{nx, ny}]);
if(!ben.count(make_pair(nx-1, y[i] + ny >> 1))) {
ben[{nx-1, y[i] + ny >> 1}] = 1;
a.push_back(nx-1);
b.push_back(y[i] + ny >> 1);
} else if(!ben.count(make_pair(nx+1, y[i] + ny >> 1))) {
ben[{nx+1, y[i] + ny >> 1}] = 1;
a.push_back(nx+1);
b.push_back(y[i] + ny >> 1);
} else assert(0);
}
}
}
trav(0);
for(int i=0; i<n; ++i) if(!vis[i]) {
return 0;
}
build(u, v, a, b);
return 1;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:52:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | if((x[i] + nx >> 1) < 4) {
parks.cpp:53:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | if(!ben.count(make_pair(x[i] + nx >> 1, ny - 1))) {
parks.cpp:54:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | ben[{x[i] + nx >> 1, ny - 1}] = 1;
parks.cpp:55:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | a.push_back(x[i] + nx >> 1);
parks.cpp:57:61: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | } else if(!ben.count(make_pair(x[i] + nx >> 1, ny + 1))) {
parks.cpp:58:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | ben[{x[i] + nx >> 1, ny + 1}] = 1;
parks.cpp:59:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | a.push_back(x[i] + nx >> 1);
parks.cpp:64:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | if(!ben.count(make_pair(x[i] + nx >> 1, ny + 1))) {
parks.cpp:65:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | ben[{x[i] + nx >> 1, ny + 1}] = 1;
parks.cpp:66:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | a.push_back(x[i] + nx >> 1);
parks.cpp:69:61: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | } else if(!ben.count(make_pair(x[i] + nx >> 1, ny - 1))) {
parks.cpp:70:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | ben[{x[i] + nx >> 1, ny - 1}] = 1;
parks.cpp:71:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | a.push_back(x[i] + nx >> 1);
parks.cpp:78:42: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | b.push_back(y[i] + ny >> 1);
parks.cpp:81:42: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
81 | b.push_back(y[i] + ny >> 1);
parks.cpp:104:52: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
104 | if(!ben.count(make_pair(nx-1, y[i] + ny >> 1))) {
parks.cpp:105:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | ben[{nx-1, y[i] + ny >> 1}] = 1;
parks.cpp:107:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
107 | b.push_back(y[i] + ny >> 1);
parks.cpp:108:59: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
108 | } else if(!ben.count(make_pair(nx+1, y[i] + ny >> 1))) {
parks.cpp:109:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
109 | ben[{nx+1, y[i] + ny >> 1}] = 1;
parks.cpp:111:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
111 | b.push_back(y[i] + ny >> 1);
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 9 |
Incorrect |
212 ms |
17268 KB |
Solution announced impossible, but it is possible. |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 9 |
Incorrect |
212 ms |
17268 KB |
Solution announced impossible, but it is possible. |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 9 |
Incorrect |
212 ms |
17268 KB |
Solution announced impossible, but it is possible. |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 9 |
Incorrect |
212 ms |
17268 KB |
Solution announced impossible, but it is possible. |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 9 |
Incorrect |
212 ms |
17268 KB |
Solution announced impossible, but it is possible. |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 9 |
Incorrect |
212 ms |
17268 KB |
Solution announced impossible, but it is possible. |
| 10 |
Halted |
0 ms |
0 KB |
- |
