mythofys   1년 전

제출번호 96495706, 96536508, 96536564

https://www.acmicpc.net/board/...

해당하는 몇 개의 데이터입니다.

1번 데이터는 해당 댓글을 그대로 구현하여 O(nmlogn)의 시간복잡도를 가지게 하는 pq에서 큰 가중치부터 보거나 queue를 사용한 풀이를 저격한 데이터입니다.

2번 데이터는 1번 데이터에서 모든 가중치를 0으로 바꾼 데이터입니다.

3번 데이터는 1번 데이터에서 간선의 순서를 적절히 바꿔 stack를 저격한 데이터입니다.

Input

1.in

Answer

99003

Input

2.in


Answer

0

Input

3.in

Answer

99003

이론상 O(M^2)이 걸리는 데이터까지 만들 수 있을 것 같은데 그건 이 데이터가 추가되어도 저 코드들이 안 막힌다면 시도해보겠습니다...

(수정)

https://www.acmicpc.net/source...

assert문을 통해 시도한 결과 해당 코드들이 정점을 2천만 번 이상 방문하게 하는 데이터가 존재하지 않습니다. 위 데이터들은 해당 코드들이 정점을 1억번 정도 방문하게 하는 데이터입니다.

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