유사코2 BOJ 15586 - Moo tube ( 오프라인 쿼리, 유니온 파인드 ) https://www.acmicpc.net/problem/15586 왜 정답률이 65퍼인지 궁금한 문제 자연수 가중치가 있는 트리가 주어진다. 정점 u~v경로 상의 가중 치 중 가장 작은 값을 usado(u,v)라고 한다. 최대 1e5개의 쿼리 (ki, vi)가 주어진다. vi와 연결된 정점 중 유사도가 ki이상인 정점의 수를 구하라. V^2에 풀수있지만 TLE. 아예 다른방법으로 접근해야 한다. 임의의 정점에 대해 유사도 ki이상인 정점을 구하려면 가중치가 ki이상인 간선들만 필요하다. ->가중치가 ki 이상인 간선들로만 이뤄진 스패닝 트리를 두고 생각하면 편해진다. 쿼리를 ki에 대해 내림차순으로 정렬하고 간선도 가중치 기준으로 내림차순 정렬한다. 쿼리를 순차로 보면서, ki이상의 가중치를 가진 간선.. 2020. 2. 19. BOJ 15475 - A pie for a pie (이분그래프, 이분탐색) https://www.acmicpc.net/problem/15457 유사코 골드. bessie와 elsie가 서로 선물을 교환한다. 같은 선물에 대해 각자 생각하는 가치가 다를 수 있다. 최대 1e5개의 선물을 둘이 같은 개수만큼 가지고 있다. 서로 선물을 교환하려 한다. 예를들어, bessie가 볼때 3의 가치를 지닌 선물을 bessie가 받은 경우 3이상 3+d이하(bessie기준)선물을 elsie에게 보답으로 준다. elsie도 마찬가지다. 이런 방법으로 계속 선물을 교환할 때, 본인이 생각했을 때 가치가 0인 선물을 받으면 성공적으로 선물 교환이 이뤄진 것으로 본다. bessie부터 선물을 주기로 한다. bessie의 i번째 선물을 처음으로 elsie에게 줬을 때 가장 적은 횟수로 성공적인 선물교.. 2020. 2. 18. 이전 1 다음