글 읽기 - 제 풀이가 시간초과되어야 하는데 정답이라고 뜹니다

rlarudgh2017 1년 전 2

BFS 시간복잡도가 정점의 제곱이라고 알고 있습니다. 아래 풀이가 제가 푼 풀이인데 수빈이와 동생이 만나지 않을 경우, 500000개의 정점을 다 탐색해서 정점제곱하면 (5 * 10^5)^2 입니다. 시간 제한이 0.25초이니 0.25 * 10^8인데 어떻게 제 풀이가 통과되는 거죠???

from collections import deque

n, k = map(int, input().split())
visited = [[987654321] * 500001 for _ in range(2)]

def bfs(start, end):
    q = deque([(start, 0)])
    visited[0][start] = 0
    brother = [-1] * 500001
    while q:
        cur, time = q.popleft()
        for nxt in [cur - 1, cur + 1, cur * 2]:
            if nxt < 0 or nxt > 500000 or visited[(time + 1) % 2][nxt] <= time + 1:
                continue
            q.append((nxt, time + 1))
            visited[(time + 1) % 2][nxt] = time + 1
    brother[end] = 0
    step = 1
    cur = end
    while cur < 500001:
        if visited[brother[cur] % 2][cur] <= brother[cur]:
            return brother[cur]
        nxt = cur + step
        if nxt < 500001:
            brother[nxt] = brother[cur] + 1
        step += 1
        cur = nxt
    return -1

print(bfs(n, k))

alsrb9936 1년 전 1

인접 행렬이면 정점 제곱인데

인접리스트로 푸시면 시간복잡도 정점 + 간선입니다

통과하시겠네요

fallguy1250 8달 전 7

제 풀이는 정답이여야되는데 시간초과라 뜹니다.

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

문제

문제

출처

ICPC

제 풀이가 시간초과되어야 하는데 정답이라고 뜹니다

rlarudgh2017 1년 전 2

alsrb9936 1년 전 1

fallguy1250 8달 전 7

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말