#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=2*1e5+5;
pair<int,int> p[maxn];
map<pair<int,int>, int> mp,e;
map<pair<int,int>, vector<int> > bench;
int k,used[maxn];
int in;
vector<int> v,u,a,b;
void dfs(int i,int l)
{
//cout<<i<<endl;
in++;
if(i!=1)
{
if(p[i].first==p[l].first)
{
int heh=min(p[i].second,p[l].second)+1;
bench[ {p[i].first-1,heh}].push_back(v.size());
bench[ {p[i].first+1,heh}].push_back(v.size());
}
else
{
int heh=min(p[i].first,p[l].first)+1;
bench[ {heh,p[i].second-1}].push_back(v.size());
bench[ {heh,p[i].second+1}].push_back(v.size());
}
v.push_back(l);
u.push_back(i);
e[ {i,l}]=e[ {l,i}]=1;
}
used[i]=1;
pair<int,int> c;
c=p[i];
c.first+=2;
if(mp[c]&&!used[mp[c]])dfs(mp[c],i);
c=p[i];
c.first-=2;
if(mp[c]&&!used[mp[c]])dfs(mp[c],i);
c=p[i];
c.second+=2;
if(mp[c]&&!used[mp[c]])dfs(mp[c],i);
c=p[i];
c.second-=2;
if(mp[c]&&!used[mp[c]])dfs(mp[c],i);
}
int done[maxn];
map<pair<int,int>,int> use;
int construct_roads(std::vector<int> x, std::vector<int> y)
{
mp.clear();
e.clear();
v.clear();
u.clear();
a.clear();
b.clear();
memset(used,0,sizeof(used));
memset(done,0,sizeof(done));
bench.clear();
in=0;
k=x.size();
for(int i=0; i<k; i++)
{
p[i+1]= {x[i],y[i]};
mp[p[i+1]]=i+1;
}
dfs(1,0);
if(in!=k)return 0;
vector<pair<int,int> > val;
for(int i=0; i<k-1; i++)
{
pair<int,int> p1=p[v[i]],p2=p[u[i]];
if(p1.first==p2.first)
{
int f=p1.first;
int g=min(p1.second,p2.second);
if(bench[ {f-1,g+1}].size()==1)val.push_back({f-1,g+1});
if(bench[ {f+1,g+1}].size()==1)val.push_back({f+1,g+1});
}
else
{
int f=min(p1.first,p2.first);
int g=p1.second;
if(bench[ {f+1,g-1}].size()==1)val.push_back({f+1,g-1});
if(bench[ {f+1,g+1}].size()==1)val.push_back({f+1,g+1});
}
}
/* cout<<"out"<<endl;
for(int i=0;i<val.size();i++)
cout<<val[i].first<<" "<<val[i].second<<endl;
*/
a.resize(x.size()-1);
b.resize(x.size()-1);
while(val.size())
{
int i=val.size()-1;
int id=bench[val[i]][0];
if(done[id])
{
val.pop_back();
continue;
}
done[id]=1;
a[id]=val[i].first;
b[id]=val[i].second;
bench[val[i]].clear();
//cout<<id<<endl;
//cout<<val[i].first<<" "<<val[i].second<<endl;
val.pop_back();
pair<int,int> p1=p[v[id]],p2=p[u[id]];
if(p1.first==p2.first)
{
int f=p1.first;
int g=min(p1.second,p2.second);
if(bench[ {f-1,g+1}].size()==2)
{
int hi=bench[{f-1,g+1}][0];
if(hi==id)bench[{f-1,g+1}]={bench[{f-1,g+1}][1]};
else bench[{f-1,g+1}]={bench[{f-1,g+1}][0]};
val.push_back({f-1,g+1});
}
if(bench[ {f+1,g+1}].size()==2)
{
int hi=bench[{f+1,g+1}][0];
if(hi==id)bench[{f+1,g+1}]={bench[{f+1,g+1}][1]};
else bench[{f+1,g+1}]={bench[{f+1,g+1}][0]};
val.push_back({f+1,g+1});
}
}
else
{
int f=min(p1.first,p2.first);
int g=p1.second;
if(bench[ {f+1,g-1}].size()==2)
{
int hi=bench[{f+1,g-1}][0];
if(hi==id)bench[{f+1,g-1}]={bench[{f+1,g-1}][1]};
else bench[{f+1,g-1}]={bench[{f+1,g-1}][0]};
val.push_back({f+1,g-1});
}
if(bench[ {f+1,g+1}].size()==2)
{
int hi=bench[{f+1,g+1}][0];
if(hi==id)bench[{f+1,g+1}]={bench[{f+1,g+1}][1]};
else bench[{f+1,g+1}]={bench[{f+1,g+1}][0]};
val.push_back({f+1,g+1});
}
}
}
for(int i=0; i<k-1; i++)
{
if(done[i])continue;
pair<int,int> p1=p[v[i]],p2=p[u[i]];
if(p1.first==p2.first)
{
int f=p1.first;
int g=min(p1.second,p2.second);
b[i]=g+1;
if(e[ {mp[{f,g}],mp[{f-2,g}]}]||e[ {mp[{f,g}],mp[{f+2,g}]}])
a[i]=f+1;
else a[i]=f-1;
}
else
{
int f=min(p1.first,p2.first);
int g=p1.second;
a[i]=f+1;
if(e[ {mp[{f,g}],mp[{f,g-2}]}]||e[ {mp[{f,g}],mp[{f,g+2}]}])
b[i]=g-1;
else b[i]=g+1;
}
}
for(int i=0; i<k-1; i++)
v[i]--,u[i]--;
/*use.clear();
for(int i=0;i<k-1;i++)
{
use[{a[i],b[i]}]++;
if(use[{a[i],b[i]}]==2)
{
for(int j=0;j<x.size();j++)
cout<<x[j]<<" "<<y[j]<<endl;
for(int j=0;j<x.size()-1;j++)
cout<<a[j]<<" "<<b[j]<<endl;
exit(0);
}
}
cout<<"done"<<endl;*/
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... |