jh05013   1년 전

bfs를 할 때 pop(0)를 하는 코드가 통과합니다.

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

Pypy3로 아주 평범하게 구현해도 0.7초 안에 풀 수 있습니다.

startlink   1년 전

:appfearful:

startlink   1년 전

재채점했습니다.

Acka   1년 전

@startlink

안녕하세요. 모든 언어에 대한 시간 보너스를 없앤 것에 대해서 문의 드립니다.

Java로 나름 평범하게 구현한 코드가 기존에 1.8초 정도였고, 재채점에서 시간초과를 받았습니다.

LCA 뎁스를 20에서 18로 줄여 1.3초로 맞았습니다를 받긴했는데, C++로는 완전히 같은 로직이 0.1초가 나옵니다.

시간복잡도가 같고 상수가 크게 차이 나는 것도 아니라 구현 방법에 따라 시간초과와 맞았습니다가 갈릴 수 있습니다. 실제로 NlogN 복잡도를 가진 Java/Python 제출이 많이 시간초과를 받았습니다.

저격하신 코드가 파이썬 리스트 자료구조를 제대로 이해하지 못하고 시간복잡도상으로 통과하지 않아야하는 코드인 것에는 동의합니다. 하지만 이 문제가 LCA 기본문제이며 LCA 자체가 다양한 로직으로 짜여질 수 있는 것을 고려할 때, (C 계열 외에서) 1.5초는 상수 경계에 있어 빡빡하지 않나 싶습니다.

문제 제작자가 백준님이고, 시간제한을 수정하신 것이 백준님이니 출제자 의도 역시 그렇구나..라고 넘어가기엔 걸려서, 혹시 시간제한을 0.5초로 설정하고 언어별 시간제한을 그대로 적용하는 것은 어떤가요?

Acka   1년 전

https://www.acmicpc.net/problem/status/11438/55

0.5초 이상의 C++코드가 딱 세개 있는데, 모두 부분로직미스/함수반복호출 등으로 시간초과를 받는게 맞는 것 같네요.

spectaclehong   1년 전

위 status에 c++ 에서 유난히 느리게 동작하는 코드를 시간초과 내는 데이터를 추가요청 했습니다.

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

startlink   1년 전

제가 Java 코드를 두 가지 방법으로 구현했는데요.

Scanner와 System.out을 사용하면 1784ms, BufferedReader와 BufferedWriter를 사용하면 1056ms가 걸렸습니다. 1.5초면 될 것 같습니다.

startlink   1년 전

위에서 두 가지 방법은 입/출력 방식을 다르게 한 두 가지 방법이 아니고, DP결과를 이용해서 LCA를 다르게 구하는 두 방법을 말하는데, 쓰고보니 굳이 없어도 될 내용이었네요.

Acka   1년 전

ㅠㅠ 알겠습니다.

startlink   1년 전

Java의 시간 제한을 2.5초로 수정했습니다.

startlink   1년 전

재채점했습니다.

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