#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class Disjoint{
vector<int> parent,sz;
public:
Disjoint(int n){
parent.resize(n+1);
sz.resize(n+1,1);
for(int i=0;i<n+1;i++) parent[i]=i;
}
int findPar(int node){
if(parent[node]==node) return node;
return parent[node] = findPar(parent[node]);
}
void uz(int node1,int node2){
int p1 = findPar(node1);
int p2 = findPar(node2);
if(p1==p2) return;
if(sz[p1]>sz[p2]){
parent[p2]=parent[p1];
sz[p1] += sz[p2];
}else{
parent[p1]=parent[p2];
sz[p2] += sz[p1];
}
}
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
ll n = x.size();
Disjoint ds(n+10);
map<ll,map<ll,ll>> hash1;
map<ll,pair<ll,ll>> hash2;
map<ll,ll> picked;
vector<vector<int>> arr(n,vector<int>(3));
int crInd = 1;
for(int i=0;i<n;i++){
hash1[x[i]][y[i]]=crInd;
hash2[crInd] = {x[i],y[i]};
arr[i][0] = x[i];
arr[i][1] = y[i];
arr[i][2] = i;
crInd++;
}
sort(arr.begin(),arr.end());
vector<int> u, v, a, b;
for(int i=0;i<n;i++){
int crX = arr[i][0];
int crY = arr[i][1];
int in = arr[i][2];
//cout<<crX<<" "<<crY<<endl;
//cout<<hash1[crX][crY+2]<<endl;
if(hash1[crX+2][crY]){
if(ds.findPar(in)!=ds.findPar(hash1[crX+2][crY]-1)){
ds.uz(i,hash1[crX+2][crY]-1);
u.push_back(in);
v.push_back(hash1[crX+2][crY]-1);
}
}
if(hash1[crX-2][crY]){
//cout<<"x"<<endl;
if(ds.findPar(in)!=ds.findPar(hash1[crX-2][crY]-1)){
ds.uz(i,hash1[crX-2][crY]-1);
u.push_back(in);
v.push_back(hash1[crX-2][crY]-1);
}
}
if(hash1[crX][crY+2]){
//cout<<"x"<<endl;
if(ds.findPar(in)!=ds.findPar(hash1[crX][crY+2]-1)){
ds.uz(i,hash1[crX][crY+2]-1);
u.push_back(in);
v.push_back(hash1[crX][crY+2]-1);
}
}
if(hash1[crX][crY-2]){
//cout<<"x"<<endl;
if(ds.findPar(in)!=ds.findPar(hash1[crX][crY-2]-1)){
ds.uz(i,hash1[crX][crY-2]-1);
u.push_back(in);
v.push_back(hash1[crX][crY-2]-1);
}
}
}
set<int> p;
for(int i=0;i<n;i++){
p.insert(ds.findPar(i));
}
//cout<<p.size()<<endl;
if(p.size()!=1){
return 0;
}
map<ll,map<ll,ll>> oc;
for(int i=0;i<n-1;i++){
int crX = x[u[i]];
int crY = y[u[i]];
int nxX = x[v[i]];
int nxY = y[v[i]];
if(crX == nxX){
ll bv = (crY + nxY)/2;
if(oc[crX + 1][bv]){
a.push_back(crX - 1);
b.push_back(bv);
oc[crX - 1][bv] = 1;
}else{
a.push_back(crX + 1);
b.push_back(bv);
oc[crX + 1][bv] = 1;
}
}else{
ll av = (crX + nxX) / 2;
if(oc[av][crY + 1]){
a.push_back(av);
b.push_back(crY - 1);
oc[av][crY - 1] = 1;
}else{
a.push_back(av);
b.push_back(crY + 1);
oc[av][crY + 1] = 1;
}
}
}
// bool f=1;
// for(ll i=0;i<n-1;i++){
// if((arr[i+1].first - arr[i].first) != 2){
// return 0;
// }
// u.push_back(arr[i+1].second);
// v.push_back(arr[i].second);
// a.push_back(1);
// b.push_back((arr[i+1].first+arr[i].first)/2);
// }
build(u, v, a, b);
return 1;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
432 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
130 ms |
43508 KB |
Wrong answer detected in grader |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
432 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
130 ms |
43508 KB |
Wrong answer detected in grader |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
432 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
130 ms |
43508 KB |
Wrong answer detected in grader |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
432 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
130 ms |
43508 KB |
Wrong answer detected in grader |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
432 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
130 ms |
43508 KB |
Wrong answer detected in grader |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
432 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
130 ms |
43508 KB |
Wrong answer detected in grader |
| 10 |
Halted |
0 ms |
0 KB |
- |
