#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
int n,x[mxn],y[mxn],p[mxn],sz[mxn];
int ax[4]={1,1,-1,-1};
int ay[4]={-1,1,1,-1};
vector<pii>vt;
map<pii,int>mp;
int fnd(int u){
if(p[u]==u) return u;
return p[u]=fnd(p[u]);
}
void Union(int u,int v){
u=fnd(u);
v=fnd(v);
if(u!=v){
if(sz[u]>sz[v]) swap(u,v);
sz[u]+=sz[v];
p[v]=u;
}
}
bool cmp(pii a,pii b){
return a.F+a.S<b.F+b.S;
}
int construct_roads(vector<int> xx, vector<int> yy) {
n=xx.size();
if(n==1){
build({},{},{},{});
return 1;
}
for(int i=0;i<n;i++){
vt.pb({xx[i],yy[i]});
mp[{xx[i],yy[i]}]=i+1;
x[i+1]=xx[i];
y[i+1]=yy[i];
}
set<pii>st;
for(int i=1;i<=n;i++){
p[i]=i;
sz[i]=1;
}
vector<int>idxl,idxr,posl,posr;
sort(all(vt),cmp);
for(int i=1;i<n;i++){
int l=vt[i].F,r=vt[i].S;
int a=l-2,b=r;
int c=l,d=r-2;
int u=mp[{l,r}];
int idx=mp[{a,b}];
int idx2=mp[{c,d}];
if(idx&&idx2){
int p1=(a+l)/2,p2=(b+r)/2;
if(p1%2){
if(!st.count({p1,p2-1})){
idxl.pb(u-1);
idxr.pb(idx-1);
posl.pb(p1);
posr.pb(p2-1);
st.insert({p1,p2-1});
continue;
}
else if(!st.count({p1,p2+1})){
idxl.pb(u-1);
idxr.pb(idx-1);
posl.pb(p1);
posr.pb(p2+1);
st.insert({p1,p2+1});
continue;
}
}
else{
if(!st.count({p1-1,p2})){
idxl.pb(u-1);
idxr.pb(idx-1);
posl.pb(p1-1);
posr.pb(p2);
st.insert({p1-1,p2});
continue;
}
else if(!st.count({p1+1,p2})){
idxl.pb(u-1);
idxr.pb(idx-1);
posl.pb(p1+1);
posr.pb(p2);
st.insert({p1+1,p2});
continue;
}
}
p1=(c+l)/2,p2=(d+r)/2;
if(p1%2){
if(!st.count({p1,p2-1})){
idxl.pb(u-1);
idxr.pb(idx2-1);
posl.pb(p1);
posr.pb(p2-1);
st.insert({p1,p2-1});
continue;
}
else if(!st.count({p1,p2+1})){
idxl.pb(u-1);
idxr.pb(idx2-1);
posl.pb(p1);
posr.pb(p2+1);
st.insert({p1,p2+1});
continue;
}
}
else{
if(!st.count({p1-1,p2})){
idxl.pb(u-1);
idxr.pb(idx2-1);
posl.pb(p1-1);
posr.pb(p2);
st.insert({p1-1,p2});
continue;
}
else if(!st.count({p1+1,p2})){
idxl.pb(u-1);
idxr.pb(idx2-1);
posl.pb(p1+1);
posr.pb(p2);
st.insert({p1+1,p2});
continue;
}
}
}
else if(idx){
int p1=(a+l)/2,p2=(b+r)/2;
if(p1%2){
if(!st.count({p1,p2-1})){
idxl.pb(u-1);
idxr.pb(idx-1);
posl.pb(p1);
posr.pb(p2-1);
st.insert({p1,p2-1});
continue;
}
else if(!st.count({p1,p2+1})){
idxl.pb(u-1);
idxr.pb(idx-1);
posl.pb(p1);
posr.pb(p2+1);
st.insert({p1,p2+1});
continue;
}
}
else{
if(!st.count({p1-1,p2})){
idxl.pb(u-1);
idxr.pb(idx-1);
posl.pb(p1-1);
posr.pb(p2);
st.insert({p1-1,p2});
continue;
}
else if(!st.count({p1+1,p2})){
idxl.pb(u-1);
idxr.pb(idx-1);
posl.pb(p1+1);
posr.pb(p2);
st.insert({p1+1,p2});
continue;
}
}
}
else if(idx2){
int p1=(c+l)/2,p2=(d+r)/2;
if(p1%2){
if(!st.count({p1,p2-1})){
idxl.pb(u-1);
idxr.pb(idx2-1);
posl.pb(p1);
posr.pb(p2-1);
st.insert({p1,p2-1});
continue;
}
else if(!st.count({p1,p2+1})){
idxl.pb(u-1);
idxr.pb(idx2-1);
posl.pb(p1);
posr.pb(p2+1);
st.insert({p1,p2+1});
continue;
}
}
else{
if(!st.count({p1-1,p2})){
idxl.pb(u-1);
idxr.pb(idx2-1);
posl.pb(p1-1);
posr.pb(p2);
st.insert({p1-1,p2});
continue;
}
else if(!st.count({p1+1,p2})){
idxl.pb(u-1);
idxr.pb(idx2-1);
posl.pb(p1+1);
posr.pb(p2);
st.insert({p1+1,p2});
continue;
}
}
}
}
build(idxl,idxr,posl,posr);
return 1;
}
/*
cd "c:\Users\User\Desktop\parks (4)\cpp\" ; if ($?) { g++ parks.cpp grader.cpp -o parks } ; if ($?) { .\a.exe }
5
4 4
4 6
6 4
4 2
2 4
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Given structure is not connected: There is no path between vertices 0 and 1 |
| 4 |
Halted |
0 ms |
0 KB |
- |
