글 읽기 - 50%에서 자꾸 틀립니다..

kj9203 6년 전 0

계속 50%에서 틀렸다고 나오는데 어디가 잘못된건지 도저히 모르겠네요... MST로 간선을 그릴 때 벽이 이어지면 그만두도록 하려고

union과정에서 root의 정보를 갱신하면서 root의 정보가 같을때 break하게 구현했는데 어디가 잘못된걸까요..

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
int uf[1004];
int n;
int find(int a) {
	if (uf[a] == a) return a;
	return uf[a] = find(uf[a]);
}

bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return false;
	for (int i = 0; i <= n + 1; i++) {
		if (uf[i] == a) uf[i] = b;
	}
	return true;
}
double dist(int x1, int y1, int x2, int y2) {
	return sqrt(abs(x1 - x2)*abs(x1 - x2) + abs(y1 - y2)*abs(y1 - y2));
}

bool comp(tuple<int, int, double> a, tuple<int, int, double> b) {
	return get<2>(a) < get<2>(b);
}
int main() {
	int T;
	cin >> T;
	while (T > 0) {
		int W;
		vector < tuple<int, int, double>>e;
		T--;
		int x[1004], y[1004], r[1004];
		cin >> W;
		cin >> n;
		for (int i = 1; i <=n; i++) {
			cin >> x[i] >> y[i] >> r[i];
		}
		for (int i = 1; i <=n; i++) {
			for (int j = 1; j <=n; j++) {
				if (i == j) continue;
				e.push_back(tuple<int, int, double>(i, j, max(0.0, dist(x[i], y[i], x[j], y[j]) - r[i] - r[j])));
			}
		}
		for (int i = 1; i <=n; i++) {
			e.push_back(tuple<int, int, double>(i, 0, max(0, x[i] - r[i])));
			e.push_back(tuple<int, int, double>(i, n+1, max(0, W-x[i] - r[i])));
		}
		e.push_back(tuple<int, int, double>(0, n + 1, W));
		sort(e.begin(), e.end(), comp);
		for (int i = 0; i <= n+1; i++) {
			uf[i] = i;
		}
		double result = 0;
		int cnt = 0;
		for (int i = 0; ; i++) {
			int a = get<0>(e[i]), b = get<1>(e[i]);
			if (merge(a, b)) {
				result = get<2>(e[i]);
			}
			if (uf[a] == uf[b] && uf[a] == uf[0] && uf[a] == uf[n + 1]) {
				break;
			}
		}
		printf("%.6lf\n", result / 2);
	}

}

sgchoi5 6년 전 0

http://gooddaytocode.blogspot.... 에 가시면 원래 대회 때의 TC 받을 수 있는 링크가 있습니다.

그 TC 로 잘 되는지 해보시길..

portableangel 6년 전 1

마지막 루프 탈출 종료 조건이 find(0)==find(n+1) 이어야 하지 않을까요?

wagurano 3년 전 2

원인 찾았습니다.

저도 50에서 멈추길래 조건들을 보니

n이 0일때가 있네요.

n 0일때 처리로직이 있어야할 듯 합니다.

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

문제

문제

출처

ICPC

50%에서 자꾸 틀립니다..

kj9203 6년 전 0

sgchoi5 6년 전 0

portableangel 6년 전 1

wagurano 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말