글 읽기 - 시간초과입니다.......

noisywhitecat 3년 전 0

코드가 좀 거친 건 이해 바랍니다.......

x의 조상들을 리스트에 담아둔 뒤 y의 조상을 하나씩 찾으며 리스트에 있는지 체크해 보았습니다.

당연하게도 예제는 전부 잘 출력됩니다.

시간 초과가 나는 포인트가 보인다면 알려주시면 감사하겠습니다...

import sys

def parent(z, k):
    return (z - 2) // k + 1

N, K, Q = list(map(int, sys.stdin.readline().split()))
for _ in range(Q):
    x, y = list(map(int, sys.stdin.readline().split()))
    if K == 1:
        print(abs(x - y))
        continue

    t = 0
    x_parent = []
    while t != 1:
        if x == 1:
            x_parent = [1]
            break
        t = parent(x, K)
        x_parent.append(t)
        x = t

    counter = 0
    while True:
        if y == 1:
            p = 1
            break
        counter += 1
        p = parent(y, K)
        if p in x_parent:
            break
    print(counter + x_parent.index(p))

dmswl022329 1년 전 0

k가 1일경우

입력이 1 10^15가 들어올 때 10^15 부터 1까지 1씩 거슬러 올라가서 LCA를 찾게 될 겁니다.

이런경우를 생각해보시면 될 것 같습니다.

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

문제

문제

출처

ICPC

시간초과입니다.......

noisywhitecat 3년 전 0

dmswl022329 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말