Submission #1217699

#TimeUsernameProblemLanguageResultExecution timeMemory
1217699guagua0407Fountain Parks (IOI21_parks)C++20
5 / 100
288 ms42728 KiB
#include "parks.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); namespace{ struct DSU{ vector<int> e; DSU(int n){ e=vector<int>(n,-1); } int find(int x){ return (e[x]<0?x:e[x]=find(e[x])); } int sz(int x){ return -e[find(x)]; } bool unite(int a,int b){ a=find(a); b=find(b); if(a==b) return false; if(e[a]>e[b]) swap(a,b); e[a]+=e[b]; e[b]=a; return true; } }; } int construct_roads(std::vector<int> x, std::vector<int> y) { map<int,map<int,int>> mp; map<int,int> cnt; int n=(int)x.size(); for(int i=0;i<n;i++){ mp[y[i]][x[i]]=i+1; cnt[y[i]]++; } vector<int> ys; for(int i=0;i<n;i++){ ys.push_back(y[i]); } sort(all(ys)); ys.resize(unique(all(ys))-ys.begin()); vector<int> u,v,a,b; int cnt2=0; for(auto Y:ys){ /*if(cnt[Y-2]==0){ cnt2++; continue; }*/ bool tf=false; if(mp[Y][2]!=0 and mp[Y-2][2]!=0){ u.push_back(mp[Y-2][2]-1); v.push_back(mp[Y][2]-1); a.push_back(1); b.push_back(Y-1); tf=true; } else if(mp[Y][6]!=0 and mp[Y-2][6]!=0){ u.push_back(mp[Y-2][6]-1); v.push_back(mp[Y][6]-1); a.push_back(7); b.push_back(Y-1); tf=true; } if(tf or cnt[Y-2]==0){ if(mp[Y][2]!=0 and mp[Y][4]!=0){ u.push_back(mp[Y][2]-1); v.push_back(mp[Y][4]-1); a.push_back(3); b.push_back(Y-1); //tf=true; } if(mp[Y][4]!=0 and mp[Y][6]!=0){ u.push_back(mp[Y][4]-1); v.push_back(mp[Y][6]-1); a.push_back(5); b.push_back(Y-1); //tf=true; } continue; } //continue; if(cnt[Y-2]==0) continue; if(mp[Y][4]==0 or mp[Y-2][4]==0){ return 0; } if(mp[Y][2]!=0 and mp[Y][6]!=0){ u.push_back(mp[Y-2][4]-1); v.push_back(mp[Y][4]-1); a.push_back(1); b.push_back(Y-1); u.push_back(mp[Y][4]-1); v.push_back(mp[Y][6]-1); a.push_back(5); b.push_back(Y-1); u.push_back(mp[Y][2]-1); v.push_back(mp[Y][4]-1); a.push_back(1); b.push_back(Y+1); } else if(mp[Y][2]!=0){ u.push_back(mp[Y-2][4]-1); v.push_back(mp[Y][4]-1); a.push_back(5); b.push_back(Y-1); u.push_back(mp[Y][2]-1); v.push_back(mp[Y][4]-1); a.push_back(1); b.push_back(Y-1); } else if(mp[Y][6]!=0){ u.push_back(mp[Y-2][4]-1); v.push_back(mp[Y][4]-1); a.push_back(1); b.push_back(Y-1); u.push_back(mp[Y][4]-1); v.push_back(mp[Y][6]-1); a.push_back(5); b.push_back(Y-1); } else{ u.push_back(mp[Y-2][4]-1); v.push_back(mp[Y][4]-1); a.push_back(5); b.push_back(Y-1); } } //if(cnt2>1) return 0; /*vector<pair<int,int>> e; for(int i=0;i<n;i++){ if(mp.find({x[i]-2,y[i]})!=mp.end()){ e.push_back({mp[{x[i]-2,y[i]}],i}); } if(x[i]==2 or x[i]==6){ if(mp.find({x[i],y[i]-2})!=mp.end()){ e.push_back({mp[{x[i],y[i]-2}],i}); } } }*/ DSU dsu(n); for(int i=0;i<(int)u.size();i++){ //cout<<v.f<<' '<<v.s<<'\n'; dsu.unite(u[i],v[i]); } if(dsu.sz(0)!=n) return 0; /*vector<int> u,v,a,b; for(auto p:e){ u.push_back(p.f); v.push_back(p.s); if(y[p.f]==y[p.s]){ a.push_back((x[p.f]+x[p.s])/2); b.push_back(y[p.f]+1); } else{ if(x[p.f]==2) a.push_back(1); else a.push_back(7); b.push_back((y[p.f]+y[p.s])/2); } }*/ build(u,v,a,b); 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...