jhs7jhs   8년 전

PKU 쪽에서는 Accept 받았습니다만, BOJ에서는 시간 초과가 계속 나네요.

시간 제한을 2초 정도로 늘리는 것이 맞지 않을까요?

소스 또한 첨부합니다. 소요 시간 줄이려고 노력했습니다..

-> 소스 지웠습니다

pl0892029   8년 전

이렇게까지 해야될지는 모르겠지만... 한줄씩 입력이 들어온단 부분에서도 시간초를 줄일 수 있고, N과 M의 최대 제한이 완전 그래프에 가깝단 점을 이용하면 메모리 할당 시간을 줄일 수 있겠네요.

jhs7jhs   8년 전

동일한 edge가 여러개 들어올 수 있다는 점에서 착안하여 따로 중복되는 edge를 처리해주는 방법도 사용해보았지만 PKU OJ 기준으로 수행 시간이 더 늘어나는 효과만 있었습니다. vector를 사용하지 않고 배열을 사용하는 경우도 동일하고, vector 대신에 동적 할당을 통해 직접 구현한 stack의 경우도 마찬가지입니다.

pl0892029   8년 전

부연이 너무 없었네요. arr[2000][2000] 으로 체크하는 것을 의미했습니다.

SL fill이나 memset으로 초기화 시간을 메모리 할당/해제 없이 할 수 있기 때문에 빠르단 의미였습니다.

지금 떠오른 다른 방법은 간선을 정렬해서 쓰는 방법인데, 이거는 속도가 어떨지 모르겠습니다. (이 문제에서는 유용할 것 같지 않네요.)

h0ngjun7   8년 전

jhs7jhs   8년 전

ACM-ICPC Live Archive에서 WA가 나왔기 때문에 재고해보겠습니다.

너무나 풀이가 자명한 2-SAT 문제라고 생각했는데 Tarjan이랑 Kosaraju 두 방법 모두 WA가 나와서 당황스럽네요.

jhs7jhs   8년 전

여러분 scanf("%d%d",&n,&m)!=EOF 쓰지 말고 ==2 씁시다

portableangel   8년 전

이 문제 입력이 EOF로 안끝나네요..

while(~scanf("%d %d",&n,&m)) 에서 시간초과, while(scanf("%d %d",&n,&m)==2) 에서 AC가 뜹니다

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