[일반] 이런 거 진짜 안 올리는데 코드 좀 봐줄 분

[익명(115.140)]

어제자 코포 G번 왜 터지는지 모르겠어 너무 답답해ㅐ

https://codeforces.com/contest/1714/submission/166586485

[익명(182.231)]

이분탐색도 없고 이분탐색 자료구조나 함수도 없고 완탐돌리니까 TLE난거 아님? - dc App

[익명(115.140)]

이분 탐색 없어도 O(N) 코드 아님? dfs인데

[익명(182.231)]

모든 n개 점을 순회하는 것만 이미 o(n)인데 각각에서 b값을 어떻게 빠르게 찾을거임 일일히 올라가면서 찾으면 o(n^2)임. 일직선 트리 생각해보셈 - dc App

[익명(115.140)]

이미 지나온 b를 큐에 저장하고 po 변수로 포인터처럼 관리해주고 있어서 b값 찾는 게 전체 코드에서 O(n) 걸리지 않음? 한 번 다시 봐야겠네

[익명(182.231)]

b가 순증가해서 일직선트리는 반례가 아닐 수 있네 완전 이진 트리 생각해보면 될듯 - dc App

[익명(115.140)]

더 고민해볼게 봐줘서 고마움