This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
///~~~LOTA~~~///
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define N 200001
int siz[N];
int par[N];
int root(int v){
if(!par[v]) return v;
par[v]=root(par[v]);
return par[v];
}
void merge(int v,int u){
v=root(v);
u=root(u);
par[u]=v;
siz[v]+=siz[u];
}
bool same(int v,int u){
return (root(v)==root(u));
}
int construct_roads(vector<int> x,vector<int> y){
map<pii,int> c,z;
int n,m,o,p,q,r;
n=x.size();
vector<int> v,u,a,b;
vector<pair<pii,int>> w;
for(int i=0;i<n;i++){
w.append({{y[i],x[i]},i+1});
z[{x[i],y[i]}]=i+1;
siz[i+1]=1;
}
sort(all(w));
for(auto& i:w){
q=i.ff.ff;
p=i.ff.ss;
r=z[{p,q-2}];
if(r){
if(!same(i.ss,r)){
merge(i.ss,r);
v.append(i.ss-1);
u.append(r-1);
if(!c[{p-1,q-1}]){
a.append(p-1);
b.append(q-1);
c[{p-1,q-1}]=1;
}
else if(!c[{p+1,q-1}]){
a.append(p+1);
b.append(q-1);
c[{p+1,q-1}]=1;
}
else return 0;
}
}
r=z[{p-2,q}];
if(r){
if(!same(i.ss,r)){
merge(i.ss,r);
v.append(i.ss-1);
u.append(r-1);
if(!c[{p-1,q-1}]){
a.append(p-1);
b.append(q-1);
c[{p-1,q-1}]=1;
}
else if(!c[{p-1,q+1}]){
a.append(p-1);
b.append(q+1);
c[{p-1,q+1}]=1;
}
else return 0;
}
}
}
if(siz[root(1)]!=n) return 0;
build(u,v,a,b);
return 1;
}
Compilation message (stderr)
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:31:11: warning: unused variable 'm' [-Wunused-variable]
31 | int n,m,o,p,q,r;
| ^
parks.cpp:31:13: warning: unused variable 'o' [-Wunused-variable]
31 | int n,m,o,p,q,r;
| ^
# | 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... |