제출 #894896

#제출 시각아이디문제언어결과실행 시간메모리
894896MuhammadSaram분수 공원 (IOI21_parks)C++17
5 / 100
783 ms59980 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b); const int M = 2e5; set<int> nei[M]; bool vis[M]; void dfs(int u) { vis[u]=true; for (int i:nei[u]) if (!vis[i]) dfs(i); } int construct_roads(vector<int> x, vector<int> y) { int n=x.size(); map<pair<int,int>,int> ind; for (int i=0;i<n;i++) ind[{x[i],y[i]}]=i; for (int i=0;i<n;i++) for (int j=-2;j<=2;j+=2) for (int k=-2;k<=2;k+=2) { if ((j==0)==(k==0)) continue; if (ind.find({x[i]+j,y[i]+k})!=ind.end()) nei[i].insert(ind[{x[i]+j,y[i]+k}]); } dfs(0); for (int i=0;i<n;i++) if (!vis[i]) return 0; set<pair<int,int>> se; vector<int> u,v,a,b; for (int i=0;i<n;i++) { bool o=true; for (int j=-2;j<=2 and o;j+=2) for (int k=-2;k<=2 and o;k+=2) { if ((j==0)==(k==0)) continue; if (ind.find({x[i]+j,y[i]+k})==ind.end()) o=false; } if (o) { u.push_back(i),v.push_back(ind[{x[i],y[i]-2}]); a.push_back(x[i]-1),b.push_back(y[i]-1); se.insert({a.back(),b.back()}); u.push_back(i),v.push_back(ind[{x[i]-2,y[i]}]); a.push_back(x[i]-1),b.push_back(y[i]+1); se.insert({a.back(),b.back()}); u.push_back(i),v.push_back(ind[{x[i],y[i]+2}]); a.push_back(x[i]+1),b.push_back(y[i]+1); se.insert({a.back(),b.back()}); u.push_back(i),v.push_back(ind[{x[i]+2,y[i]}]); a.push_back(x[i]+1),b.push_back(y[i]-1); se.insert({a.back(),b.back()}); nei[i].erase(ind[{x[i],y[i]-2}]),nei[ind[{x[i],y[i]-2}]].erase(i); nei[i].erase(ind[{x[i]-2,y[i]}]),nei[ind[{x[i]-2,y[i]}]].erase(i); nei[i].erase(ind[{x[i],y[i]+2}]),nei[ind[{x[i],y[i]+2}]].erase(i); nei[i].erase(ind[{x[i]+2,y[i]}]),nei[ind[{x[i]+2,y[i]}]].erase(i); } } for (int i=0;i<n;i++) for (int j:nei[i]) { if (x[i]==x[j]) { int avg=(y[i]+y[j])/2; if (se.find({x[i]-1,avg})==se.end()) { u.push_back(i),v.push_back(j); a.push_back(x[i]-1),b.push_back(avg); se.insert({a.back(),b.back()}); } else { u.push_back(i),v.push_back(j); a.push_back(x[i]+1),b.push_back(avg); se.insert({a.back(),b.back()}); } } else { int avg=(x[i]+x[j])/2; if (se.find({avg,y[i]-1})==se.end()) { u.push_back(i),v.push_back(j); a.push_back(avg),b.push_back(y[i]-1); se.insert({a.back(),b.back()}); } else { u.push_back(i),v.push_back(j); a.push_back(avg),b.push_back(y[i]+1); se.insert({a.back(),b.back()}); } } nei[j].erase(i); } 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...