느리게 짠 O(NM) 풀이를 썼다가 시간 초과를 받아서 wnsdl1659님의 데이터를 보고 메모제이션만 추가했는데 276ms로 통과합니다.
이외에도 파이썬 코드 중 실행 시간이 빠른 코드들을 보면, 78254429번과 같이 저처럼 O(NM)으로 TLE를 받았다가 메모제이션으로 통과한 코드들이 꽤 있는 거 같습니다.
시간 초과 코드 (82538528번) -> 메모제이션 코드 (82538494번)
아래 코드로 생성한 데이터로는 82538494번(Python3) 제출이 시간 초과를 받아야 합니다.
wnsdl1659님의 데이터처럼 두 갈래로 나뉘어지지만 매번 다른 쿼리가 입력되는 데이터가 필요할 거 같습니다.
특정 케이스를 텍스트로 제출하려고 했는데 해당 케이스만 예외 처리하기 쉬울 거 같아 코드로 제출합니다.
코드가 생성하는 트리의 구조는 아래처럼 되어있고, 양 갈래 끝에 있는 100개의 노드들로 이루어진 9990개의 쿼리와, 같은 갈래에 있는 두 노드로 이루어진 쿼리 10개를 생성합니다.
[ 트리 구조 ]
Θ 루트 노드 (1번)
│
.
. 2 ~ 10개의 서브 노드 (랜덤)
.
│
Θ 서브 루트 (랜덤)
┌──────┴──────┐
Θ Θ
│ │
Θ Θ
│ │
. .
. . 남은 모든 노드 (랜덤)
. .
│ │
Θ Θ
│ │
Θ Θ
[ 입력 ]
노드 수 : 50000개
쿼리 수 : 10000개 = 양 갈래 마지막의 두 노드가 주어지는 경우 9990개 + 한 갈래의 두 노드가 주어지는 경우 10개
[ 정답 ]
서브 루트 x 9990번 + 10개의 특수 쿼리에 맞는 답 10번
kimryungyo 2년 전 2
느리게 짠 O(NM) 풀이를 썼다가 시간 초과를 받아서 wnsdl1659님의 데이터를 보고 메모제이션만 추가했는데 276ms로 통과합니다.
이외에도 파이썬 코드 중 실행 시간이 빠른 코드들을 보면, 78254429번과 같이 저처럼 O(NM)으로 TLE를 받았다가 메모제이션으로 통과한 코드들이 꽤 있는 거 같습니다.
wnsdl1659님의 데이터처럼 두 갈래로 나뉘어지지만 매번 다른 쿼리가 입력되는 데이터가 필요할 거 같습니다.
특정 케이스를 텍스트로 제출하려고 했는데 해당 케이스만 예외 처리하기 쉬울 거 같아 코드로 제출합니다.
코드가 생성하는 트리의 구조는 아래처럼 되어있고, 양 갈래 끝에 있는 100개의 노드들로 이루어진 9990개의 쿼리와, 같은 갈래에 있는 두 노드로 이루어진 쿼리 10개를 생성합니다.
[ 트리 구조 ] Θ 루트 노드 (1번) │ . . 2 ~ 10개의 서브 노드 (랜덤) . │ Θ 서브 루트 (랜덤) ┌──────┴──────┐ Θ Θ │ │ Θ Θ │ │ . . . . 남은 모든 노드 (랜덤) . . │ │ Θ Θ │ │ Θ Θ [ 입력 ] 노드 수 : 50000개 쿼리 수 : 10000개 = 양 갈래 마지막의 두 노드가 주어지는 경우 9990개 + 한 갈래의 두 노드가 주어지는 경우 10개 [ 정답 ] 서브 루트 x 9990번 + 10개의 특수 쿼리에 맞는 답 10번