글 읽기 - [Python] LCA 시간초과를 어떻게 해결할 수 있을지 궁금합니다.

iron1209 4년 전 0

LCA - Sparse Table을 구성하는 알고리즘을 작성했는데도 Cpp로는 통과해도 파이썬으로는 통과하기가 힘든것 같은데 어떤 부분에서 시간을 줄일 수 있을지 조언을 구합니다.

__import__('sys').setrecursionlimit(10**6)
input=__import__('sys').stdin.readline
def dfs(v):
    for i in con[v]:
        if depth[i]==-1:
            dp[i][0]=v
            depth[i]=depth[v]+1
            dfs(i)
N=int(input())
con=[[]for _ in range(N+1)]
dp=[[-1]*(18)for _ in range(N+1)]
depth=[0,0]+[-1]*(N-1)
for _ in range(N-1):
    a,b=map(int,input().split())
    con[a].append(b)
    con[b].append(a)
dfs(1)
for i in range(0,17):
    for j in range(1,N+1):
        if dp[j][i]!=-1:
            dp[j][i+1]=dp[ dp[j][i] ][i]
M=int(input())
for _ in range(M):
    a,b=map(int,input().split())
    if depth[a]<depth[b]:
        a,b=b,a
    diff=depth[a]-depth[b]
    i=0
    while diff!=0:
        if diff%2: a=dp[a][i]
        diff//=2
        i+=1
    if a!=b:
        for i in range(17,-1,-1):
            if dp[b][i]!=dp[a][i]:
                a,b=dp[a][i],dp[b][i]
        a=dp[a][0]    
    print(a)

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

문제

문제

출처

ICPC

[Python] LCA 시간초과를 어떻게 해결할 수 있을지 궁금합니다.

iron1209 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말