Submission #1230220

#TimeUsernameProblemLanguageResultExecution timeMemory
1230220LudisseyFountain Parks (IOI21_parks)C++20
5 / 100
3363 ms49704 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; #define all(a) a.begin(), a.end() #define sz(a) (int)a.size() vector<int> sz,parent; int getParent(int a){ if(parent[a]==a) return a; return parent[a]=getParent(parent[a]); } bool same(int a, int b){ a=getParent(a); b=getParent(b); return (a==b); } void unite(int a, int b){ a=getParent(a); b=getParent(b); if(a==b) return; if(sz[a]<sz[b]){ swap(a,b); } sz[a]+=sz[b]; parent[b]=a; } int construct_roads(std::vector<int> x, std::vector<int> y) { int n=sz(x); vector<vector<pair<int,int>>> neigh(n); sz.resize(n,1); parent.resize(n); for (int i = 0; i < n; i++) parent[i]=i; vector<pair<pair<int,int>,int>> f(n); for (int i = 0; i < n; i++) f[i]={{x[i],y[i]},i}; map<pair<int,int>, int> mp; for (int i = 0; i < n; i++) mp[{x[i],y[i]}]=i; vector<int> u, v, a, b; vector<pair<int,int>> moves={{-2,0},{0,-2},{0,2},{2,0}}; for (int i = 0; i < n; i++) { for (int j = 0; j < sz(moves); j++) { pair<int,int> nxt={f[i].first.first+moves[j].first,f[i].first.second+moves[j].second}; if(mp.find(nxt)!=mp.end()){ if(!same(f[i].second,mp[nxt])){ unite(f[i].second,mp[nxt]); neigh[f[i].second].push_back({sz(u),j}); neigh[mp[nxt]].push_back({sz(u),3-j}); u.push_back(f[i].second); v.push_back(mp[nxt]); a.push_back(-1); b.push_back(-1); } } } } set<pair<int,int>> st; for (int i = 0; i < n; i++) { int _x=x[i]; int _y=y[i]; if(sz(neigh[i])==4){ for (auto u : neigh[i]) { if(u.second==0){ a[u.first]=_x-1; b[u.first]=_y-1; }else if(u.second==1){ a[u.first]=_x+1; b[u.first]=_y-1; }else if(u.second==2){ a[u.first]=_x-1; b[u.first]=_y+1; }else{ a[u.first]=_x+1; b[u.first]=_y+1; } } }else if(sz(neigh[i])==3){ set<int> rem; rem.insert(0); rem.insert(1); rem.insert(2); rem.insert(3); for (auto u : neigh[i]) rem.erase(u.second); int indx=*(rem.begin()); for (auto u : neigh[i]) { if(u.second==0){ if(indx==2){ a[u.first]=_x-1; b[u.first]=_y-1; }else{ a[u.first]=_x-1; b[u.first]=_y+1; } }else if(u.second==1){ if(indx==3){ a[u.first]=_x-1; b[u.first]=_y-1; }else{ a[u.first]=_x+1; b[u.first]=_y-1; } }else if(u.second==2){ if(indx==0){ a[u.first]=_x-1; b[u.first]=_y+1; }else{ a[u.first]=_x+1; b[u.first]=_y+1; } }else{ if(indx==1){ a[u.first]=_x+1; b[u.first]=_y-1; }else{ a[u.first]=_x+1; b[u.first]=_y+1; } } } } } for (int i = 0; i < sz(a); i++) { if(a[i]>=0) st.insert({a[i],b[i]}); } int MAX=100; while(MAX--){ for (int i = 0; i < n; i++) { int _x=x[i]; int _y=y[i]; for (auto u : neigh[i]) { if(a[u.first]>=0) continue; if(u.second==0){ if(st.find({_x-1,_y-1})==st.end()&&st.find({_x-1,_y+1})==st.end()) continue; if(st.find({_x-1,_y-1})==st.end()){ st.insert({_x-1,_y-1}); a[u.first]=_x-1; b[u.first]=_y-1; }else{ st.insert({_x-1,_y+1}); a[u.first]=_x-1; b[u.first]=_y+1; } }else if(u.second==1){ if(st.find({_x-1,_y-1})==st.end()&&st.find({_x+1,_y-1})==st.end()) continue; if(st.find({_x-1,_y-1})==st.end()){ st.insert({_x-1,_y-1}); a[u.first]=_x-1; b[u.first]=_y-1; }else{ st.insert({_x+1,_y-1}); a[u.first]=_x+1; b[u.first]=_y-1; } }else if(u.second==2){ if(st.find({_x-1,_y+1})==st.end()&&st.find({_x+1,_y+1})==st.end()) continue; if(st.find({_x-1,_y+1})==st.end()){ st.insert({_x-1,_y+1}); a[u.first]=_x-1; b[u.first]=_y+1; }else{ st.insert({_x+1,_y+1}); a[u.first]=_x+1; b[u.first]=_y+1; } }else{ if(st.find({_x+1,_y-1})==st.end()&&st.find({_x+1,_y+1})==st.end()) continue; if(st.find({_x+1,_y-1})==st.end()){ st.insert({_x+1,_y-1}); a[u.first]=_x+1; b[u.first]=_y-1; }else{ st.insert({_x+1,_y+1}); a[u.first]=_x+1; b[u.first]=_y+1; } } } } } for (int i = 0; i < n; i++) { int _x=x[i]; int _y=y[i]; for (auto u : neigh[i]) { if(a[u.first]>=0) continue; if(u.second==0){ if(st.find({_x-1,_y-1})==st.end()){ st.insert({_x-1,_y-1}); a[u.first]=_x-1; b[u.first]=_y-1; }else{ st.insert({_x-1,_y+1}); a[u.first]=_x-1; b[u.first]=_y+1; } }else if(u.second==1){ if(st.find({_x-1,_y-1})==st.end()){ st.insert({_x-1,_y-1}); a[u.first]=_x-1; b[u.first]=_y-1; }else{ st.insert({_x+1,_y-1}); a[u.first]=_x+1; b[u.first]=_y-1; } }else if(u.second==2){ if(st.find({_x-1,_y+1})==st.end()){ st.insert({_x-1,_y+1}); a[u.first]=_x-1; b[u.first]=_y+1; }else{ st.insert({_x+1,_y+1}); a[u.first]=_x+1; b[u.first]=_y+1; } }else{ if(st.find({_x+1,_y-1})==st.end()){ st.insert({_x+1,_y-1}); a[u.first]=_x+1; b[u.first]=_y-1; }else{ st.insert({_x+1,_y+1}); a[u.first]=_x+1; b[u.first]=_y+1; } } } } if (sz[getParent(0)] != n) { return 0; } 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...