| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 817835 | alvingogo | Fountain Parks (IOI21_parks) | C++17 | 0 ms | 0 KiB |
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>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct DSU{
vector<int> bo,ss;
void init(int x){
bo.resize(x);
ss.resize(x,1);
iota(bo.begin(),bo.end(),0);
}
int find(int x){
return bo[x]==x?x:bo[x]=find(bo[x]);
}
int merge(int x,int y){
x=find(x);
y=find(y);
if(x==y){
return 0;
}
bo[x]=y;
ss[y]+=ss[x];
return 1;
}
}dsu;
vector<int> au,av,aa,ab;
set<pair<int,int> > vis;
void ag(int a,int b,int c,int d){
au.push_back(a);
av.push_back(b);
dsu.merge(a,b);
aa.push_back(c);
ab.push_back(d);
vis.insert({c,d});
//cout << a << " " << b << " " << c << " " << d << '\n';
}
int construct_roads(vector<int> x, vector<int> y) {
vis.clear();
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
map<pair<int,int>,int> mp;
int n=x.size();
for(int i=0;i<n;i++){
mp[{x[i],y[i]}]=i;
}
dsu.init(n);
const int dx[4]={0,0,2,-2},dy[4]={2,-2,0,0};
function<void(pair<int,int>,int)> dfs=[&](pair<int,int> w,int q){
int a=0,b=0,c=0,d=0;
if(dx[q]){
a=b=dx[q]/2;
c=1;
d=-1;
}
else{
a=1;
b=-1;
c=d=dy[q]/2;
}
int e=0,f=0,g=0,h=0;
int way=2*(1-q/2);
if(mp.find({w.fs+a,w.sc+c})==mp.end()){
if(mp.find({w.fs+b,w.sc+d})==mp.end()){
return;
}
way++;
}
if(dx[way]){
e=f=dx[way]/2;
g=1;
h=-1;
}
else{
e=1;
f=-1;
g=h=dy[way]/2;
}
for(int i=w.fs,j=w.sc;;i+=dx[way],j+=dy[way]){
int sx=i+e,sy=j+g,tx=i+f,ty=j+h;
if(mp.find({sx,sy})==mp.end() || mp.find({tx,ty})==mp.end()){
if(way<2){
assert(mp.find({sx-dx[way],sy-dy[way]})!=mp.end());
assert(mp.find({tx-dx[way],ty-dy[way]})!=mp.end());
ag(mp[{sx-dx[way],sy-dy[way]}],mp[{tx-dx[way],ty-dy[way]}],i,j);
}
dfs({i,j},way);
break;
}
else{
if(vis.find({i+dx[way],j+dy[way]})!=vis.end()){
break;
}
if(way>=2){
ag(mp[{sx,sy}],mp[{tx,ty}],i+dx[way],j+dy[way]);
}
}
}
};
for(int p=0;p<n;p++){
int c=x[p]+2,d=y[p];
if(mp.find({c,d})!=mp.end()){
if(mp.find({x[p]+2,y[p]+2})!=mp.end() && mp.find({x[p],y[p]+2})!=mp.end()){
continue;
}
int a=mp[{c,d}];
if(vis.find({x[p]+1,y[p]+1})==vis.end()){
ag(a,p,x[p]+1,y[p]+1);
dfs({x[p]+1,y[p]+1},0);
}
}
}
for(int p=0;p<n;p++){
int c=x[p],d=y[p]+2;
if(mp.find({c,d})!=mp.end()){
int a=mp[{c,d}];
if(vis.find({x[p]+1,y[p]+1})==vis.end()){
ag(a,p,x[p]+1,y[p]+1);
}
else if(vis.find(x[p]-1,y[p]+1)==vis.end()){
ag(a,p,x[p]-1,y[p]+1);
}
}
}
if(dsu.ss[dsu.find(0)]!=n){
return 0;
}
build(au,av,aa,ab);
return 1;
}