dhsrhkdgus   2년 전

Persistent segment tree를 구현한 코드입니다.

Fast IO를 안쓰면 TLE가 뜬다고는 하는데 그 이전에 그냥 WA가 뜨네요.

테스트케이스 여러 개 만들어서 해봤을 때 모두 맞았는데 어떤 부분이 틀렸는지 못찾겠습니다.

(cn은 weight를 compress했을 때 개수입니다. 이 문제에서는 다 다르다 했으니까 n이 될거에요)

dongwon0427   2년 전

저도 16%에서 시간 초과가 나요.. ㅜㅜ 왜이러지

dongwon0427   2년 전

저같은 경우는 완전히 틀리게 식을 써놨었네요 ㅎㅎ;

16%까지는 그냥 진행되는 건가봐요. 실수로 freopen을 안 지웠을때도 16%까지는 맞더라구요

dhsrhkdgus   2년 전

그렇군요 다시 확인해봐야겠네요

정보 감사합니다

dongwon0427   2년 전

LCA 함수를 보니까

두 노드들이 조상 관계일 때 예외처리를 안 하신 것 같네요.

그 경우에는 이미 두 노드들이 같기 때문에

두번째 루프에서 더 올라가지 않게 되고

LCA의 조상이 리턴됩니다

dhsrhkdgus   2년 전

아 u==v 빼먹었네요ㅋㅋ

if(u==v) return u

추가하니까 맞았습니다 나왔네요

감사합니다~

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