| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 440559 | MetalPower | Fountain Parks (IOI21_parks) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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
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]] = i + 1;
for(int j = 0; j < 4; j++)
pts.push_back(mp(x[i] + dgx[i], y[i] + dgy[i]));
}
` 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);
}
}
}
build(u, v, a, b);
return 1;
}