레야몬

1. 문제 나라에는 1부터 N까지 번호가 매겨진 N개의 공항이 있고 M개의 시간 여행이 가능한 비행기가 있다. \((1 \leq N, M \leq 200,000)\). 비행기 \(j\)는 공항 \(c_j\) 시각 \(r_j\)에서 공항 \(d_j\) 시각 \(s_j\)에 착륙한다. \((0 \leq r_j, s_j \leq 10^9, s_j < r_j is possible)\). 게다가 공항에서 환승할 때는 \(a_i\)만큼의 시간이 걸린다. \((1 \leq a_i \leq 10^9)\). Bessie는 도시 1, 시각 0에서 시작할 때 1부터 N까지의 공항으로 각각 도착했을 때 최단 시각은 얼마인가? -1- N, M -M- \(c_j, r_j, d_j, s_j (1 \leq c_j, d_j \leq ..

1. 문제 ACM 왕국의 왕 Mercer가 있다. 그 왕국에는 하나의 수도와 여러 개의 도시로 이루어져 있다. 원래 짜인 도로 건설 계획이 있었으나 비용 절감을 위해 다음과 같은 규칙을 적용하여 도로를 건설하는데 드는 비용을 최소화하려고 한다. 모든 도시는 서로 갈 수 있는 길이 있어야 한다. 도시에서 수도로 가는 최단 거리는 처음 계획과 달라지지 않는다. -1- 도시의 개수 \(N(1 \leq N \leq 10,000)\), 도로의 개수 \(M(0 \leq M \leq 20,000)\) -M- 연결된 두 도시 u_i, v_i, 도로의 거리 d_i, 도로 건설비 c_i \((1 \leq u_i, v_i \leq N, u_i \leq v_i, 1 \leq d_i \leq 1,000, 1 \leq c_i \..

1. 문제 한 심사위원은 반드시 찬성 또는 반대하는 두 사람을 고른다. 심사위원은 자신이 행사한 두 표 모두 반대되는 결과가 나오면 의심한다. 상근이가 포함된 다음 라운드 진출목록을 만들 수 있는지 없는지 구하시오. - 1 - 참가자의 수 n, 심사위원의 수 m \(2 \leq n < 1,000, 1 \leq m < 2,000)\) - m개의 줄 - 각 심사위원이 행사한 루트의, 정보 a, b \((1 \leq \left| a \right| , \left| b \right| \leq n, \left| a \right| \neq \left| b \right|)\) 정보가 x0인 경우 찬성표를 던질 것이다. 참가자의 번호는 1~n번이다. 상근이는 1번 참가자이다. 다음 라운드 진출 목록을 심사위원의 의심 없..

1. 문제 도현이는 경기장을 여러 구역으로 나누고, 어떤 선수가 A->B 움직임을 (A, B)로 표현한다. 다른 모든 구역에 도달할 수 있는 시작구역을 모두 찾자. - 1 - 테스트 케이스의 개수 \(T(1 \leq T \leq 11)\) - 1 - 구역의 수 N, 지시한 움직임의 수 M \(1 \leq N, M \leq 100,000)\) - M개의 줄 - 움직임 (A, B) \(0 \leq A, B < N)\) 가능한 모든 시작 구역을 오름차순으로 출력, 만일 그러한 시작 구역이 없으면 Confused 출력 2. 재정의 시작하면 모두 연결되는 정점 모두 출력 3. 해결 방법 SCC 알고리즘으로 구역 나누기 연결되는 그룹들을 모두 제거했을 때 남은 그룹의 개수가 1개면 그 그룹의 모든 원소. 0개면 모..

1. 문제 한 도미노 블록이 넘어지면 다음 도미노가 연쇄적으로 쓰러진다. 그러나 특정 다른 블록을 넘어뜨리지 못하게 배치되어 있다면 수동으로 넘어뜨려야 한다. 각 도미노 블록 배치가 주어질 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최솟값을 구하라. - 1 - 테스트케이스의 개수 T - 1 - 정수 \(N, M(1 \leq N \leq 100,000)\) N: 도미노 개수, M: 관계의 개수 도미노 블록 번호는 1~N사이 정수다. - M개의 줄 - 두 정수 x, y(x번 블록이 넘어지면 y번 블록도 넘어짐) 손으로 넘어뜨리는 최소의 도미노 블록 개수 출력 2. 재정의 모든 노드를 다 지나기 위해 시작해야 되는 최소 노드 수 3. 해결 방법 SCC로 그룹 짓기 if(scc[i] ..

1. 문제 n개의 팀은 1~n번까지 번호가 매겨져 있고 작년과 참가한 팀이 같다. 작년 순위와 상대적인 순위가 바뀐 모든 팀이 주어졌을 때, 올해 순위를 만드시오. 하지만 올해 순위가 결정되지 않을 수도 있고, 잘못된 정보일 수도 있어 이도 알아내야 한다. - 1 - 테스트 케이스의 개수 \(T(1 \leq T \leq 100)\) - 1 - 팀의 수 \(n(2 \leq n \leq 500)\) - 2 - \(t_{i}(1 \leq t_{i} \leq n)\). \(t_{i}\)는 작년에 i 등 한 팀의 번호 - 3 - 상대적인 등수가 바뀐 쌍의 수 \(m(0 \leq m \leq 25,000)\) - m개의 줄 - 상대적인 등수가 바뀐 두 팀. 중복은 X 1등팀부터 순위 출력. 순위가 결정되지 않을 경..

1. 문제 난이도 순서로 된 1~N번까지 총 N개의 문제로 되어 있는 문제를 풀려고 한다. 민오는 세 가지 조건에 따라 문제를 풀 순서를 정한다. N개의 문제를 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 푼다. 문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건에 맞는 민오가 풀 문제의 순서를 결정하시오. - 1 - 문제의 수 \(N(1 \leq N \leq 32,000)\), 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 \(M(1 \leq M \leq 100,000)\) - M개의 줄 - 두 정수의 순서쌍 A, B. A번 문제가 B번 문제보다 먼저 푸는 것이 좋다. 항상 문..

1. 문제 도현이는 n개의 별들을 이어서 별자리를 만들 것이다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태 모든 별들은 별자리 위의 선을 통해 직/간접적으로 이어져야 한다. 별들은 2차원 평면 위에 있고 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 들 때, 별자리를 만드는 최소 비용을 구하시오. - 1 - 별의 개수 \(n(1 \leq n \leq 100)\) - n개의 줄 - 각 별의 x, y좌표(실수) 최대 소수점 둘째 자리까지 \((0 \leq x, y \leq 1,000)\) 정답 출력(절대 상태 오차는 \(10^{-2}\)까지 허용 2. 재정의 좌표간 거리가 비용인 그래프의 최소 스패닝 트리 구하기 3. 해결 방법 \(n^2 = 10,000\)이므로 간선의 가중치가..