글 읽기 - 50% 틀렸습니다.

yepp0112 3년 전 0

Union-Find로 풀었고 예제 전부 다 맞고 게시판에 있는 예외 케이스까지 다 해봤는데도

50%에서 틀렸습니다가 뜨네요..

예외케이스가 도대체 뭘까요...??

코딩 고수님들 반례 부탁드립니다...

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

int parent[5001];

int findParent(int a){
	if(parent[a]==a) return a;
	
	return parent[a]=findParent(parent[a]);
}

void unionParent(int a,int b){
	int x=parent[a];
	int y=parent[b];
	
	if(x<y) parent[y]=x;
	else parent[x]=y;
}

bool compare(int a,int b){
	int x=parent[a];
	int y=parent[b];
	
	if(x==y) return true;
	else return false;
}

int main (){
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int testcase;
	
	cin>>testcase;
	
	for(int i=0;i<testcase;i++){
		fill(parent,parent+5000,0);
		int x[5001]={0, },y[5001]={0, },r[5001]={0, };
		
		int m;
		
		cin>>m;
		
		for(int j=0;j<m;j++){
			cin>>x[j]>>y[j]>>r[j];
			
			parent[j]=j;
		}
		
		for(int j=0;j<m;j++){
			for(int k=j+1;k<m;k++){
				int disx=(x[j]-x[k])*(x[j]-x[k]);
				int disy=(y[k]-y[k])*(y[j]-y[k]);
				
				int disr=(r[j]+r[k])*(r[j]+r[k]);
				
				int dis=disx+disy;
				
				if(dis<=disr){
					unionParent(j,k);
				}
			}
		}
		
		int count=0;
		for(int j=0;j<m;j++){
			if(parent[j]==j) count++;
		}
		
		cout<<count<<'\n';
	}	
	return 0;
}

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

문제

문제

출처

ICPC

50% 틀렸습니다.

yepp0112 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말