유니온파인드6 BOJ 15745 - Snow boots (오프라인 쿼리, 유니온 파인드) https://www.acmicpc.net/problem/15745 최대 1e5개의 음이 아닌 정수 n개가 주어진다. 첫번째와 마지막은 0임이 보장된다. 쿼리 s d가 최대 1e5개 주어진다. 배열에서 s를 초과하는 연속하는 부분수열의 최대 길이 < d인 경우 1을, 그 외엔 0을 출력한다. s에 대해 내림차순으로 query를 정렬한다. 각 쿼리마다 배열에서 서로 인접하면서 s를 초과하는 값을 갖는 인덱스끼리 merge해준다. (한 번 처리한 값을 중복해서 처리하지 않도록 한다) 그러면 각 쿼리마다 집합들 중 최대 크기가 s를 초과하는 연속하는 부분 수열의 길이가 된다. 쿼리마다 O(lgN)에 최대값을 찾고 모든 쿼리에 걸쳐 인덱스에 대해 한번씩만 연산하므로 O(QlgN+N)쯤 될 것 같다. int n,.. 2020. 3. 1. BOJ 17038 - The great revegetation (유니온 파인드, 이분그래프) https://www.acmicpc.net/problem/17038 그래프가 이분그래프인지 아는법 기록 + 온라인쿼리 풀이 숙지 최대 1e5개의 목초지 n개가 있다고 할 때, 소(쿼리) m개가의 정보가 들어온다. 목초지는 두 그룹으로 나뉜다. S a b : a,b목초지가 같은 그룹에 있어야 해. D a b : a,b목초지가 다른 그룹에 있어야 해. 모든 목초지를 나누는 경우의 수를 구하라 오프라인 쿼리. s먼저 입력해서 merge해두고 d를 입력받으면서 a,b의 대표값을 간선으로 이어준다. 그래프가 이분그래프라면 컴포넌트마다 그룹을 나누는 경우가 두가지이므로 2^컴포넌트의 수가 정답. 그래프가 이분그래프가 아니면 그룹을 나눌 수 없다. int n, m, uf[MAX], vst[MAX]; vector ad.. 2020. 2. 22. 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 12012 - Closing the farm (유니온파인드) https://www.acmicpc.net/problem/12012 거꾸로 생각해서 쉬워지는 문제 최대 2e5개의 정점과 간선으로 이뤄진 양방향 그래프가 주어진다. 정점의 개수를 n이라고 할때 쿼리가 n개 들어온다. 각 쿼리에선 정점이 하나 주어지는데(u), 현재 전체 컴포넌트의 수가 1이라면 YES를, 1이상이라면 NO를 출력한 후, 해당 정점과 정점에 연결된 간선을 모두 지운다. 문제 설명대로 완성된 그래프에 간선을 지워가면서 컴포넌트의 수를 log시간 이하로 구하는 것은 매우 어렵다. (불가능한 것 같다) 쿼리를 기록해두고 거꾸로 접근하면, 아무것도 없는 그래프에 정점과 연결된 컴포넌트를 이어주며 컴포넌트의 개수를 유지하는 문제로 바뀐다. 정점u를 추가할 때 이미 그래프에 추가된 정점들에 대해서만 .. 2020. 2. 7. 이전 1 2 다음