#include<bits/stdc++.h>
#include "parks.h"
#define MAXN 800007
using namespace std;
struct bench{
int from,to;
int a,b;
};
int n,curr,benches,br,k,comp[MAXN],ans[MAXN];
bool li[MAXN];
vector<int> v[MAXN],r[MAXN];
stack<int> st;
vector<bench> sol;
vector<int> A,B,C,D;
vector< pair<int,int> > ors;
map< pair<int,int>, int> mp;
void add(int x,int y,int z){
if(mp.find({x,y})==mp.end()){
mp[{x,y}]=z;
}
}
int op(int x){
if(x<400000)return x+400000;
return x-400000;
}
void dfs(int x){
li[x]=true;
for(int i=0;i<v[x].size();i++){
if(!li[v[x][i]])dfs(v[x][i]);
}
st.push(x);
}
void scc(int x){
comp[x]=k;
li[x]=true;
for(int i=0;i<r[x].size();i++){
if(!li[r[x][i]])scc(r[x][i]);
}
}
int construct_roads(vector<int> x,vector<int> y){
n=int(x.size());
for(int i=0;i<n;i++){
mp[{x[i],y[i]}]=i+1;
}
br=0;
for(int i=0;i<n;i++){
curr=mp[{x[i]-2,y[i]}];
if(curr!=0){
curr--;
add(x[i]-1,y[i]-1,br);
add(x[i]-1,y[i]+1,br+1);
ors.push_back({br,br+1});
if(mp[{x[i]-1,y[i]-1}]!=br)ors.push_back({op(mp[{x[i]-1,y[i]-1}]),op(br)});
if(mp[{x[i]-1,y[i]+1}]!=br+1)ors.push_back({op(mp[{x[i]-1,y[i]+1}]),op(br+1)});
br+=2;
}
curr=mp[{x[i],y[i]-2}];
if(curr!=0){
curr--;
add(x[i]-1,y[i]-1,br);
add(x[i]+1,y[i]-1,br+1);
ors.push_back({br,br+1});
if(mp[{x[i]-1,y[i]-1}]!=br)ors.push_back({op(mp[{x[i]-1,y[i]-1}]),op(br)});
if(mp[{x[i]+1,y[i]-1}]!=br+1)ors.push_back({op(mp[{x[i]+1,y[i]-1}]),op(br+1)});
br+=2;
}
}
if(br!=2*n-2)return 0;
for(int i=0;i<ors.size();i++){
v[op(ors[i].first)].push_back(ors[i].second);
r[ors[i].second].push_back(op(ors[i].first));
v[op(ors[i].second)].push_back(ors[i].first);
r[ors[i].first].push_back(op(ors[i].second));
}
for(int i=0;i<800000;i++){
if(!li[i])dfs(i);
}
for(int i=0;i<800000;i++)li[i]=false;
while(!st.empty()){
if(!li[st.top()]){
k++; scc(st.top());
}
st.pop();
}
for(int i=0;i<br;i++){
if(comp[i]==comp[op(i)])return 0;
if(comp[i]<comp[op(i)])ans[i]=0;
else ans[i]=1;
}
br=0;
for(int i=0;i<n;i++){
curr=mp[{x[i]-2,y[i]}];
if(curr!=0){
curr--;
if(ans[br]==0 and ans[br+1]==0)return -1;
if(ans[br]==1){
sol.push_back({curr,i,x[i]-1,y[i]-1});
}else{
sol.push_back({curr,i,x[i]-1,y[i]+1});
}
br+=2;
}
curr=mp[{x[i],y[i]-2}];
if(curr!=0){
curr--;
if(ans[br]==0 and ans[br+1]==0)return -1;
if(ans[br]==1){
sol.push_back({curr,i,x[i]-1,y[i]-1});
}else{
sol.push_back({curr,i,x[i]+1,y[i]-1});
}
br+=2;
}
}
for(int i=0;i<sol.size();i++){
A.push_back(sol[i].from);
B.push_back(sol[i].to);
C.push_back(sol[i].a);
D.push_back(sol[i].b);
}
build(A,B,C,D);
}
/*
int main(){
construct_roads({4, 4, 6, 4, 2}, {4, 6, 4, 2, 4});
}
*/
Compilation message
parks.cpp: In function 'void dfs(int)':
parks.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
parks.cpp: In function 'void scc(int)':
parks.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0;i<r[x].size();i++){
| ~^~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i=0;i<ors.size();i++){
| ~^~~~~~~~~~~
parks.cpp:145:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bench>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for(int i=0;i<sol.size();i++){
| ~^~~~~~~~~~~
parks.cpp:152:18: warning: control reaches end of non-void function [-Wreturn-type]
152 | build(A,B,C,D);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
70 ms |
91124 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
70 ms |
91124 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
70 ms |
91124 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
70 ms |
91124 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
70 ms |
91124 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
70 ms |
91124 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
