블로그 옮겼습니다

문제 링크 \(1\leq{N}\leq{10^5}\)\(1\leq{M}\leq{2\cdot{10^5}}\)\(1\leq{x,y}\leq{10^6}\) 2차원 좌표평면상에 도시의 개수 N이 주어지고 N개의 줄에 각 도시의 x,y 좌표가 주어진다.그리고 쿼리의 수 M이 주어지는데 각 쿼리의 동작은 두가지다. road a b : 도시 a와 b 사이에 직선 도로를 이어 하나의 state 로 만든다.line c : x축에 평행하게 y = c 직선을 그어 한 도로라도 이 직선에 교차되는 state 들의 수와그 state 들의 도시 수의 합을 출력한다. c는 무조건 1.5, 5.5 등 ~~.5 의 형태이며 도로들은 서로 교차하지 않는다. \(0\lt{c}\lt{10^6}\) 서로다른 state 가 도로에 의해 하나의 ..

Union-find 다른 말로 Disjoint sets(상호 배타적 집합) 이란 여러개의 집합들에 대해,서로 다른 두 집합의 교집합이 공집합이며, 모든 집합들의 합집합이 전체 집합이 되는 집합들을 말한다.그런데 이게 유용한 이유는 이렇다. 1. 서로 다른 두 원소가 같은 집합 내에 속해 있는지, 아니면 서로 다른 집합에 속해있는 지를 빠른 시간내에 구할 수가 있다.2. 서로 다른 집합에 속해있는 두 노드가 속해있는 두 집합을 빠른시간에 합쳐 더 큰 하나의 집합으로 만들 수가 있다. 그렇기 때문에 크루스칼 알고리즘에서도 유용하며, dfs 대용으로도 쓸 수가 있으며 그 활용이 무궁무진하다.그런데 일반적인 방법으로는 집합을 한꺼번에 합치는 것은 가능하지만, 집합 내의 특정 한 원소 단위로는옮길 수가 없다. 하..

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3138 정말 좋은 문제인것 같다. 풀이

https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=4075 해석이 너무 안돼서 제대로 이해하는데 엄청 오래걸렸다.. \(5\leq{N}\leq{2\cdot{10^4}}\)\(0\leq{M}\leq{2\cdot{10^5}}\)N은 회사의 수, M은 쿼리의 수N개의 회사는 각각 센터를 가지고 있다. 이 회사들의 일부를 병합을 하여 하나의 더 큰 덩어리로 만드는 동시에센터는 하나로 유지를 하려고 한다. 병합을 할 때에는 하나의 덩어리의 센터에서 나머지 덩어리의 아무 회사로도로를 놓으면서 병합을 한다. 도로의 길이는 회사 a와 b를 이을 때 | a - b| mod 10..

https://oj.uz/problem/view/KRIII5_YZ \(1\leq{N,M}\leq{400}\)N x M 의 격자가 주어진다. 격자의 각 칸은 'B' 또는 'W' 이다.이 격자를 상하좌우대각선으로 무한히 이어붙였을때 무늬가 나타날 것이다. 여기에는 같은 색끼리 상하좌우로붙어있기도하고 혼자있기도 할텐데 이 같이 붙어있는 수를 각 칸마다 구하는 문제이다. 무한히 많은 같은색 칸이붙게 되는 칸은 -1 을 출력한다.예를 들어 이 경우에는 답이2 2 -1-1 -1 -1이 된다.흰 칸들은 모두 무한히 이어지며, 검은칸들은 각각 두개씩 붙어있기 때문이다. 그럼 이문제를 어떻게 풀까?dfs로도 풀 수가 있겠지만 구현도 쉽고, 예외처리해줄것도 적어 깔끔한 유니온 파인드로 풀어보자.모든 칸들에 대해 상하좌우와..