글 읽기 - [파이썬]런타임 에러 이유를 모르겠습니다.

closet0426 4년 전 0

정답은 알맞게 구하는 것 같은데,,

런타임 에러의 이유를 도저히 모르겠습니다.

도와주시면 감사하겠습니다...

from math import inf
import sys
from collections import deque
input = sys.stdin.readline

def dfs(cur):
    for link in node[cur]:
        if (d[link] == inf):
            d[link] = d[cur] + 1
            p[link].append(cur)
#p[link][-1] : 방금 추가된 parent
#p[p[link][-1]] #방금 추가된 parent의 조상
            for num in range(1,n+1):
                if (len(p[p[link][-1]]) >= num) :
                    p[link].append(p[p[link][-1]][num-1])
            dfs(link)
            
def find_lca(a,b):
    if d[b] > d[a]:
        a, b = b, a #d[a]가 항상 더 크다
    for i in range(len(p[a])-1,-1,-1):
        if (d[a] - d[b] >= (1<<i)): 
            a = p[a][i] 
    #최종족으로 d[a] == d[b]를 만족한다
    if a == b : return a
    for i in range(len(p[a])-1,-1,-1):
        if p[a][i] != p[b][i]: #공통 조상을 갖지 않는다면
            a = p[a][i] #a,b를 update한다
            b = p[b][i]
    return p[a][0] #최종 update된 값의 부모노드가 LCA로 확정된다
    
n = int(input().strip())
node = [[] for i in range(n+1)]
d = [inf for i in range(n+1)]
p = [[] for i in range(n+1)] #p[i][j] : ith node's j^2 th ancestors

for i in range(n-1):
    a, b = map(int, input().strip().split())
    node[a].append(b)
    node[b].append(a)
d[1] = 0 #1st node is root
dfs(1)
p[1].append(1) # root에 대해서는 자기 자신을 호출한다

m = int(input().strip())
for i in range(m):
    a, b = map(int, input().strip().split())
    print(find_lca(a,b))

djm03178 4년 전 1

sys.setrecursionlimit(200000)을 넣으면 런타임 에러는 해결되지만, 시간 초과가 됩니다.

closet0426 4년 전 0

그렇군요... 어떤 부분이 시간초과인 걸까요..

djm03178 4년 전 0

모든 간선에 대해 13번째 줄에서 n번 루프를 도니 O(n^2)이겠네요.

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

문제

문제

출처

ICPC

[파이썬]런타임 에러 이유를 모르겠습니다.

closet0426 4년 전 0

djm03178 4년 전 1

closet0426 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말