#include "parks.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
//#define int long long
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
//typedef long double ld;
typedef long long ll;
using namespace std;
struct node{double x,y;};
//double len(node a,node b)
//{return sqrt((a.x-b.x)*(a.x-b.y)+(a.y-b.y)*(a.x-b.y));}
struct seg{
int l,r,id;
};
const string out[2]={"NO\n","YES\n"};
const ll dx[]={-1,-1,1,1};
const ll dy[]={-1,1,-1,1};
const ll dxx[]={0,0,2,-2};
const ll dyy[]={2,-2,0,0};
const int md=998244353;
const int mod=1e9+7;
const int mx=8e5+12;
const int tst=1e5;
const bool T=0;
pair<int,pair<int,int>> p[mx];
map<int,bool> used[mx];
map<int,int> pos[mx];
vector<int> g[mx];
int ma[mx];
int mi[mx];
void dfs(int x,int y){
used[x][y]=1;
ma[x]=max(ma[x],y);
mi[x]=min(mi[x],y);
for(int k=0;k<4;k++){
int x1=x+dxx[k];
int y1=y+dyy[k];
if(!used[x1].count(y1) && pos[x1].count(y1))dfs(x1,y1);
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n=x.size();
for(int i=1;i<=n;i++){
p[i]={x[i-1],{y[i-1],i}};
}
sort(p+1,p+n+1);
int mx=0;
reverse(x.begin(),x.end());
reverse(y.begin(),y.end());
x.push_back(0);
y.push_back(0);
reverse(x.begin(),x.end());
reverse(y.begin(),y.end());
for(int i=1;i<=n;i++){
mx=max(mx,x[i]);
pos[x[i]][y[i]]=i-1;
}
for(int i=0;i<=mx;i++)mi[i]=1e9;
dfs(x[1],y[1]);
for(int i=1;i<=n;i++){
if(!used[x[i]][y[i]]){
return 0;
}
}
vector<int> u,v,a,b;
if(mx<=6){
for(int i=mi[2];i<ma[2];i+=2){
u.push_back(pos[2][i]);
v.push_back(pos[2][i+2]);
a.push_back(1);
b.push_back(i-1);
}
if(mx==2){
build(u,v,a,b);
return 1;
}
for(int i=mi[4];i<ma[4];i+=2){
u.push_back(pos[4][i]);
v.push_back(pos[4][i+2]);
a.push_back(3);
b.push_back(i-1);
}
if(ma[2]<ma[4]){
u.push_back(pos[2][ma[2]]);
v.push_back(pos[4][ma[2]]);
a.push_back(1);
b.push_back(ma[2]+1);
}
else{
u.push_back(pos[2][ma[4]]);
v.push_back(pos[4][ma[4]]);
a.push_back(3);
b.push_back(ma[4]+1);
}
if(mx==4){
build(u,v,a,b);
return 1;
}
for(int i=mi[6];i<ma[6];i+=2){
u.push_back(pos[6][i]);
v.push_back(pos[6][i+2]);
a.push_back(7);
b.push_back(i-1);
}
int x=min(ma[4],ma[6]);
u.push_back(pos[4][x]);
v.push_back(pos[6][x]);
a.push_back(5);
b.push_back(x+1);
build(u,v,a,b);
return 1;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
94156 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
94124 KB |
Tree (a[0], b[0]) = (1, 1) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
94156 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
94124 KB |
Tree (a[0], b[0]) = (1, 1) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
94156 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
94124 KB |
Tree (a[0], b[0]) = (1, 1) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
94156 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
94124 KB |
Tree (a[0], b[0]) = (1, 1) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
94156 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
94124 KB |
Tree (a[0], b[0]) = (1, 1) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
94156 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
94124 KB |
Tree (a[0], b[0]) = (1, 1) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4) |
| 3 |
Halted |
0 ms |
0 KB |
- |
