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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF (int) 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
template<typename T>
using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename AA,typename BB>
void _print(vector<pair<AA,BB>> x) {cerr<<"["; int cnt_temp12=0;
for(auto e:x) {
if(cnt_temp12) cerr<<", ";
cerr<<"{"<<e.first<<","<<e.second<<"}"; ++cnt_temp12;} cerr<<"]";
}
template<typename AA,typename BB>
void _print(pair<AA,BB> x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(vector<T> x) {cerr<<"{"; int cnt_temp12=0;
for(auto e:x) {
if(cnt_temp12) cerr<<",";
cerr<<e; ++cnt_temp12;
}cerr<<"}";
}
template<typename T>
void _print(T x) {cerr<<x;}
void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
_print(H);
if(sizeof...(T)) cerr<<",";
else cerr<<" \"]";
dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\" ",dbg(__VA_ARGS__)
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//int rnglr(int l,int r) {return rng()%(r-l+1)+l;}
struct dt {
int x,y,idx;
bool operator<(const dt &r) {
return y<r.y;
}
};
const int mxn = 2e5+10;
int n;
int flag[7][mxn];
vector<int> par;
int dm[4] = {-2,0,2,0};
int dn[4] = {0,2,0,-2};
bool valid(int M,int N) {
if(M<=0 or N<=0 or M>4) return false;
return flag[M][N]>=0;
}
int findp(int x) {
if(par[x] == x) return x;
return par[x] = findp(par[x]);
}
void unionset(int u,int v) {
int U = findp(u), V = findp(v);
par[U] = V;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
n = x.size();
par.resize(n);
vector<dt> ar;
for(int i=0;i<7;i++) fill(flag[i],flag[i]+mxn,-1);
for(int i=0;i<n;i++) {
ar.push_back({x[i],y[i],i});
}
sort(all(ar));
for(int i=0;i<n;i++) {
flag[x[i]][y[i]] = i;
}
vector<int> u,v,a,b;
for(int i=0;i<n;i++) {
int X = x[i], Y = y[i];
for(int j=0;j<4;j++) {
int XX = X+dm[j], YY = Y+dn[j];
if(valid(XX,YY)) {
int i2 = flag[XX][YY];
if(i>i2) continue;
// debug(i,i2);
u.push_back(ar[i].idx);
v.push_back(ar[i2].idx);
unionset(i,i2);
if(X==2) {
if(XX==2) a.push_back(1),b.push_back(min(Y,YY)+1);
else a.push_back(3),b.push_back(min(Y,YY)+1);
}
else {
// X=4
if(XX==2) a.push_back(3),b.push_back(min(Y,YY)+1);
else a.push_back(5), b.push_back(min(Y,YY)+1);
}
}
// debug(u);
// debug(v);
// debug(a);
// debug(b);
}
}
// debug(u);
// debug(v);
// debug(a);
// debug(b);
set<int> par_list;
for(int i=0;i<n;i++) {
int temp = findp(i);
par_list.insert(temp);
}
if(par_list.size()!=1) 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... |