#include <bits/stdc++.h>
#include "parks.h"
#include <random>
#include <chrono>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
const int MOD1=1e9+7;
const int MOD2=998244353;
const ll INF=3e18;
const ld PI=3.14159265358979323846;
ll gcd(ll a,ll b){if(b==0) return a; return gcd(b,a%b);}
ll fpow(ll a,ll b,ll m)
{
if(!b) return 1;
ll ans=fpow(a*a%m,b/2,m);
return (b%2?ans*a%m:ans);
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
//#define int ll
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define repk(i,m,n) for(int i=m;i<n;i++)
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)
const int N=2e5+1;
bool vis[N<<2];
vector<int> x,y;
vector<int> retu,retv,a,b;
vector<pii> ed[N<<2];
pii point[N],pos[N<<2];
set<pii> edges,ban;
map<pii,int> id,id2;
int n,tn=0,cnt=0;
int par[N];
int fp(int u){return u==par[u]?u:par[u]=fp(par[u]);}
int unite(int u,int v)
{
if(fp(u)==fp(v)) return 0;
par[fp(v)]=fp(u);
return 1;
}
int solve()
{
for(pii tmp:edges)
{
int u=tmp.F,v=tmp.S;
int can=unite(u,v);
if(can)
{
cnt++;
retu.pb(u);
retv.pb(v);
if(y[u]==y[v])
{
int mid=x[u]+x[v]>>1;
if((mid+y[u]+1)%4==0)
{
a.pb(mid);
b.pb(y[u]+1);
}
else
{
a.pb(mid);
b.pb(y[u]-1);
}
}
else
{
int mid=y[u]+y[v]>>1;
if((mid+x[u]+1)%4==2)
{
a.pb(x[u]+1);
b.pb(mid);
}
else
{
a.pb(x[u]-1);
b.pb(mid);
}
}
}
}
}
void dfs(int u)
{
vis[u]=1;
for(pii tmp:ed[u])
{
if(vis[tmp.F]) continue;
pii p=pos[tmp.F];
if(tmp.S==1)
{
edges.erase({id[{p.F+1,p.S-1}],id[{p.F+1,p.S+1}]});
}
else if(tmp.S==2)
{
edges.erase({id[{p.F-1,p.S-1}],id[{p.F-1,p.S+1}]});
}
else if(tmp.S==3)
{
edges.erase({id[{p.F-1,p.S-1}],id[{p.F+1,p.S-1}]});
}
else if(tmp.S==4)
{
edges.erase({id[{p.F-1,p.S+1}],id[{p.F+1,p.S+1}]});
}
dfs(tmp.F);
}
}
int construct_roads(vector<int> X,vector<int> Y) {
x=X;
y=Y;
n=x.size();
if(n==1)
{
build(retu,retv,a,b);
return 1;
}
rep(i,n)
{
point[i]={x[i],y[i]};
id[point[i]]=i;
}
rep(i,n)
{
int tmp=0;
if(id.count({x[i]+2,y[i]}))
{
edges.insert({id[{x[i]+2,y[i]}],i});
tmp++;
}
if(id.count({x[i],y[i]+2}))
{
edges.insert({id[{x[i],y[i]+2}],i});
tmp++;
}
if(tmp==2)
{
if(id.count({x[i]+2,y[i]+2}))
{
tn++;
pos[tn]={x[i]+1,y[i]+1};
id2[{x[i]+1,y[i]+1}]=tn;
}
}
}
rep1(i,tn)
{
pii tmp=pos[i];
if((tmp.F+tmp.S)%4==0)
{
if(id2.count({tmp.F,tmp.S-2}))
{
int u=id2[{tmp.F,tmp.S-2}];
ed[i].pb({u,4});
ed[u].pb({i,3});
}
else ed[0].pb({i,3});
if(id2.count({tmp.F,tmp.S+2}))
{
int u=id2[{tmp.F,tmp.S+2}];
ed[i].pb({u,3});
ed[u].pb({i,4});
}
else ed[0].pb({i,4});
}
else
{
if(id2.count({tmp.F-2,tmp.S}))
{
int u=id2[{tmp.F-2,tmp.S}];
ed[i].pb({u,1});
ed[u].pb({i,2});
}
else ed[0].pb({i,2});
if(id2.count({tmp.F+2,tmp.S}))
{
int u=id2[{tmp.F+2,tmp.S}];
ed[i].pb({u,2});
ed[u].pb({i,1});
}
else ed[0].pb({i,1});
}
}
if(tn>0)
{
dfs(0);
}
rep(i,n) par[i]=i;
solve();
if(cnt<n-1) return 0;
else
{
build(retu,retv,a,b);
return 1;
}
}
/*
for blocks:
if (x+y)%4==0 then ud
if (x+y)%4==2 then lr
direction:
1: left
2: right
3: up
4: down
/*
signed main()
{
MottoHayaku
}
*/
Compilation message
parks.cpp:228:1: warning: "/*" within comment [-Wcomment]
228 | /*
|
parks.cpp: In function 'int solve()':
parks.cpp:76:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int mid=x[u]+x[v]>>1;
parks.cpp:90:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
90 | int mid=y[u]+y[v]>>1;
parks.cpp:104:1: warning: no return statement in function returning non-void [-Wreturn-type]
104 | }
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
19020 KB |
Output is correct |
| 2 |
Execution timed out |
3580 ms |
19000 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
19020 KB |
Output is correct |
| 2 |
Execution timed out |
3580 ms |
19000 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
19020 KB |
Output is correct |
| 2 |
Execution timed out |
3580 ms |
19000 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
19020 KB |
Output is correct |
| 2 |
Execution timed out |
3580 ms |
19000 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
19020 KB |
Output is correct |
| 2 |
Execution timed out |
3580 ms |
19000 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
19020 KB |
Output is correct |
| 2 |
Execution timed out |
3580 ms |
19000 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
