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 ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
struct point{
ll x,y,id;
point(ll x1 = 0,ll y1 = 0,ll id1 = 0):x(x1),y(y1),id(id1){}
bool operator < (const point &p)const {
return MP(x,y) < MP(p.x,p.y);
}
};
const ll MAXN = 2e5+100;
ll dsu[MAXN];
ll f(ll x){
if (dsu[x] < 0)return x;
return (dsu[x] = f(dsu[x]));
}
bool join(ll x,ll y){
x = f(x),y = f(y);
if (x==y)return 0;
dsu[x] += dsu[y];
dsu[y] = x;
return 1;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
ll n = sz(x);
vector <point> a(n);
for (ll i = 0;i < n;i ++){
dsu[i] = -1;
a[i] = {x[i],y[i],i};
}
sort(a.begin(),a.end());
vector <int> U, V, A, B;
set <pll> bench;
auto add = [&](ll u,ll v, ll x,ll y){
// cout<<u<<' '<<v<<endl;
if (join(u,v)==0)return;
U.push_back(u);
V.push_back(v);
A.push_back(x);
B.push_back(y);
bench.insert(MP(x,y));
};
auto id = [&](pll x){
auto tmp = lower_bound(a.begin(),a.end(),point(x.fi,x.se,0));
if (tmp != a.end() && (*tmp).x==x.fi&&(*tmp).y==x.se)return (*tmp).id;
else return -1;
};
for (ll i = 0;i < n;i ++){
// cout<<i<<endl;
if (((a[i].x + a[i].y)/2)&1){
if (bench.find(MP(a[i].x + 1,a[i].y - 1)) == bench.end() && id(MP(a[i].x,a[i].y-2)) != -1){
add(a[i].id,id(MP(a[i].x,a[i].y-2)),a[i].x+1,a[i].y-1);
}
if (bench.find(MP(a[i].x - 1,a[i].y - 1)) == bench.end() && id(MP(a[i].x-2,a[i].y)) != -1){
add(a[i].id,id(MP(a[i].x-2,a[i].y)),a[i].x-1,a[i].y-1);
}
}
else{
// cout<<i<<endl;
if (bench.find(MP(a[i].x - 1,a[i].y - 1)) == bench.end() && id(MP(a[i].x,a[i].y-2)) != -1){
add(a[i].id,id(MP(a[i].x,a[i].y-2)),a[i].x-1,a[i].y-1);
}
if (bench.find(MP(a[i].x - 1,a[i].y + 1)) == bench.end() && id(MP(a[i].x-2,a[i].y)) != -1){
add(a[i].id,id(MP(a[i].x-2,a[i].y)),a[i].x-1,a[i].y+1);
}
}
}
{
if (dsu[f(0)] != -n)return 0;
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... |