글 읽기 - 테스트 케이스의 개수..?

medic_programmer 7년 전 1

혹시 테스트 케이스의 개수가 몇 개인지 알 수 있을까요?

표준적이라고 생각하는(?) 유니온 파인드 알고리즘을 썼는데 시간초과가 나오네요 ㅠㅠ

map의 시간복잡도가 lgN이니까 전체 알고리즘의 복잡도는 애커만 상수를 무시할 때 NlgN이 되어 안전하게 통과해야 하는 것 같은데 ㅠㅠ

#include<iostream>
#include<stdio.h>
#include<map>
#include<string>
#define M 200001

using namespace std;

int n,Rank[M],count[M],pnt,parent[M];
map<string,int> index;

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

void process()
{
	string a,b;
	int pa,pb,t,i;
	
	index.clear();
	pnt = 0;
	
	scanf("%d",&n);
	
	for(i=1; i<=n*2; i++){
		parent[i] = i;
		count[i] = 1;
	}
	
	for(i=1; i<=n; i++){
		
		cin>>a>>b;
		
		if(index.count(a) == 0) index[a] = ++pnt;
		if(index.count(b) == 0)	index[b] = ++pnt;
		
		pa = findParent(index[a]); pb = findParent(index[b]);
		
		if(pa == pb){
			printf("%d\n",count[pa]);
			continue;
		}
		
		if(Rank[pa] == Rank[pb]) Rank[pa]++;
		else if(Rank[pa] < Rank[pb]){
			t = pa; pa = pb; pb = t;
		}
		
		parent[pb] = pa;
		count[pa] += count[pb];
		printf("%d\n",count[pa]);
	}
}

int main()
{
	int TC,i;
	
	cin>>TC;
	
	for(i=1; i<=TC; i++) process();
	return 0;
}

koosaga 7년 전 1

union find가 느린게 문제인거 같지는 않고 cin cout을 scanf printf로 바꿔보세요

medic_programmer 7년 전 0

그러면 string 입력을 못 받지 않나요?

map은 필연적으로 써야 하는 것 같은데..

medic_programmer 7년 전 0

아 됐습니다!

제가 string에 대해 잘못 이해하고 있었네요

감사합니다~

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

문제

문제

출처

ICPC

테스트 케이스의 개수..?

medic_programmer 7년 전 1

koosaga 7년 전 1

medic_programmer 7년 전 0

medic_programmer 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말