This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |