글 읽기 - 50프로에서 왜 틀렸는지 도저히 모르겟습니다.

rkr638 6년 전 0

색칠하기 문제랑 똑같다고 생각해서 풀었는데 50%에서 틀렸다고 하네요...

두시간을 봐도 답이없습니다...

다른방법으로 다시 풀면 할수는있는데 그것보다 이 코드가 왜 안되는지 모르겟어요....

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
typedef pair<int, int> pa;

int color[3003];
pa arr[3003];
int RR[3003];
int anc[3003];
int num, ans;
int lenn(pa a, pa b) {
	return (a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second);
}
int fc(int now) {
	int c = color[now];

	while (c != color[c]) {
		c = color[c];
	}
	return c;
}
void find() {
	memset(color, -1, sizeof(color));
	memset(anc, 0, sizeof(anc));
	memset(RR, 0, sizeof(RR));
	ans = 0;
	num = 0;
	scanf("%d", &num);
	for (int i = 0; i < num; i++) {
		scanf("%d %d %d", &arr[i].first, &arr[i].second, &RR[i]);
		color[i] = i;
	}
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			if (i != j && lenn(arr[i], arr[j]) <= (RR[i] + RR[j])*(RR[i] + RR[j])) {
				//printf("[%d %d]\n", i, j);
				color[i] = min(fc(i), fc(j));
				color[j] = min(fc(i), fc(j));
			}
		}
	}

	for (int i = 0; i < num; i++) {
		anc[fc(i)] = 1;
	}

	for (int i = 0; i < num; i++) {
		if (anc[i] == 1)
			ans++;
	}

	printf("%d\n", ans);
	return;
}
int main() {
	int t = 0;
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		find();
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

50프로에서 왜 틀렸는지 도저히 모르겟습니다.

rkr638 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말