#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=2e5+99;
int n,a[N],b[N],f[N];
queue<pair<int,int>> q;
map<int,int> mark[N];
map<pair<int,int>,vector<pair<int,int>>> sq;
map<pair<int,int>,pair<int,int>> tn;
int getpar(int u){
if(f[u]<0) return u;
return f[u]=getpar(f[u]);
}
int merge(int u,int v){
u=getpar(u),v=getpar(v);
if(u==v) return 0;
if(f[u]>f[v]) swap(u,v);
f[u]+=f[v];
f[v]=u;
return 1;
}
void del(int x,int y,pair<int,int> p){
f(i,0,sz(sq[mp(x,y)])){
if(sq[mp(x,y)][i]==p){
sq[mp(x,y)].erase(sq[mp(x,y)].begin()+i);
break ;
}
}
if(sz(sq[mp(x,y)])==1){
tn[sq[mp(x,y)][0]]=mp(x,y);
q.push(sq[mp(x,y)][0]);
}
}
int construct_roads(vector<int> _a,vector<int> _b) {
fill(f,f+N,-1);
f(i,0,sz(_a)) a[i+1]=_a[i];
f(i,0,sz(_b)) b[i+1]=_b[i];
n=_a.size();
f(i,1,n+1){
mark[a[i]][b[i]]=i;
}
f(i,1,n+1){
if(mark[a[i]+2].count(b[i])){
int j=mark[a[i]+2][b[i]];
sq[{a[i]+1,b[i]+1}].pb({i,j});
sq[{a[i]+1,b[i]-1}].pb({i,j});
}
if(mark[a[i]].count(b[i]+2)){
int j=mark[a[i]][b[i]+2];
sq[{a[i]+1,b[i]+1}].pb({i,j});
sq[{a[i]-1,b[i]+1}].pb({i,j});
}
}
for(auto [p,v] : sq){
if(v.size()==1){
tn[v[0]]=p;
q.push(v[0]);
}
}
while(q.size()){
int u=q.front().F,v=q.front().S;
q.pop();
if(a[u]+2==a[v]){
del(a[u]+1,a[v]-1,mp(u,v));
del(a[u]+1,a[v]+1,mp(u,v));
}
}
vector<int> U,V,A,B;
f(i,1,n+1){
if(mark[a[i]+2].count(b[i])){
int j=mark[a[i]+2][b[i]];
if(merge(i,j)){
U.pb(i);
V.pb(j);
A.pb(tn[mp(i,j)].F);
B.pb(tn[mp(i,j)].S);
}
}
if(mark[a[i]].count(b[i]+2)){
int j=mark[a[i]][b[i]+2];
if(merge(i,j)){
U.pb(i);
V.pb(j);
A.pb(tn[mp(i,j)].F);
B.pb(tn[mp(i,j)].S);
}
}
}
/*cout<<endl;
cout<<U.size()<<endl;
f(i,0,n-1){
cout<<U[i]<<" "<<V[i]<<" "<<A[i]<<" "<<B[i]<<endl;
}
cout<<endl;*/
build(U,V,A,B);
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
10452 KB |
Integer parameter [name=v[j]] equals to 2, violates the range [0, 1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
10452 KB |
Integer parameter [name=v[j]] equals to 2, violates the range [0, 1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
10452 KB |
Integer parameter [name=v[j]] equals to 2, violates the range [0, 1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
10452 KB |
Integer parameter [name=v[j]] equals to 2, violates the range [0, 1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
10452 KB |
Integer parameter [name=v[j]] equals to 2, violates the range [0, 1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
10452 KB |
Integer parameter [name=v[j]] equals to 2, violates the range [0, 1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
