wakeupear1y   2년 전

단순하게 생각해서 부모를 자식들의 min 값을 놓는 트리를 만들어 놓고, 구간 트리를  사용해서 최소값을 구해주도록 계산하였는데, 시간초과가 나네요..

좀 더 최적화가 필요할까요?

simm4256   2년 전

전처리기 MIN 때문입니다.

min(a,b)를 ((a)<(b)? (a):(b)) 라고 설정하셨는데

보시면 init 함수와 find 함수에서 재귀호출하는 부분에서 min을 사용하셨죠.

그럼 결국 저 재귀호출부분은

find(a) < find(b) ? find(a) : find(b)

라고 전처리될탠데 불필요한 재귀호출이 2개 있죠?


이렇게 바꿔보세요.


int a = find(a);

int b = find(b);

return min(a,b);

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