#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
int dx[4] = {2,0,-2,0};
int dy[4] = {0,2,0,-2};
struct S {
int x,y;
int dir;
}s_;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
const int mxN = (int)2e5 + 5;
int construct_roads(std::vector<int> x, std::vector<int> y) {
const int n = (int)x.size();
for(int A = 0 ; A < n ; A++) {
map<pair<int,int>,int>mp;
for(int i = 0 ; i < n ; i++)
mp[{x[i],y[i]}] = i;
vector<int>u(n-1),v(n-1),a(n-1),b(n-1);
set<pair<int,int>>processed;
stack<S>s;
s_.x = x[A], s_.y = y[A], s_.dir = 0;
processed.insert({x[A], y[A]});
s.push(s_);
int P = 0;
while(!s.empty()) {
auto node = s.top();
s.pop();
int x = node.x, y = node.y, dir = node.dir;
bool in_order = 0;
if(mp.count({x + dx[dir], y + dy[dir]})) in_order = 1;
int i = dir;
int ii = mp[{x,y}];
int p_ = P;
if(!in_order) {
dir--;
i--;
dir += 4;
i += 4;
dir %= 4;
i %= 4;
} else {
dir++;
i++;
dir += 4;
i += 4;
dir %= 4;
i %= 4;
}
do {
if(in_order) {
if(mp.count({x + dx[i], y + dy[i]}) && !processed.count({x + dx[i], y + dy[i]})) {
if(dx[i] == 0 && dy[i] == 2) {
if(!processed.count({x+1,y + dy[i]/2}))
a[P] = x+1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
else if(!processed.count({x-1,y + dy[i]/2}))
a[P] = x-1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
} else if(dx[i] == 0 && dy[i] == -2) {
if(!processed.count({x-1,y + dy[i]/2}))
a[P] = x-1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
else if(!processed.count({x+1,y + dy[i]/2}))
a[P] = x+1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
} else if(dy[i] == 0 && dx[i] == 2) {
if(!processed.count({x + dx[i]/2, y-1}))
a[P] = x + dx[i]/2, b[P] = y-1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
else if(!processed.count({x + dx[i]/2, y+1}))
a[P] = x + dx[i]/2, b[P] = y+1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
} else if(dy[i] == 0 && dx[i] == -2) {
if(!processed.count({x + dx[i]/2, y+1}))
a[P] = x + dx[i]/2, b[P] = y+1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
else if(!processed.count({x + dx[i]/2, y-1}))
a[P] = x + dx[i]/2, b[P] = y-1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
}
}
} else {
if(mp.count({x + dx[i], y + dy[i]}) && !processed.count({x + dx[i], y + dy[i]})) {
if(dx[i] == 0 && dy[i] == 2) {
if(!processed.count({x-1,y + dy[i]/2}))
a[P] = x-1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
else if(!processed.count({x+1,y + dy[i]/2}))
a[P] = x+1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
} else if(dx[i] == 0 && dy[i] == -2) {
if(!processed.count({x+1,y + dy[i]/2}))
a[P] = x+1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
else if(!processed.count({x-1,y + dy[i]/2}))
a[P] = x-1, b[P] = y + dy[i]/2, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
} else if(dy[i] == 0 && dx[i] == 2) {
if(!processed.count({x + dx[i]/2, y+1}))
a[P] = x + dx[i]/2, b[P] = y+1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
else if(!processed.count({x + dx[i]/2, y-1}))
a[P] = x + dx[i]/2, b[P] = y-1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
} else if(dy[i] == 0 && dx[i] == -2) {
if(!processed.count({x + dx[i]/2, y-1}))
a[P] = x + dx[i]/2, b[P] = y-1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
else if(!processed.count({x + dx[i]/2, y+1}))
a[P] = x + dx[i]/2, b[P] = y+1, u[P] = ii, v[P] = mp[{x + dx[i], y + dy[i]}], s_.x = x + dx[i], s_.y = y + dy[i], s_.dir = i, s.push(s_), processed.insert({x + dx[i], y + dy[i]}),processed.insert({a[P],b[P]}),P++;
}
}
}
if(in_order) i++,i%=4;
else i--, i+=4, i%= 4;
} while(i != dir);
}
if(P < n-1)
continue;
build(u,v,a,b);
return 1;
}
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:45:17: warning: unused variable 'p_' [-Wunused-variable]
45 | int p_ = P;
| ^~
parks.cpp:125:1: warning: control reaches end of non-void function [-Wreturn-type]
125 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
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) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
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) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
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) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
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) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
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) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
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) |
| 4 |
Halted |
0 ms |
0 KB |
- |
