2111번 - 선인장
입력의 각 줄의 첫 번째 정수, 즉 경로에 포함된 정점의 개수에 제한이 없다면, 최대 N^2개(약 4억개)까지 가능하며, 이러한 입력이 존재하는 경우 입력만으로 시간초과가 발생하는 경우가 생길 수 있을 것 같습니다.
이에 따라 경로에 포함된 정점의 개수에도 제한이 필요할 것 같습니다.
선인장이 아닌 경우 0을 출력하라는 지문으로 보아 O(N^2)이 여전히 가능해 보입니다.
수정했습니다.
댓글을 작성하려면 로그인해야 합니다.
artichoke42 5년 전 1
입력의 각 줄의 첫 번째 정수, 즉 경로에 포함된 정점의 개수에 제한이 없다면, 최대 N^2개(약 4억개)까지 가능하며, 이러한 입력이 존재하는 경우 입력만으로 시간초과가 발생하는 경우가 생길 수 있을 것 같습니다.
이에 따라 경로에 포함된 정점의 개수에도 제한이 필요할 것 같습니다.