#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int construct_roads(vector<int> x,vector<int> y){
int n = x.size();
map<pair<int,int>,int> lookup;
for(int i=0;i<n;i++)lookup[{x[i],y[i]}]=i;
vector<int> u,v,a,b;
vector<vector<int>> adj(1);
vector<tuple<int,int,int,int>> edges;
edges.emplace_back(0,0,0,0);
int S = 0;
for(int i=0;i<n;i++){
if(lookup.count({x[i]+2,y[i]})){
S++;
adj.emplace_back();
edges.emplace_back(i,lookup[{x[i]+2,y[i]}],x[i]+1,y[i]-1);
if(lookup.count({x[i]+1,y[i]-1})){
adj[S].emplace_back(lookup[{x[i]+1,y[i]-1}]);
adj[lookup[{x[i]+1,y[i]-1}]].emplace_back(S);
} else lookup[{x[i]+1,y[i]-1}]=S;
S++;
adj.emplace_back();
edges.emplace_back(i,lookup[{x[i]+2,y[i]}],x[i]+1,y[i]+1);
if(lookup.count({x[i]+1,y[i]+1})){
adj[S].emplace_back(lookup[{x[i]+1,y[i]+1}]);
adj[lookup[{x[i]+1,y[i]+1}]].emplace_back(S);
} else lookup[{x[i]+1,y[i]+1}]=S;
adj[S].emplace_back(S-1);
adj[S-1].emplace_back(S);
}
if(lookup.count({x[i],y[i]-2})){
S++;
adj.emplace_back();
edges.emplace_back(i,lookup[{x[i],y[i]-2}],x[i]-1,y[i]-1);
if(lookup.count({x[i]-1,y[i]-1})){
adj[S].emplace_back(lookup[{x[i]-1,y[i]-1}]);
adj[lookup[{x[i]-1,y[i]-1}]].emplace_back(S);
} else lookup[{x[i]-1,y[i]-1}]=S;
S++;
adj.emplace_back();
edges.emplace_back(i,lookup[{x[i],y[i]-2}],x[i]+1,y[i]-1);
if(lookup.count({x[i]+1,y[i]-1})){
adj[S].emplace_back(lookup[{x[i]+1,y[i]-1}]);
adj[lookup[{x[i]+1,y[i]-1}]].emplace_back(S);
} else lookup[{x[i]+1,y[i]-1}]=S;
adj[S].emplace_back(S-1);
adj[S-1].emplace_back(S);
}
}
vector<int> colour(S+1,-1);
bool works = true;
function<void(int,int)> dfs = [&](int x,int col){
if(colour[x]!=-1){
if(colour[x]!=col)works=false;
return;
}
colour[x]=col;
for(int&i:adj[x])dfs(i,col^1);
};
for(int i=1;i<=S;i++)if(colour[i]==-1)dfs(i,0);
if(!works)return 0;
for(int i=1;i<=S;i++){
if(colour[i]==0)continue;
auto [c,d,e,f] = edges[i];
u.emplace_back(c);
v.emplace_back(d);
a.emplace_back(e);
b.emplace_back(f);
}
build(u,v,a,b);
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
