oj.uz

Submission #218635

# Submission time Handle Problem Language Result Execution time Memory
218635 2020-04-02T12:25:12 Z KCSC Park (BOI16_park) C++14
100 / 100
 456 ms 37624 KB 
#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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 34936 KB Output is correct
2 Correct 338 ms 34936 KB Output is correct
3 Correct 335 ms 34936 KB Output is correct
4 Correct 340 ms 34936 KB Output is correct
5 Correct 337 ms 34936 KB Output is correct
6 Correct 338 ms 34936 KB Output is correct
7 Correct 284 ms 35064 KB Output is correct
8 Correct 273 ms 34936 KB Output is correct
9 Correct 6 ms 3456 KB Output is correct
10 Correct 6 ms 3456 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 6452 KB Output is correct
2 Correct 127 ms 6336 KB Output is correct
3 Correct 123 ms 6392 KB Output is correct
4 Correct 129 ms 6392 KB Output is correct
5 Correct 125 ms 6392 KB Output is correct
6 Correct 119 ms 6392 KB Output is correct
7 Correct 131 ms 6136 KB Output is correct
8 Correct 131 ms 6264 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 34936 KB Output is correct
2 Correct 338 ms 34936 KB Output is correct
3 Correct 335 ms 34936 KB Output is correct
4 Correct 340 ms 34936 KB Output is correct
5 Correct 337 ms 34936 KB Output is correct
6 Correct 338 ms 34936 KB Output is correct
7 Correct 284 ms 35064 KB Output is correct
8 Correct 273 ms 34936 KB Output is correct
9 Correct 6 ms 3456 KB Output is correct
10 Correct 6 ms 3456 KB Output is correct
11 Correct 121 ms 6452 KB Output is correct
12 Correct 127 ms 6336 KB Output is correct
13 Correct 123 ms 6392 KB Output is correct
14 Correct 129 ms 6392 KB Output is correct
15 Correct 125 ms 6392 KB Output is correct
16 Correct 119 ms 6392 KB Output is correct
17 Correct 131 ms 6136 KB Output is correct
18 Correct 131 ms 6264 KB Output is correct
19 Correct 450 ms 37548 KB Output is correct
20 Correct 445 ms 37496 KB Output is correct
21 Correct 446 ms 37496 KB Output is correct
22 Correct 449 ms 37368 KB Output is correct
23 Correct 456 ms 37624 KB Output is correct
24 Correct 385 ms 37624 KB Output is correct