cho.sh

문제

문제를 고르고 내장 에디터에서 풀이를 작성해 보시기 바랍니다. 채점기가 실제 테스트 케이스로 코드를 바로 검증하고, 아카이브의 문제들도 자유롭게 둘러볼 수 있습니다.

전체 결과문제 366개
제목난이도유형정답자시간 제한메모리 제한채점
New Megacity가중 그래프의 각 간선을 모든 최소 신장 트리에 포함되는지, 일부에만 포함되는지, 어디에도 포함되지 않는지 분류한다.어려움8최소 신장 트리유니온 파인드+2아직 제출이 없습니다2.5초2048 MB지문만 제공
Omnes Viae Yokohamam Ducunt?각 간선의 취약도와 도시 1에서 분리되는 도시들의 중요도 합을 곱한 값의 총합을 최소로 하는 신장 트리를 고른다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다3초2048 MB지문만 제공
Highways of the Future일부 구역의 원자로가 꺼져도 남은 원자로가 모든 구역에 전력을 공급하도록 추가할 최소 방향 간선 수를 구한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다6초2048 MB지문만 제공
Interplanetary Traditions행성 i에 i명이 살고 i에서 j로 사절단이 갈 때 선물 총 무게가 i*j*square가 되도록 할 때, 행성 1의 정보가 모든 행성에 전달되도록 하는 최소 희생 무게 합을 구한다.어려움8정수론수학+2아직 제출이 없습니다10초2048 MB지문만 제공
전선 연결하기가중치 트리가 주어질 때 도로와 겹치지 않는 전선 N-1개로 모든 마을을 연결할 수 있는지 판별하고, 가능하면 전선 길이 합의 최솟값을 구한다.어려움8트리최소 신장 트리+2아직 제출이 없습니다1.5초1024 MB지문만 제공
도로 공사기존 경로를 따라 도로를 건설하고, 철거한 도로의 길이만큼 자원을 충당해 지름길을 놓을 때, 1번 마을에서 N번 마을까지 이동 거리의 최솟값을 구한다.어려움8최소 신장 트리기하+2아직 제출이 없습니다0.5초1024 MB지문만 제공
Dangerous City모든 정점 U에 대해, U에서 다른 모든 정점으로 가는 경로마다 경로 위 위험 등급의 최댓값을 구하고 그 최솟값들을 모두 더해 N개의 합을 출력한다.어려움8그래프최소 신장 트리+2아직 제출이 없습니다1초2048 MB지문만 제공
소행성 레인저움직이는 n개 점에 대해 미래 모든 시각에서 최소 신장 트리가 바뀌는 횟수에 최초 구축을 더해 센다.어려움9최소 신장 트리기하+2아직 제출이 없습니다1초128 MB채점 가능
오래된 공장의 급수 배관물 높이를 정해 물이 차는 구역을 고르고, 열린 구멍은 뚜껑이나 새 파이프로 막아 최소 비용으로 시작점에서 도착점까지 물을 보낸다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다5초128 MB채점 가능
농장 단순화하기각 간선 길이가 최대 세 번만 나타나는 가중 그래프에서 최소 신장 트리의 총 길이와 서로 다른 최소 신장 트리의 개수를 10^9+7로 나눈 나머지를 구한다.어려움9최소 신장 트리유니온 파인드+2아직 제출이 없습니다1초128 MB채점 가능
선심성 고속도로망각 질의 구간 [l, h]에 포함된 도로만으로 연결 가능한 도시 쌍을 최대로 연결하는 가장 저렴한 네트워크 비용을 구합니다.어려움9최소 신장 트리분할 정복+2아직 제출이 없습니다30초256 MB채점 가능
고속도로와 자치주짧은 도로로 연결된 도시 그룹 중 인구수 합이 K의 배수가 되는 부분집합을 포함한 그룹이 생기는 가장 작은 도로 길이 제한을 구합니다.어려움9최소 신장 트리동적 계획법+2아직 제출이 없습니다2초64 MB채점 가능
어둠 막기전구 세기 격자와 천장 높이가 주어질 때 각 칸의 조도를 계산해 어두운 칸을 가린 뒤, 모든 어두운 칸을 포함하면서 내부 칸만으로 이루어진 집합의 최소 울타리 비용을 구한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
부스터걷기는 체력을 소모하고 부스터는 축 방향으로만 이동할 수 있다는 규칙에서, 체력 한계 X로 체크포인트 A에서 B로 갈 수 있는지 각 질의마다 판정한다.어려움9그래프유니온 파인드+2아직 제출이 없습니다8초512 MB채점 가능
Minimum Diameter Spanning Tree가중치가 있는 연결 그래프에서 가장 긴 경로의 길이(지름)가 최소가 되는 신장 트리를 찾아, 그 지름과 트리의 간선들을 출력한다.어려움9그래프최단 경로+2아직 제출이 없습니다5초1024 MB지문만 제공
Flipping Colors각 변에 빨강 또는 검정 색과 페널티가 있는 완전 그래프에서, 일부 정점을 골라 연결된 모든 변의 색을 뒤집어 페널티 합이 최소인 빨강 신장 트리를 만들고, 불가능하면 -1을 출력한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다3초512 MB지문만 제공
건설 사업N개 마을 중 H개 이하에 공항을 세우고, M개의 직사각형 장애물을 피하는 축에 평행한 도로로 모든 마을을 연결할 때, 공항 비용과 도로 길이의 합을 최소화한다.어려움9최소 신장 트리기하+2아직 제출이 없습니다5초256 MB채점 가능
Six Words정점 i의 퍼텐셜이 i이고 간선 i의 가중치가 i인 연결 그래프가 주어질 때, 선그래프의 선그래프에서 최소 신장 트리의 총 가중치를 구한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
Road Manager원형 격자에서 연속한 열 구간을 지운 뒤 남는 그래프의 최소 신장 트리 가중치를 각 질의마다 구한다. 간선 가중치는 주어진 난수 생성기로 만든다.어려움9최소 신장 트리그래프+2아직 제출이 없습니다4초512 MB지문만 제공
Minimum Spanning Trees각 정점 쌍이 독립적으로 간선이 없거나 1부터 k까지의 가중치를 확률적으로 가질 때, 그래프가 연결되어 있고 최소 신장 트리의 가중치가 주어진 s가 될 확률을 모든 s에 대해 구한다.어려움9조합론그래프+2아직 제출이 없습니다4초512 MB지문만 제공
Minimal Variance Tree연결된 다중 그래프에서 간선 가중치들의 평균으로부터의 제곱 편차 합으로 정의되는 분산이 최소가 되는 신장 트리를 찾는다.어려움9최소 신장 트리그리디+2아직 제출이 없습니다1초256 MB지문만 제공
최소 스패닝 트리와 쿼리가중치 방향 그래프 G와 i개 정점의 방향 경로 그래프의 텐서 곱에 대해, i가 2부터 Q+1까지 각각의 최소 스패닝 트리 간선 가중치 합을 구한다.어려움9최소 신장 트리그래프+2아직 제출이 없습니다5초256 MB지문만 제공
전화 통화집들이 이루는 트리 위에 m개의 전화선이 있고, 각 선은 두 경로의 합집합에 속한 서로 다른 두 집이 비용 w로 통화하게 한다. 집 1에서 연락할 수 있는 최대 집 수와 그때의 최소 비용을 구한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB채점 가능
Flow가중 이분 그래프를 k개 이어 붙인 층상 네트워크에서 최대 유량이 수렴하는지 판정하고, 수렴하면 그 극한값을, 아니면 -1을 출력한다.어려움9그래프최단 경로+1아직 제출이 없습니다2초256 MB지문만 제공
Computing MDSST정점이 n개(2 이상 15 이하)인 완전 가중 그래프에서 모든 정점 쌍 거리의 합이 최소가 되는 신장 트리를 골라 그 값을 출력한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB지문만 제공
Kitamasa's Counterattack두 플레이어가 열쇠 가격을 조정하고 모든 상자를 여는 최소 비용 열쇠 집합을 고르는 게임에서 최적 값을 구하고, 무한히 커질 수 있으면 -1을 출력한다.어려움9게임 이론최소 신장 트리+2아직 제출이 없습니다2초256 MB지문만 제공
Minimal Cut가중 무방향 그래프에 무게 10^9인 n개의 순환 간선을 추가한 뒤, 모든 정점 쌍의 최소 s-t 컷 값을 합해 998244353으로 나눈 나머지를 구한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다3초1024 MB지문만 제공
Minimum Spanning Tree간선 가중치 1부터 m의 순열 중에서 처음 n-1개 간선이 주어진 다중 그래프의 최소 신장 트리를 이루는 경우의 수를 센다.어려움9최소 신장 트리조합론+2아직 제출이 없습니다1초256 MB지문만 제공
두 최단 경로음이 아닌 가중치를 가진 방향 그래프에서 각 정점 i마다 1번 정점에서 i로 가는 간선이 겹치지 않는 두 경로의 최소 비용 합을 구한다.어려움9그래프최단 경로+2아직 제출이 없습니다5초1024 MB지문만 제공
King SlimeW x H 격자 위의 슬라임이 벽이나 다른 슬라임에 닿을 때까지 동서남북으로 미끄러지며, 모든 슬라임이 하나로 합쳐지는 최소 이동 횟수를 구한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다8초512 MB지문만 제공
The King's Guards각 경비병을 허용된 마을 중 하나에 배치하고, 모든 마을이 정확히 한 경비병의 연결 요소에 속하도록 하는 최소 비용 도로 집합을 고른다.어려움9최소 신장 트리동적 계획법+2아직 제출이 없습니다1초2048 MB지문만 제공
Minimum Spanning Cactus가중치가 있는 선인장 그래프에서 최소 신장 선인장의 비용을 출력하고, 간선 하나의 가중치를 바꾸는 쿼리마다 갱신된 최소 비용을 출력한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다1.2초512 MB지문만 제공
All Pair Maximum Flow볼록 다각형 위에 교차하지 않게 그려진 평면 그래프에서 모든 정점 쌍 사이 최대 유량의 합을 구합니다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다6초256 MB지문만 제공
MST CameraN개 정점에 대한 가중 간선이 R×C 격자에 놓여 있을 때, 부분행렬마다 그 안의 간선들로 만든 최소 신장 트리의 가중치 합을 구하고, 신장 트리가 없으면 -1을 출력한다.어려움9최소 신장 트리유니온 파인드+2아직 제출이 없습니다7초512 MB지문만 제공
Girlfriend가중치가 있는 무방향 그래프에서 각 질의 (u, v)마다 단순 경로 위 간선 중 두 번째로 작은 값의 최솟값을 구한다. 두 간선만 남기고 더 작은 값은 버린다.어려움9그래프유니온 파인드+2아직 제출이 없습니다7초256 MB지문만 제공
Square Graph수열에서 길이 2k인 구간이 앞뒤 절반이 같을 때 대응 위치를 잇는 간선을 만들고, 이 그래프의 최소 신장 포레스트 무게를 구한다.어려움9문자열 매칭유니온 파인드+2아직 제출이 없습니다5초256 MB지문만 제공
Vertex Merge Game가중치가 있는 연결 그래프에서 각 라운드마다 Yunee는 빨강과 파랑 정점 수의 곱만큼, Woongbae는 고른 컷 간선의 가중치만큼 점수를 얻을 때, 최적으로 둔 결과를 판정한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다3초1024 MB지문만 제공
Rooted MST중심 정점 0과 모든 정점을 잇는 간선의 가중치를 하나씩 영구적으로 바꾸면서, 매번 최소 신장 트리의 가중치를 구한다.어려움9최소 신장 트리동적 계획법+2아직 제출이 없습니다3초1024 MB지문만 제공
DCMSF특별한 정점의 차수 제한과 멋진 정점의 차수 1 제한, 같은 종류끼리 연결 금지 조건을 지키며 간선 1개부터 N-1개까지 각각 최소 가중치 spanning forest를 구한다.어려움9최소 신장 트리그리디+1아직 제출이 없습니다2초1024 MB지문만 제공
Strange Graph모듈러 공식으로 정해지는 완전 그래프의 간선 M개를 지운 뒤 최소 신장 포레스트의 가중치 합을 구한다.어려움9유니온 파인드최소 신장 트리+2아직 제출이 없습니다7초1024 MB지문만 제공
MSTM개의 순환 시프트 간선 묶음이 주어질 때 최소 스패닝 트리의 가중치를 구하고, 존재하지 않으면 -1을 출력한다.어려움9최소 신장 트리유니온 파인드+2아직 제출이 없습니다3초1024 MB지문만 제공
Łańcuchy górskie평면 위 N개 도시와 M개 직선(산맥)이 주어질 때, 도시를 잇는 각 도로의 비용을 지나는 직선 수로 정의하고 모든 도시를 연결하는 최소 총비용을 구한다.어려움9기하최소 신장 트리+2아직 제출이 없습니다2초1024 MB지문만 제공
연애 혁명일부 간선이 이미 선택된 가중 무방향 그래프에서, 선택된 간선은 유지하면서 K각 관계(길이 K 이상의 사이클)가 생기지 않도록 버릴 간선의 애정도 합의 최솟값을 구한다.어려움9최소 신장 트리유니온 파인드+2아직 제출이 없습니다1초1024 MB지문만 제공
Security Guard각 섬에 불안도 S_i가 주어진 연결 그래프에서 최대 k개의 간선을 추가하고 일부를 제거해 연결성을 유지하면서 필요한 경비원 수의 최솟값을 구하고, k=0부터 Q까지 각각 출력한다.어려움9최소 신장 트리그리디+2아직 제출이 없습니다3초1024 MB지문만 제공
Bikes vs Cars모든 쌍에 대해 가장 넓은 자동차와 자전거 폭 행렬이 주어질 때, 폭 W의 양방향 도로를 최대 2023개 지어 각 도로를 자전거 차로와 자동차 차로로 나누어 모든 쌍의 최대 통행 폭이 정확히 일치하도록 하는 그래프를 구성한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다5초1024 MB지문만 제공
Pasture 1N개의 말뚝 사이에 교차하지 않는 전선을 놓아 길이 합이 M 이하가 되도록 최대 개수의 삼각형을 만들고, 그때 총 길이를 최소로 한다.어려움9기하그리디+2아직 제출이 없습니다1초1024 MB지문만 제공
Pasture 2N개의 말뚝을 교차하지 않는 선분으로 이어 삼각형 우리 개수를 최대로 만들고, 예산 M 안에서 사용하는 선의 총 길이를 최소로 줄이는 문제다.어려움9기하그리디+2아직 제출이 없습니다1초1024 MB지문만 제공
Convex Polygon MST볼록 다각형의 n-1개 현으로 신장 트리를 만들 때 유클리드 거리의 제곱 합의 최댓값을 구한다.어려움9기하최소 신장 트리+2아직 제출이 없습니다7초1024 MB지문만 제공
Air Reform베를라플로트의 각 간선에 대해, 원래 그래프의 minimax 거리로 가중치가 정해진 여객 그래프에서 두 끝점 사이의 minimax 거리를 구한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다2초1024 MB지문만 제공
Tube Master III각 교차점에 사용되는 관이 0개 또는 2개가 되고 각 칸에 정확히 count[i][j]개의 꺾임점이 인접하도록 관을 선택해 총비용을 최소화한다.어려움9동적 계획법그래프+2아직 제출이 없습니다1초1024 MB지문만 제공
Two PathsDAG와 두 정점 쌍이 주어질 때, 각 쌍을 잇는 간선 비공유 단순 경로 중 총 길이가 최소인 쌍을 찾는다.어려움9그래프최단 경로+2아직 제출이 없습니다5초1024 MB지문만 제공
Random Spanning Tree정점이 8개 이하인 연결 그래프의 각 변 길이가 [0,1]에서 균등분포일 때 최소 신장 트리 무게의 기댓값을 분수로 구한다.어려움9조합론확률+2아직 제출이 없습니다1초1024 MB지문만 제공
최소 스패닝 트리 다시 그리기 놀이고른 최소 스패닝 트리에서 같은 가중치의 간선을 모두 지운 뒤 다시 만들 수 있는 최소 스패닝 트리 개수의 기댓값을 1e9+7로 나눈 나머지로 구한다.어려움9최소 신장 트리조합론+2아직 제출이 없습니다2초1024 MB지문만 제공
2017 지구멸망일부 줄기가 이미 자란 상태에서 가능한 모든 최대 신장 트리에 대해 광도의 합과 광도의 제곱의 합을 구한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB지문만 제공
Avoiding an Arrrgument보석 종류별로 남은 상위 N+1개 값이 주어질 때, 뱀 순서 선택에서 두 번째 선택까지 보장받는 합이 최대가 되는 첫 보석을 고른다.어려움9게임 이론그리디+2아직 제출이 없습니다1초1024 MB지문만 제공
Two trees, twelve forests간선이 두 개의 신장 트리로 나뉘고 크루스칼식 배정으로 계산한 숲 점수가 정확히 k인 가중 그래프를 출력한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다1초1024 MB지문만 제공
Blocking the Way타일 조각이 왼쪽 위에서 오른쪽 아래로 이동하지 못하도록 막는 데 필요한 최소 비용을 구한다.어려움9그래프최단 경로+2아직 제출이 없습니다8초1024 MB지문만 제공
Increase the Toll Fees최소 신장 트리가 유일한 연결 가중 그래프가 주어질 때, 원래 MST의 간선을 어떤 MST도 쓰지 않도록 간선 가중치를 최소 총량으로 올리는 문제이다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다2초1024 MB지문만 제공
휴가 계획각 간선의 가중치가 2^i일 때 연결된 그래프에서 두 정점 사이의 최단 경로 중 간선 수가 가장 적은 경로를 여러 질의에 대해 구한다.어려움9그래프유니온 파인드+2아직 제출이 없습니다2초1024 MB지문만 제공
영 타블로가 싫은 재우N개의 영 타블로와 합칠 수 있는 쌍이 주어질 때, 칸 추가/삭제 비용과 무료 거울 합치기를 써서 모든 영 타블로를 직사각형으로 만드는 최소 비용을 구한다.어려움9그리디그래프+2아직 제출이 없습니다2.5초1024 MB지문만 제공
MST의 기댓값가중치가 있는 연결 그래프에 모든 정점 쌍과 0 이상 10^9 이하의 가중치로 이루어진 삼중항 중 하나를 무작위로 골라 간선을 추가할 때, Minimum Spanning Tree 가중치 합의 기댓값을 10^9+7로 나눈 나머지를 구한다.어려움9최소 신장 트리유니온 파인드+2아직 제출이 없습니다1초512 MB지문만 제공
Wind Turbines일부 터빈 구간이 해안과 무료로 연결될 때, 모든 터빈이 해안에 도달하도록 하는 최소 비용 간선 부분집합을 각 질의마다 구한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다4초2048 MB지문만 제공
Island Cities연결된 다리 그래프와 예산이 주어질 때 모든 두 섬 사이 병목 값의 최솟값을 최대화하고, 각 다리의 최적 강화 횟수를 하나 출력한다.어려움9최소 신장 트리이분 탐색+2아직 제출이 없습니다3초1024 MB지문만 제공
Halcyon같은 n개 정점 위의 두 가중치 트리가 주어질 때, 각 k에 대해 첫 번째 트리에서 k개, 두 번째 트리에서 n-1-k개의 간선을 사용하는 최소 가중치 신장 트리의 무게를 구하고 불가능하면 -1을 출력한다.어려움9최소 신장 트리그래프+2아직 제출이 없습니다10초1024 MB지문만 제공
물리를 잘하는 시시포스는 오늘도 우울지그재그로 배열된 평지 높이가 주어질 때, 인접한 평지 사이에 높이 차만큼의 비용이 드는 에스컬레이터를 설치해 모든 평지가 서로 도달 가능하도록 만드는 최소 비용을 구한다.어려움9그래프최소 신장 트리+1아직 제출이 없습니다1초1024 MB지문만 제공
패널 최적화(Hard)각 격자의 전압을 조정해 인접한 격자 사이의 보상에서 전압 변경 비용을 뺀 값을 최대로 만든다.어려움10동적 계획법그래프+1아직 제출이 없습니다4초1024 MB지문만 제공