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 namespace std;
#define MP make_pair
const int maxn=(2e5)+10;
map<pair<int,int>,int> M;
int n,m,hd,tl;
bool vis[maxn];
int fx[4][2]={{-2,0},{2,0},{0,-2},{0,2}};
int q[maxn];
int construct_roads(vector<int> X,vector<int> Y) {
n=(int)X.size();
vector<int> u,v,a,b;
for (int i=0;i<n;i++) M[MP(X[i],Y[i])]=i;
hd=tl=1; q[1]=0; vis[0]=1;
while (hd<=tl) {
int x=X[q[hd]],y=Y[q[hd]]; hd++;
for (int i=0;i<4;i++) {
int xx=x+fx[i][0],yy=y+fx[i][1];
if (M.count(MP(xx,yy))) {
int id=M[MP(xx,yy)]; if (vis[id]) continue;
vis[id]=1; q[++tl]=id;
}
}
}
if (tl!=n) return 0;
for (int i=0;i<n;i++) {
int x=X[i],y=Y[i];
int A=x+2,B=y;
if (M.count(MP(A,B))) {
u.push_back(i),v.push_back(M[MP(A,B)]);
a.push_back(x+1); if ((x+y)&2) b.push_back(y+1); else b.push_back(y-1);
}
A=x,B=y+2;
if (M.count(MP(A,B))) {
u.push_back(i),v.push_back(M[MP(A,B)]);
if ((x+y)&2) a.push_back(x-1); else a.push_back(x+1); b.push_back(y+1);
}
}
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... |