Submission #817838

#TimeUsernameProblemLanguageResultExecution timeMemory
817838alvingogoFountain Parks (IOI21_parks)C++17
5 / 100
729 ms46688 KiB
#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]+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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...