Submission #440569

#TimeUsernameProblemLanguageResultExecution timeMemory
440569MetalPowerFountain Parks (IOI21_parks)C++17
100 / 100
776 ms81016 KiB
#include <bits/stdc++.h> using namespace std; #include "parks.h" #define pii pair<int, int> #define fi first #define se second #define mp make_pair const int MX = 2e5 + 10; int dx[4] = {2, -2, 0, 0}, dy[4] = {0, 0, 2, -2}; int dgx[4] = {1, 1, -1, -1}, dgy[4] = {1, -1, 1, -1}; pii pos[MX]; map<pii, int> nd; bool vis[MX]; void dfs(int u){ vis[u] = true; int nx = pos[u].fi, ny = pos[u].se; for(int i = 0; i < 4; i++){ int v = nd[mp(nx + dx[i], ny + dy[i])]; if(v != 0 && !vis[v]) dfs(v); } } // if there doesn't exist 2 * 2 squares // we can color the 2 * 2 cells by black or white like a chess board // if it is black color the left or right // if it is white color the up or down // We know that for every color at most direction exists because there doesn't exist 2 * 2 squares /* void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b){ int N = u.size(); for(int i = 0; i < N; i++){ printf("edge %d - %d and bench at (%d, %d)\n", u[i], v[i], a[i], b[i]); } } */ vector<pii> pts; int construct_roads(vector<int> x, vector<int> y){ int N = x.size(); vector<int> u, v, a, b; // u - v the fountains, (a, b) the index of the bench for(int i = 0; i < N; i++){ pos[i + 1] = mp(x[i], y[i]); nd[pos[i + 1]] = i + 1; for(int j = 0; j < 4; j++) pts.push_back(mp(x[i] + dgx[j], y[i] + dgy[j])); } dfs(1); for(int i = 0; i < N; i++) if(!vis[i + 1]) return 0; sort(pts.begin(), pts.end()); pts.resize(unique(pts.begin(), pts.end()) - pts.begin()); for(auto p : pts){ bool st = ((p.fi >> 1) + (p.se >> 1)) & 1; if(st){ // left or right if(nd[mp(p.fi - 1, p.se - 1)] && nd[mp(p.fi - 1, p.se + 1)]){ u.push_back(nd[mp(p.fi - 1, p.se - 1)]); v.push_back(nd[mp(p.fi - 1, p.se + 1)]); a.push_back(p.fi); b.push_back(p.se); }else if(nd[mp(p.fi + 1, p.se - 1)] && nd[mp(p.fi + 1, p.se + 1)]){ u.push_back(nd[mp(p.fi + 1, p.se - 1)]); v.push_back(nd[mp(p.fi + 1, p.se + 1)]); a.push_back(p.fi); b.push_back(p.se); } }else{ // up or down if(nd[mp(p.fi - 1, p.se + 1)] && nd[mp(p.fi + 1, p.se + 1)]){ u.push_back(nd[mp(p.fi - 1, p.se + 1)]); v.push_back(nd[mp(p.fi + 1, p.se + 1)]); a.push_back(p.fi); b.push_back(p.se); }else if(nd[mp(p.fi - 1, p.se - 1)] && nd[mp(p.fi + 1, p.se - 1)]){ u.push_back(nd[mp(p.fi - 1, p.se - 1)]); v.push_back(nd[mp(p.fi + 1, p.se - 1)]); a.push_back(p.fi); b.push_back(p.se); } } } for(auto& p : u) p--; for(auto& p : v) p--; build(u, v, a, b); return 1; } /* int main(){ int N; vector<int> x, y; scanf("%d", &N); x.resize(N); y.resize(N); for(int i = 0; i < N; i++) scanf("%d %d", &x[i], &y[i]); printf("%d\n", construct_roads(x, y)); } */
#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...