Submission #440566

#	Time	Username	Problem	Language	Result	Execution time	Memory
440566		MetalPower	Fountain Parks (IOI21_parks)	C++17	0 / 100	1 ms	204 KiB

parks

#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 + 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);
			}
		}
	}

	build(u, v, a, b);
	return 1;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30