oj.uz

답안 #63847

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63847 2018-08-03T05:16:30 Z ainta(#1864) Park (BOI16_park) C++11
0 / 100
 311 ms 24036 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int n, m, W, H;
struct point {
	int x, y, r;
}w[2010];
struct Edge {
	int a, b, c;
	bool operator < (const Edge &p)const {
		return c < p.c;
	}
}Ed[3010000];
int cnt, UF[2040], D[5][5];
int Find(int a) {
	if (a == UF[a])return a;
	return UF[a] = Find(UF[a]);
}
void Merge(int a, int b, int c) {
	a = Find(a), b = Find(b);
	if (a == b)return;
	for (int i = 1; i <= 4; i++) {
		if (Find(n + i) == a) {
			for (int j = 1; j <= 4; j++) {
				if (Find(n + j) == b) {
					D[i][j] = D[j][i] = c;
				}
			}
		}
	}
	UF[a] = b;
}
int Res[5][5];
int main() {
	int i, j;
	scanf("%d%d%d%d", &n, &m, &W, &H);
	for (i = 1; i <= n; i++) {
		scanf("%d%d%d", &w[i].x, &w[i].y, &w[i].r);
	}
	for (i = 1; i <= n; i++) {
		for (j = i + 1; j <= n; j++) {
			long long dx = (w[j].x - w[i].x), dy = (w[j].y - w[i].y);
			long long t = sqrt(dx*dx + dy*dy) - w[i].r - w[j].r;
			t = max(0ll, t - 5);
			while ((t + 1 + w[i].r + w[j].r)*(t + 1 + w[i].r + w[j].r) <= dx*dx + dy*dy)t++;
			t /= 2;
			Ed[cnt++] = { i,j,(int)t };
		}
		Ed[cnt++] = { n + 1, i, w[i].y / 2 };
		Ed[cnt++] = { n + 2, i, w[i].x / 2 };
		Ed[cnt++] = { n + 3, i, (W-w[i].x) / 2 };
		Ed[cnt++] = { n + 4, i, (H-w[i].y) / 2 };
	}
	sort(Ed, Ed + cnt);
	for (i = 1; i <= n + 4; i++) {
		UF[i] = i;
	}
	for (i = 0; i < cnt; i++) {
		Merge(Ed[i].a, Ed[i].b, Ed[i].c);
	}
	Res[1][2] = min(min(D[1][2], D[1][3]), D[1][3]);
	Res[1][3] = min(min(D[1][2], D[1][4]), min(D[3][2], D[3][4]));
	Res[1][4] = min(min(D[2][1], D[2][3]), D[2][4]);
	Res[2][3] = min(min(D[3][1], D[3][2]), D[3][4]);
	Res[2][4] = min(min(D[2][4], D[2][3]), min(D[1][4], D[1][3]));
	Res[3][4] = min(min(D[4][1], D[4][2]), D[4][3]);
	for (i = 1; i <= 4; i++)for (j = 1; j < i; j++)Res[i][j] = Res[j][i];
	while (m--) {
		int a, r, i;
		scanf("%d%d", &r, &a);
		for (i = 1; i <= 4; i++) {
			if (a==i || Res[a][i] >= r)printf("%d", i);
		}
		puts("");
	}
	return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &n, &m, &W, &H);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &w[i].x, &w[i].y, &w[i].r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &r, &a);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 288 ms 23928 KB Output is correct
2 Incorrect 311 ms 24036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 24036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 288 ms 23928 KB Output is correct
2 Incorrect 311 ms 24036 KB Output isn't correct
3 Halted 0 ms 0 KB -