Submission #441444

#TimeUsernameProblemLanguageResultExecution timeMemory
441444daniel920712Fountain Parks (IOI21_parks)C++17
30 / 100
767 ms45712 KiB
#include "parks.h" #include <map> #include <utility> #include <queue> #include <set> #include <stdio.h> using namespace std; map < pair < int , int > , int > all,con; map < pair < int , int > , pair < int , int > > road; vector < int > u,v,a,b; queue < pair < int , int > > BFS; set < pair < int , int > > have,Not; int Father[200005]; int Find(int here) { if(Father[here]==here) return here; Father[here]=Find(Father[here]); return Father[here]; } int construct_roads(vector < int > x, vector < int > y) { int N=x.size(),i,t,aa,bb,ok=1,xx,yy,M; for(i=0;i<N;i++) { all[make_pair(x[i],y[i])]=i; Father[i]=i; } for(i=0;i<N;i++) { if(all.find(make_pair(x[i],y[i]+2))!=all.end()) { t=all[make_pair(x[i],y[i]+2)]; aa=Find(i); bb=Find(t); if(aa!=bb) Father[aa]=bb; if(x[i]==2) { u.push_back(i); v.push_back(t); a.push_back(x[i]-1); b.push_back(y[i]+1); } else if(x[i]==4) { if(y[i]%4==0) { u.push_back(i); v.push_back(t); a.push_back(x[i]-1); b.push_back(y[i]+1); } else { u.push_back(i); v.push_back(t); a.push_back(x[i]+1); b.push_back(y[i]+1); } } else if(x[i]==6) { u.push_back(i); v.push_back(t); a.push_back(x[i]+1); b.push_back(y[i]+1); } } if(all.find(make_pair(x[i]+2,y[i]))!=all.end()) { t=all[make_pair(x[i]+2,y[i])]; aa=Find(i); bb=Find(t); if(aa!=bb) Father[aa]=bb; if(y[i]%4==0) { if(x[i]==2) { u.push_back(i); v.push_back(t); a.push_back(x[i]+1); b.push_back(y[i]-1); } else { u.push_back(i); v.push_back(t); a.push_back(x[i]+1); b.push_back(y[i]+1); } } else { Not.insert(make_pair(i,t)); } } } M=a.size(); for(i=0;i<M;i++) have.insert(make_pair(a[i],b[i])); for(auto i:Not) { if(have.find(make_pair(x[i.first]+1,y[i.first]+1))==have.end()) { have.insert(make_pair(x[i.first]+1,y[i.first]+1)); u.push_back(i.first); v.push_back(i.second); a.push_back(x[i.first]+1); b.push_back(y[i.first]+1); } else if(have.find(make_pair(x[i.first]+1,y[i.first]-1))==have.end()) { have.insert(make_pair(x[i.first]+1,y[i.first]-1)); u.push_back(i.first); v.push_back(i.second); a.push_back(x[i.first]+1); b.push_back(y[i.first]-1); } } t=Find(0); for(i=0;i<N;i++) { //printf("%d %d\n",t,Find(i)); if(t!=Find(i)) ok=0; } if(ok==0) return ok; if(ok) build(u,v,a,b); return ok; }

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:22:35: warning: unused variable 'xx' [-Wunused-variable]
   22 |     int N=x.size(),i,t,aa,bb,ok=1,xx,yy,M;
      |                                   ^~
parks.cpp:22:38: warning: unused variable 'yy' [-Wunused-variable]
   22 |     int N=x.size(),i,t,aa,bb,ok=1,xx,yy,M;
      |                                      ^~
#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...