kimryungyo   2년 전

느리게 짠 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번

startlink   2년 전

재채점했습니다.

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