#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include "parks.h"
using namespace std;
map<pair<int,int>,int>d,vis;
vector<pair<int,int>>z;
// queue<pair<int,int>>Q;
int x1=0,y11=0;
bool check(int x,int y)
{
if (d.find({x,y})!=d.end()&&!vis[{x,y}])
{
vis[{x,y}]=1;
z.push_back({d[{x1,y11}],d[{x,y}]});
return 1;
}
return 0;
}
vector<pair<int,int>>i={{0,-2},{0,2},{2,0},{-2,0}};
void bfs(int x,int y)
{
vis[{x,y}]=1;
for (int j=0;j<4;j++)
{
x1=x;
y11=y;
if (check(x+i[j].first,y+i[j].second));
bfs(x+i[j].first,y+i[j].second);
}
}
int construct_roads(vector<int> x, vector<int> y)
{
int n=x.size();
for (int i=0;i<n;i++)
d[{x[i],y[i]}]=i;
int reqx=1e9+10,reqy=1e9+10;
for (int i=0;i<n;i++)
{
if (x[i]<reqx)
{
reqx=x[i];
reqy=y[i];
}
else if (x[i]==reqx&&reqy>y[i])
reqy=y[i];
}
sort(begin(i),end(i));
do
{
vis={};
z={};
// Q={};
bfs(reqx,reqy);
bool w=1;
for (int i=0;i<n;i++)
{
if (!vis[{x[i],y[i]}])
w=0;
}
vis={};
vector<int>u,v,a,b;
for (auto i:z)
{
u.push_back(i.first);
v.push_back(i.second);
pair<int,int>r,q;
r.first=x[i.first],r.second=y[i.first];
q.first=x[i.second],q.second=y[i.second];
if (r.first-q.first==0)
{
a.push_back(r.first-1);
b.push_back((r.second+q.second)/2);
if (vis[{a.back(),b.back()}])
{
a.pop_back();
a.push_back(r.first+1);
if (vis[{a.back(),b.back()}])
w=0;
vis[{a.back(),b.back()}]=1;
}
else
vis[{a.back(),b.back()}]=1;
}
else
{
a.push_back((r.first+q.first)/2);
b.push_back(r.second-1);
if (vis[{a.back(),b.back()}])
{
b.pop_back();
b.push_back(r.second+1);
if (vis[{a.back(),b.back()}])
w=0;
vis[{a.back(),b.back()}]=1;
}
else
vis[{a.back(),b.back()}]=1;
}
}
if (w==1)
{
build(u,v,a,b);
return 1;
}
}
while(next_permutation(begin(i),end(i)));
return 0;
}
Compilation message
parks.cpp: In function 'void bfs(int, int)':
parks.cpp:29:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
29 | if (check(x+i[j].first,y+i[j].second));
| ^~
parks.cpp:30:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
30 | bfs(x+i[j].first,y+i[j].second);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3608 ms |
1505000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3608 ms |
1505000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3608 ms |
1505000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3608 ms |
1505000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3608 ms |
1505000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3608 ms |
1505000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
