Submission #218635

#	Time	Username	Problem	Language	Result	Execution time	Memory
218635		KCSC	Park (BOI16_park)	C++14	100 / 100	456 ms	37624 KiB

park

#include <bits/stdc++.h>
using namespace std;

const int NMAX = 2005;
const int MMAX = 100005;
const double EPS = 0.000001;

struct Circle {
	int x, y, r;
} crc[NMAX];

struct Edge {
	int x, y; 
	double d;
} edg[NMAX * NMAX];

struct Event {
	int x, r, id;
} evn[MMAX];

int fth[NMAX], mrk[4], com[4];
string ans[MMAX]; 
vector<int> gph[4];

inline int sign(double d1, double d2) {
	if (fabs(d1 - d2) < EPS)
		return 0;
	return d1 < d2 ? -1 : 1;
}

inline int getRoot(int x) {
	while (fth[x] > 0)
		x = fth[x];
	return x;
}

void dfs(int x) {
	mrk[x] = true;
	for (int y = 0; y < 4; ++y) {
		bool ok = true;	
		for (int z : gph[x])
			if (y == z)
				ok = false;
		if (ok and !mrk[y])
			dfs(y);
	}
}

int main(void) {
#ifdef HOME
	freopen("park.in", "r", stdin);
	freopen("park.out", "w", stdout);
#endif
	int n, m; cin >> n >> m;
	int w, h; cin >> w >> h;
	for (int i = 1; i <= n; ++i) 
		cin >> crc[i].x >> crc[i].y >> crc[i].r;
	int k = 0;
	for (int i = 1; i <= n; ++i) {
		edg[++k] = {n + 1, i, crc[i].x - crc[i].r};
		edg[++k] = {n + 2, i, crc[i].y - crc[i].r};
		edg[++k] = {n + 3, i, w - crc[i].x - crc[i].r};
		edg[++k] = {n + 4, i, h - crc[i].y - crc[i].r};
		for (int j = i + 1; j <= n; ++j) 
			edg[++k] = {i, j, hypot(abs(crc[i].x - crc[j].x), abs(crc[i].y - crc[j].y)) - crc[i].r - crc[j].r};
	}
	sort(edg + 1, edg + k + 1, 
		[](const Edge &e1, const Edge &e2) {
			return sign(e1.d, e2.d) < 0;
		}
	);
	for (int i = 1; i <= m; ++i) {
		cin >> evn[i].r >> evn[i].x;
		evn[i].id = i; evn[i].r *= 2;
	}
	sort(evn + 1, evn + m + 1, 
		[](const Event &e1, const Event &e2) {
			return sign(e1.r, e2.r) < 0;
		}
	);
	for (int i = 1; i <= n + 4; ++i)
		fth[i] = -1;
	for (int i = 1, j = 1; i <= m; ++i) {
		for (; j <= k and sign(edg[j].d, evn[i].r) < 0; ++j) {
			int x = getRoot(edg[j].x), y = getRoot(edg[j].y);
			if (x == y)
				continue;
			if (fth[x] > fth[y])
				swap(x, y);
			fth[x] += fth[y]; fth[y] = x;
		}
		for (int p = 0; p < 4; ++p) {
			gph[p].clear();
			mrk[p] = false;
		}
		for (int p = 0; p < 4; ++p) { 
			com[p] = getRoot(p + n + 1);
			for (int q = 0; q < p; ++q) {
				if (com[p] == com[q]) {
					for (int a = p; a != q; a = ((a + 1) & 3)) 
					for (int b = q; b != p; b = ((b + 1) & 3)) { 
						gph[a].push_back(b);
						gph[b].push_back(a);
					}
				}
			}
		}
		dfs(evn[i].x - 1);
		for (int p = 0; p < 4; ++p)
			if (mrk[p])
				ans[evn[i].id].push_back(char(p + '1'));
	}
	for (int i = 1; i <= m; ++i)
		cout << ans[i] << "\n";
	return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:60:34: warning: narrowing conversion of '(crc[i].Circle::x - crc[i].Circle::r)' from 'int' to 'double' inside { } [-Wnarrowing]
   edg[++k] = {n + 1, i, crc[i].x - crc[i].r};
                         ~~~~~~~~~^~~~~~~~~~
park.cpp:61:34: warning: narrowing conversion of '(crc[i].Circle::y - crc[i].Circle::r)' from 'int' to 'double' inside { } [-Wnarrowing]
   edg[++k] = {n + 2, i, crc[i].y - crc[i].r};
                         ~~~~~~~~~^~~~~~~~~~
park.cpp:62:38: warning: narrowing conversion of '((w - crc[i].Circle::x) - crc[i].Circle::r)' from 'int' to 'double' inside { } [-Wnarrowing]
   edg[++k] = {n + 3, i, w - crc[i].x - crc[i].r};
                         ~~~~~~~~~~~~~^~~~~~~~~~
park.cpp:63:38: warning: narrowing conversion of '((h - crc[i].Circle::y) - crc[i].Circle::r)' from 'int' to 'double' inside { } [-Wnarrowing]
   edg[++k] = {n + 4, i, h - crc[i].y - crc[i].r};
                         ~~~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42