글 읽기 - 시간초과, 시간을 더 줄일 수 있을까요?

wwaa456 4년 전 0

예제의 답은 잘 나옵니다만 시간초과가 뜨네요

시간을 더 줄일 수가 있을까요..

pypy3도 시간 초과네요

import sys
sys.setrecursionlimit(100000)
read = sys.stdin.readline

students = []
check = []
trace = []
cnt = 0

def dfs(n, depth):
    global cnt
    check[n] = 1
    trace[n] = depth
    next = students[n]
    
    if check[next] == 0:
        dfs(next, depth+1)
    else:
        cnt -= depth - trace[n] + 1

t = int(read())
for i in range(t):
    cnt = int(read())
    students = [0] + list(map(int, read().split()))
    check = [0] * len(students)

    for j in range(1, len(students)):
        if check[j] == 0:
            trace = [0] * len(students)
            dfs(students[j], 1)

    print(cnt)

sait2000 4년 전 0

지금 trace를 최대 대략 len(students)-1번 만드니까 O(n^2)입니다. 이 정도면 통과 못 합니다. trace를 테케당 한 번만 만드는 방법을 생각해보세요

dnwlscjf167 4년 전 0

아마 답도 다르게 나올 것으로 보이네요

Test case:

1 1 1

넣어보세요

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

문제

문제

출처

ICPC

시간초과, 시간을 더 줄일 수 있을까요?

wwaa456 4년 전 0

sait2000 4년 전 0

dnwlscjf167 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말