[BOJ] 1613번: 역사

https://www.acmicpc.net/problem/1613


$a$가 $b$ 보다 먼저 발생한 사건이면 $adj[a]$에 $b$를 추가합니다. 그리고 1, 2, ... , $N$에서 flood fill을 돌리면 각 사건들에 대해 나보다 먼저 발생한 사건의 목록을 알 수 있고 이를 미리 $state[i][j]$에 저장해두면 $O(NK+S)$에 해결할 수 있습니다.


만약 $N$이 더 컸다면 LCA를 이용해 $O((K+S)lgN)$에 해결할 수 있었을 것입니다.


https://github.com/blisstoner/BOJ/blob/master/1613.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 4485번: Obstacle Course  (0) 2019.02.18
[BOJ] 1280번: 나무 심기  (0) 2019.02.13
[BOJ] 1256번: 사전  (0) 2019.02.13
[BOJ] 1613번: 역사  (0) 2019.02.13
[BOJ] 9372번: 상근이의 여행  (0) 2019.02.13
[BOJ] 1939번: 중량제한  (0) 2019.02.13
[BOJ] 15683번: 감시  (2) 2019.02.06
  Comments
댓글 쓰기