#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > vec[200005], edge;
vector<int> adj[200005], U, V, A, B;
map<pair<int, int>, bool> mp;
bool visited[20005];
queue<int> q;
int construct_roads(vector<int> X, vector<int> Y)
{
int N=X.size();
for (int i=0; i<N; i++)
vec[Y[i]].push_back({X[i], i});
bool ok=0;
for (int i=2; i<=2e5; i+=2)
{
if (vec[i].empty())
continue;
sort(vec[i].begin(), vec[i].end());
if (ok)
{
if (vec[i].size()==1)
{
int ind=-1;
for (int j=0; j<vec[i-2].size(); j++)
{
if (vec[i-2][j].first==vec[i][0].first)
{
ind=j;
break;
}
}
if (ind==-1)
return 0;
edge.push_back({vec[i-2][ind].second, vec[i][0].second});
}
else if (vec[i].size()==2)
{
if (vec[i][0].first==2 && vec[i][1].first==4)
{
int ind=-1;
for (int j=0; j<vec[i-2].size(); j++)
{
if (vec[i-2][j].first<=4)
{
ind=j;
break;
}
}
if (ind==-1)
return 0;
if (vec[i-2][ind].first==2)
edge.push_back({vec[i-2][ind].second, vec[i][0].second});
else
edge.push_back({vec[i-2][ind].second, vec[i][1].second});
}
else if (vec[i][0].first==4 && vec[i][1].first==6)
{
int ind=-1;
for (int j=0; j<vec[i-2].size(); j++)
if (vec[i-2][j].first>=4)
ind=j;
if (ind==-1)
return 0;
if (vec[i-2][ind].first==4)
edge.push_back({vec[i-2][ind].second, vec[i][0].second});
else
edge.push_back({vec[i-2][ind].second, vec[i][1].second});
}
else
{
for (int k=0; k<2; k++)
{
int ind=-1;
for (int j=0; j<vec[i-2].size(); j++)
{
if (vec[i-2][j].first==vec[i][k].first)
{
ind=j;
break;
}
}
if (ind==-1)
return 0;
edge.push_back({vec[i-2][ind].second, vec[i][k].second});
}
}
}
else
{
if (vec[i-2].empty())
return 0;
if (vec[i-2][0].first==2)
edge.push_back({vec[i-2][0].second, vec[i][0].second});
else if (vec[i-2][0].first==4)
edge.push_back({vec[i-2][0].second, vec[i][1].second});
else
edge.push_back({vec[i-2][0].second, vec[i][2].second});
}
}
if (vec[i].size()==2)
{
if (vec[i][0].first+2==vec[i][1].first)
edge.push_back({vec[i][0].second, vec[i][1].second});
}
else if (vec[i].size()==3)
{
edge.push_back({vec[i][0].second, vec[i][1].second});
edge.push_back({vec[i][1].second, vec[i][2].second});
}
ok=1;
}
for (int i=0; i<edge.size(); i++)
{
int u=edge[i].first, v=edge[i].second;
adj[u].push_back(v);
adj[v].push_back(u);
U.push_back(u);
V.push_back(v);
if (X[u]==X[v])
{
if (mp[{X[u]-1, Y[u]+1}])
{
A.push_back(X[u]+1);
B.push_back(Y[u]+1);
mp[{X[u]+1, Y[u]+1}]=1;
}
else
{
A.push_back(X[u]-1);
B.push_back(Y[u]+1);
mp[{X[u]-1, Y[u]+1}]=1;
}
}
else
{
if (mp[{X[u]+1, Y[u]-1}])
{
A.push_back(X[u]+1);
B.push_back(Y[u]+1);
mp[{X[u]+1, Y[u]+1}]=1;
}
else
{
A.push_back(X[u]+1);
B.push_back(Y[u]-1);
mp[{X[u]+1, Y[u]-1}]=1;
}
}
}
q.push(0);
visited[0]=1;
while (!q.empty())
{
int u=q.front();
q.pop();
for (int v:adj[u])
{
if (!visited[v])
{
q.push(v);
visited[v]=1;
}
}
}
for (int i=0; i<N; i++)
if (!visited[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:25:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int j=0; j<vec[i-2].size(); j++)
| ~^~~~~~~~~~~~~~~~
parks.cpp:42:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int j=0; j<vec[i-2].size(); j++)
| ~^~~~~~~~~~~~~~~~
parks.cpp:60:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int j=0; j<vec[i-2].size(); j++)
| ~^~~~~~~~~~~~~~~~
parks.cpp:75:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int j=0; j<vec[i-2].size(); j++)
| ~^~~~~~~~~~~~~~~~
parks.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for (int i=0; i<edge.size(); i++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 7 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 8 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 9 |
Incorrect |
90 ms |
26224 KB |
Solution announced impossible, but it is possible. |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 7 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 8 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 9 |
Incorrect |
90 ms |
26224 KB |
Solution announced impossible, but it is possible. |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 7 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 8 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 9 |
Incorrect |
90 ms |
26224 KB |
Solution announced impossible, but it is possible. |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 7 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 8 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 9 |
Incorrect |
90 ms |
26224 KB |
Solution announced impossible, but it is possible. |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 7 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 8 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 9 |
Incorrect |
90 ms |
26224 KB |
Solution announced impossible, but it is possible. |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 7 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 8 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 9 |
Incorrect |
90 ms |
26224 KB |
Solution announced impossible, but it is possible. |
| 10 |
Halted |
0 ms |
0 KB |
- |
