cho.sh

문제

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

전체 결과문제 5747개
제목난이도유형정답자시간 제한메모리 제한채점
침공이 일어난다면, 제발...도로로 이어진 n개 지점의 사람들을 용량이 제한된 최대 10개의 대피소로 보내는데, 모두가 도착하는 최대 시간을 최소로 만듭니다.어려움9이분 탐색BFS+2아직 제출이 없습니다3.5초512 MB채점 가능
배달 지연모든 교차점 쌍의 최단 거리를 구한 뒤 배달 순서 부분집합을 상태로 하는 동적 계획법으로, 주문 시간부터 배달까지의 최대 대기 시간을 최소로 만드는 배달 계획을 찾는다.어려움9최단 경로동적 계획법+2아직 제출이 없습니다5초512 MB채점 가능
소수 트리 - 6트리 꼭짓점에 1부터 n까지의 서로 다른 수를 배정하여 공약수가 1보다 큰 두 끝점을 잇는 나쁜 간 개수를 최소화합니다.어려움9그래프그리디+2아직 제출이 없습니다10초512 MB채점 가능
Prime Tree - 9주어진 트리의 정점에 새 번호를 붙여, 두 끝점이 1보다 큰 공약수를 갖는 간선의 수를 최소로 만든다.어려움9그래프그리디+2아직 제출이 없습니다10초512 MB채점 가능
Superstition가중 무방향 그래프에서 총 이동 시간이 K 이하이면서 D로 나누어떨어지는 경로의 수를 1,000,000,007로 나눈 나머지를 구한다.어려움9그래프행렬+2아직 제출이 없습니다2초512 MB지문만 제공
홀수 색칠색칠 결과가 각 행과 열의 검은 공 개수를 홀수로 만들도록 칠하는 방법 수를 세어서 998244353로 나눈 값을 구합니다.어려움9수학조합론+2아직 제출이 없습니다1초256 MB채점 가능
스키 경로 감시n개 정점의 DAG에서 각 정점의 나가는 경로는 최대 1개이고 도착 정점은 서로 다를 때 m개 등록 경로가 모두 지나는 정점의 최솟값을 구한다.어려움9그래프그리디+2아직 제출이 없습니다2초512 MB채점 가능
Minegraphed정점이 9개 이하인 방향 그래프가 주어질 때, 표시된 칸 사이의 도달 가능성이 그래프와 정확히 일치하는 3차원 블록 세계를 설계하는 문제다.어려움9그래프시뮬레이션+2아직 제출이 없습니다2초512 MB지문만 제공
카와이강의 다리간선이 추가되고 삭제되는 그래프에서 두 섬 사이 경로의 최대 위험도가 최소가 되는 값을 구하는 질의에 답한다. 위험도는 한 자리 수다.어려움9동적 계획법유니온 파인드+2아직 제출이 없습니다5초512 MB채점 가능
Incredible Hull볼록 위치에 놓인 점들을 이익이 큰 순서대로 주고, 재귀적 분할 규칙을 따라 통로 그래프를 만든 뒤 그 그래프의 최대 클리크를 찾는다.어려움9기하분할 정복+2아직 제출이 없습니다1초512 MB지문만 제공
의약품 수송 2최소 회전 반지름 R을 가진 차량이 후진 없이 두 방향이 정해진 리프트 사이를 이동할 때 최단 경로 길이를 구한다.어려움9기하최단 경로+2아직 제출이 없습니다0.5초256 MB지문만 제공
영과일 학회방'X' 기둥을 피하며 격자의 '.' 칸을 1x1과 1x2 타일로 덮을 때 필요한 타일 개수의 최솟값을 구합니다.어려움9그래프DFS+2아직 제출이 없습니다1초256 MB채점 가능
Praktični가중 무방향 그래프가 주어질 때, 각 연산이 값 x와 간선 부분집합을 골라 XOR하는 상황에서 모든 단순 사이클의 XOR이 0이 되도록 하는 최소 연산 수와 그 연산들을 출력한다.어려움9그래프DFS+2아직 제출이 없습니다1초512 MB지문만 제공
Amusement ParkJOI-kun이 각 명소의 게시판에 0 또는 1을 적어 X를 전달하고, IOI-chan은 시작 위치 P에서 이동하며 읽은 값으로 X를 알아내는 두 프로그램을 설계한다.어려움9그래프DFS+1아직 제출이 없습니다2초512 MB지문만 제공
블랙 기업모든 간과 한 정점을 공유하는 두 간에서 두 끝점의 크기 관계가 기여도 순서와 일치하도록 양의 급여를 정하고 그 합을 최소화합니다.어려움9그래프위상 정렬+2아직 제출이 없습니다5초512 MB채점 가능
연결그래프의 모든 간선의 저항이 1Ω일 때, 간선으로 직접 이어진 모든 점 쌍 A, B 사이 합성저항 값의 총합을 구해 소수점 넷째 자리에서 반올림한 값을 출력하는 문제모든 간선의 저항이 1인 연결 그래프에서 각 간선 양 끝점 사이의 등가 저항을 모두 더한 값을 소수점 셋째 자리까지 반올림해 구한다.어려움9그래프행렬+2아직 제출이 없습니다1초512 MB채점 가능
Dijkstra Is Playing At My House서로 겹치지 않는 최대 250,000개의 축 평행 직사각형 장애물이 있는 평면에서 두 점 사이의 맨해튼 최단 경로 길이를 구한다. 장애물의 경계는 지날 수 있다.어려움9최단 경로그래프+2아직 제출이 없습니다3초1024 MB지문만 제공
계곡서로 다른 높이를 가진 N x N 격자가 주어질 때, 모든 셀이 경계의 인접 셀보다 낮은, 구멍 없는 변 인접 영역들의 크기 합을 구한다.어려움9유니온 파인드그래프+2아직 제출이 없습니다2초512 MB채점 가능
문제집 만들기N개 문제 사이의 선후 관계를 간선 삽입과 삭제로 유지하면서, x번부터 y번까지의 문제가 이루는 부분 그래프가 비순환인지 판정한다.어려움9그래프동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
Olympic Logistics함수형 그래프에서 최대 m개의 후속 역을 바꿔 1번 역의 재귀적 가중 신뢰도가 최대가 되도록 만든다.어려움9그래프트리+2아직 제출이 없습니다1초256 MB지문만 제공
죽은 선인장의 사회가중치와 정점별 회복 수치가 주어진 캑터스에서 각 단순 사이클마다 간선을 정확히 하나씩 잘라내고, 잘린 간선이 양 끝에서 Re+Rv 길이의 경로로 재생될 때 만들어지는 트리의 지름의 최솟값을 구한다.어려움9그래프트리+2아직 제출이 없습니다4초1024 MB지문만 제공
일하는 세포주기 T로 반복되는 N개 허브의 가중 유방향 그래프가 주어질 때, 모든 허브 i에서 출발해 정확히 D초 후 허브 j에 도착하는 경로의 수를 1,000,000,007로 나눈 나머지로 각각 구한다.어려움9행렬분할 정복+2아직 제출이 없습니다1초512 MB채점 가능
삼분 그래프평면에 매장된 연결 그래프에서 Q개의 수직 절단선 쌍 x=A, x=B가 주어질 때, 두 직선으로 그래프를 잘랐을 때 생기는 연결 성분의 개수를 각각 구한다.어려움9그래프기하+2아직 제출이 없습니다2초1024 MB지문만 제공
교준이의 심부름꾼, 민제의 고충 ("Circle" Ver.)여러 번의 명령이 주어질 때, 각 중심점에서 원을 최소로 지나는 거리가 제한 이하인 집들의 행복도를 중복 없이 XOR한 값을 구한다.어려움9그래프BFS+2아직 제출이 없습니다4초1024 MB지문만 제공
동적 연결성과 쿼리간선이 있으면 지우고 없으면 추가하는 토글 연산과 두 정점의 연결 여부 질의를 처리한다. x, y와 연결 요소 개수가 xor로 가려져 있어, 질의를 거꾸로 처리하며 동적 연결 구조를 유지해야 한다.어려움9유니온 파인드그래프+2아직 제출이 없습니다3초1024 MB지문만 제공
Minimum Diameter Spanning Tree가중치가 있는 연결 그래프에서 가장 긴 경로의 길이(지름)가 최소가 되는 신장 트리를 찾아, 그 지름과 트리의 간선들을 출력한다.어려움9그래프최단 경로+2아직 제출이 없습니다5초1024 MB지문만 제공
Flipping Colors각 변에 빨강 또는 검정 색과 페널티가 있는 완전 그래프에서, 일부 정점을 골라 연결된 모든 변의 색을 뒤집어 페널티 합이 최소인 빨강 신장 트리를 만들고, 불가능하면 -1을 출력한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다3초512 MB지문만 제공
Gifted Bafuko트리에서 거리가 1 또는 2인 정점을 연결한 그래프가 주어질 때, 차수가 3 이하인 원래 트리를 복원한다.어려움9그래프트리+2아직 제출이 없습니다10초512 MB지문만 제공
Amusement Park정점이 18개 이하인 무방향 그래프에서 각 간선을 한 방향으로 정하는 배향 중 비순환인 것(위상 순서가 존재하는 것)들에 대해, 원래 방향에서 뒤집힌 간선 수의 합을 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다3초512 MB지문만 제공
Virus Experiment주기적으로 바뀌는 바람 방향과 각 칸의 저항값이 주어질 때, 처음 감염시킬 한 칸을 골라 최종 감염자 수를 최소로 만들고 그런 칸의 개수를 센다.어려움9그래프시뮬레이션+2아직 제출이 없습니다2초512 MB지문만 제공
회의임의의 세 정점에 대해 만남 지점(트리 중앙값)을 알려주는 오라클만 주어질 때, 최대 차수가 18인 N개 정점의 트리를 복원한다.어려움9트리분할 정복+2아직 제출이 없습니다2초256 MB채점 가능
두 안테나각 질의 구간에 속한 안테나 쌍 중 서로 통신할 수 있는 쌍이 있는지 판별하고, 있다면 통신 비용 |Hx-Hy|의 최댓값을 구한다.어려움9세그먼트 트리그래프+2아직 제출이 없습니다3초512 MB지문만 제공
두 가지 교통수단두 프로그램이 각자 한 종류의 가중 간선 정보를 들고 58000비트 이하로 통신해, 두 그래프를 합친 그래프에서 도시 0으로부터의 최단 거리를 구한다.어려움9최단 경로그래프+2아직 제출이 없습니다10초256 MB채점 가능
시간을 달리는 비타로경로 그래프의 각 간선 i는 시간 구간 [L_i, R_i)에서만 지날 수 있고 1쵸 되감기에 비용 1이 들 때, 간선 구간 갱신과 (A,B)에서 (C,D)로 가는 최소 되감기 횟수를 묻는 질의에 답한다.어려움9세그먼트 트리그래프+2아직 제출이 없습니다3초512 MB지문만 제공
Road Service 1도시 N개로 이루어진 트리가 주어질 때, 모든 도시 쌍 거리의 합을 최소로 만들도록 새 도로 K개를 선택한다.어려움9그래프그리디+2아직 제출이 없습니다1초512 MB지문만 제공
Wild Boar가중 무방향 그래프에서 정해진 순서의 음식 지점을 잇달아 방문하되 방금 지나온 도로를 곧바로 되짚을 수 없고, 매일 목록의 한 원소가 바뀔 때마다 최소 총 시간 또는 -1을 구한다.어려움9그래프최단 경로+2아직 제출이 없습니다10초1024 MB지문만 제공
도로 정비N개 도시와 Q개의 계획 중 일부만 시행된 상황에서, 시행되지 않은 각 계획이 그 시점의 그래프에서 최단 경로 위의 미포장 도로를 몇 개 포장하게 되는지, 새 도로를 건설하면 -1을 구한다.어려움9그래프유니온 파인드+2아직 제출이 없습니다2초256 MB채점 가능
Spaceships각 별이 단방향 우주선을 하나 관리하며 시간에 따라 활성화와 비활성화가 일어난다. 상태 변경 후 두 사람이 주어진 별에서 만날 수 있는지, 만날 수 있다면 우주선 탑승 횟수 합이 최소가 되는 별을 답한다.어려움9연결 리스트트리+2아직 제출이 없습니다10초256 MB지문만 제공
Color Codesn과 허용된 해밍 거리 집합 P가 주어질 때, 이웃한 문자열의 거리가 P에 속하도록 모든 2^n개의 n비트 문자열을 나열하거나 그러한 나열이 없음을 판정한다.어려움9그래프수학+2아직 제출이 없습니다2초512 MB지문만 제공
그래프와 사이클홀수 개의 정점을 가진 가중 완전 그래프에서 모든 간선을 서로 겹치지 않는 사이클로 분할하고, 각 사이클에서 연속한 두 간선의 최댓값 합의 총합을 최소화한다.어려움9그래프그리디+2아직 제출이 없습니다2초256 MB채점 가능
Stranded Robot우주선 블록과 진공으로 이루어진 3차원 격자에서 중력을 임의로 바꿀 수 있는 로봇이 출발 칸과 도착 칸 모두 태양빛을 받아야 한다는 조건 아래 텔레포터까지 최소 이동 횟수를 구한다.어려움9BFS그래프+2아직 제출이 없습니다4초256 MB지문만 제공
Dungeon Dawdler인접한 벽과 최대 두 개의 순간이동 덫문만을 단서로 삼아 알려지지 않은 격자 던전을 탐험하고 전체 지도를 복원한다.어려움9그래프구현+2아직 제출이 없습니다8초512 MB지문만 제공
Cross-Stitch8방향으로 연결된 십자수 무늬가 주어질 때, 뒷면 실 경로를 설계해 전체 실 길이가 최소가 되도록 바늘의 진입점과 이탈점 좌표를 출력한다.어려움9그래프그리디+2아직 제출이 없습니다2초512 MB지문만 제공
Disposable Switches모든 변의 비용이 l/v + c(v > 0, c >= 0)로 주어지는 연결 가중 그래프에서, v와 c의 값에 관계없이 1번에서 n번으로 가는 최단 경로에 결코 속할 수 없는 정점을 모두 찾는다.어려움9최단 경로그래프+2아직 제출이 없습니다4초512 MB지문만 제공
비행기 타고 가요각 표 i는 출발 도시가 [Bi,Ci]에, 도착 도시가 [Di,Ei]에 속할 때만 가격 Ai로 쓸 수 있다. K번 도시에서 모든 도시로 가는 최소 표 값 합을 구한다.어려움9그래프최단 경로+2아직 제출이 없습니다2초1024 MB지문만 제공
Falling Portals세계 i는 속도 i로 아래로 떨어지고, 높이가 같아지면 소가 다른 세계로 이동한다. i에서 Q_i로 가는 최단 시간을 기약분수로 구하거나 불가능하면 -1을 출력한다.어려움9기하그래프+2아직 제출이 없습니다2초512 MB지문만 제공
Lets Burn and Rob ManhootanBob이 격자 도로를 따라 왼쪽 위에서 오른쪽 아래로 갔다가 되돌아오는 닫힌 경로를 지날 때, 불탄 도로에 둘러싸인 블록 가치의 합에서 통행 비용을 뺀 최댓값을 구한다.어려움9동적 계획법그래프+2아직 제출이 없습니다2초512 MB지문만 제공
Trips간선 가중치가 1에서 3인 방향 그래프에서 같은 마을이나 도로를 여러 번 지나도 되는 경로를 길이 순으로 나열할 때, k번째로 짧은 경로의 길이를 구하고 그러한 경로가 k개 미만이면 -1을 출력한다.어려움9그래프동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
착한 말 나쁜 말N×N 격자의 각 세균이 직교 이웃으로 한 칸 이동하는 데 a, 좋은 칸에서 체비쇼프 거리 D 이내로 뛰는 데 b의 에너지가 들 때, 각 회의 칸마다 모든 세균이 모이는 최소 총에너지를 구한다.어려움9최단 경로그래프+2아직 제출이 없습니다2.5초1024 MB채점 가능
순찰 경로정점이 15개 이하인 연결 가중 무향 다중 그래프에서 모든 간선을 적어도 한 번 지나는 최소 길이의 닫힌 보행을 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
텐키 (Tenkey)0 키에서 시작해 커서 이동과 키 입력만으로 M으로 나눈 나머지가 R인 양의 정수를 입력할 때 필요한 최소 조작 횟수를 구한다.어려움9그래프BFS+2아직 제출이 없습니다2초512 MB채점 가능
그래프 세기정점 2n개를 가진 무향 그래프 중 완전 매칭이 없지만 어떤 없는 변을 하나 추가하면 완전 매칭이 생기는 그래프의 동형류 개수를 998244353으로 나눈 나머지로 구한다.어려움9조합론그래프+2아직 제출이 없습니다5초512 MB채점 가능
Interesting Graph그래프의 임의의 7개 정점 중 두 정점이 바깥의 단절점을 지나야만 연결되도록 보장될 때, 1부터 n가지 색 각각으로 하는 적절한 색칠의 수를 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Counting Cactus주어진 작은 그래프(n은 13 이하)에서 부분 그래프의 변 집합 가운데 연결되어 있고 모든 변이 많아야 하나의 단순 사이클에 속하는 것의 개수를 998244353으로 나눈 나머지를 구한다.어려움9동적 계획법그래프+2아직 제출이 없습니다2초512 MB지문만 제공
Six Words정점 i의 퍼텐셜이 i이고 간선 i의 가중치가 i인 연결 그래프가 주어질 때, 선그래프의 선그래프에서 최소 신장 트리의 총 가중치를 구한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다2초512 MB채점 가능
Um_nik의 알고리즘정점 2e6, 간선 2e6 규모의 이분 그래프가 주어질 때, 최대 매칭 크기의 0.95배 이상인 매칭을 찾아 출력하는 문제로, 상수 최적화가 필수적이다.어려움9그래프그리디+2아직 제출이 없습니다4초512 MB채점 가능
Interactive Algorithm길이 400 이하의 숨겨진 순열을 최대 25000번의 질의로 알아낸다. 각 질의는 제시한 순열과 숨겨진 순열이 공유하는 인접 무순서 쌍의 개수를 돌려준다.어려움9완전 탐색그래프+2아직 제출이 없습니다5초512 MB지문만 제공
괄호 오일러 투어무방향 그래프에서 각 정점에 괄호가 붙어 있을 때, 방문 순서대로 읽은 괄호열이 올바른 괄호열이 되는 오일러 투어를 찾아 출력하거나 불가능함을 판정한다.어려움9그래프DFS+2아직 제출이 없습니다2초512 MB채점 가능
Find a Tree색수 k인 그래프와 정점 k개짜리 트리가 주어질 때, 트리를 부분그래프로 포함하는 서로 다른 그래프 정점 k개를 찾거나 불가능함을 판별한다.어려움9그래프그리디+2아직 제출이 없습니다4초512 MB지문만 제공
Tomb Raider회전 가능한 두 면 gargoyle이 있는 n×m 거울 미로에서, 모든 gargoyle 면이 빛으로 다른 gargoyle 면과 연결되도록 회전 횟수의 최솟값을 구한다.어려움9그래프DFS+2아직 제출이 없습니다3초512 MB지문만 제공
QuoridorASCII 아트로 주어진 육각형 Quoridor 보드에서 플레이어 A가 놓을 수 있는 모든 벽 위치를 세되, 어떤 플레이어든 반대편에 도달하지 못하게 막는 배치는 제외한다.어려움9기하그래프+2아직 제출이 없습니다2초512 MB지문만 제공
Salty Fish도둑이 각 카메라의 감시 범위에서 사과를 훔칠 때, 잠글 카메라를 골라 비용을 지불하고 남는 이익이 최대가 되도록 하는 문제입니다.어려움9트리그리디+2아직 제출이 없습니다3초512 MB지문만 제공
Road Manager원형 격자에서 연속한 열 구간을 지운 뒤 남는 그래프의 최소 신장 트리 가중치를 각 질의마다 구한다. 간선 가중치는 주어진 난수 생성기로 만든다.어려움9최소 신장 트리그래프+2아직 제출이 없습니다4초512 MB지문만 제공
Minimum Spanning Trees각 정점 쌍이 독립적으로 간선이 없거나 1부터 k까지의 가중치를 확률적으로 가질 때, 그래프가 연결되어 있고 최소 신장 트리의 가중치가 주어진 s가 될 확률을 모든 s에 대해 구한다.어려움9조합론그래프+2아직 제출이 없습니다4초512 MB지문만 제공
Line Graphs단순 무방향 그래프 G와 1 이상 4 이하의 k가 주어질 때, k번 반복한 선 그래프 L^k(G)의 최대 클리크 크기와 최대 클리크의 개수를 10억 7로 나눈 나머지를 구한다.어려움9그래프조합론+2아직 제출이 없습니다5초512 MB지문만 제공
Bulbasaur층마다 k개의 구멍이 있는 방향 그래프에서 모든 층 쌍에 대해 서로 정점과 간선을 겹치지 않게 보낼 수 있는 최대 덩굴 수의 합을 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다6초512 MB지문만 제공
그래프 세기N개 노드의 연결된 무방향 라벨 그래프 중 다리가 정확히 K개인 것의 개수를 합성수일 수 있는 M으로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
The Halfwitters각 시작 순열에서 인접 교환(비용 a), 전체 뒤집기(비용 b), 무작위 재배치(비용 c)를 써서 항등 순열에 도달하는 최소 기대 시간을 계산한다.어려움9동적 계획법그래프+2아직 제출이 없습니다5초512 MB채점 가능
Knowledge-Oriented Problem그래프를 k번 복사하고 연속한 복사본의 같은 정점끼리 연결한 그래프에서 신장 트리의 개수를 10^9+7로 나눈 나머지를 구한다.어려움9그래프행렬+2아직 제출이 없습니다5초512 MB지문만 제공
814 - 28 곱하기 14 격자에 숫자를 채워, 1부터 X까지의 모든 수를 인접한 칸을 따라 읽을 수 있게 할 때 X를 최대화하는 문제입니다.어려움9그래프DFS+2아직 제출이 없습니다0.814초814 MB채점 가능
Making Friends on Joitter is FunM번의 팔로우 이벤트가 일어난 직후마다 확장 과정을 적용해 더 이상 추가할 수 없을 때의 팔로우 관계 총합을 각각 구한다.어려움9유니온 파인드그래프+1아직 제출이 없습니다2초512 MB지문만 제공
집 떠나와 열차 타고가중 선인장 그래프에서 1번 정점에서 V번 정점으로 가는 경로가 없어지도록 지우는 간선 길이 합의 최솟값을 구하고, 불가능하면 권욱제 재입대를 출력한다.어려움9그래프DFS+2아직 제출이 없습니다3초1024 MB지문만 제공
가슴 속에 무엇인가시간에 따라 강도 d를 가진 간선이 추가되고, 심박수가 x로 치솟는 순간 강도가 x 이상인 간선만 살아남을 때 두 세포가 연결되는지와 그 최대 x를 묻는 문제.어려움9유니온 파인드그래프+2아직 제출이 없습니다3초1024 MB지문만 제공
풀 한 포기 친구 얼굴10개의 고정 명령 문자열이 주어질 때, 격자를 벗어나지 않고 (1,1)에서 (N,M)까지 도달하는 명령 번호 수열의 가짓수를 구하거나 무한히 많으면 -1을 출력한다.어려움9그래프동적 계획법+2아직 제출이 없습니다3초1024 MB지문만 제공
시리얼소들이 좋아하는 시리얼과 두 번째로 좋아하는 시리얼이 주어질 때, 앞에서 i마리를 제거했을 때 시리얼을 받는 소의 수를 모든 i에 대해 구한다.어려움9그리디시뮬레이션+2아직 제출이 없습니다1초512 MB채점 가능
New Year and Social Network같은 n개 정점 위의 두 신장 트리 T1, T2가 주어질 때, T1의 간선들을 서로 다른 T2의 간선으로 교체해도 트리가 유지되도록 하는 최대 매칭을 찾아 그 쌍들을 출력한다.어려움9그래프유니온 파인드+2아직 제출이 없습니다4초512 MB지문만 제공
최소 스패닝 트리와 쿼리가중치 방향 그래프 G와 i개 정점의 방향 경로 그래프의 텐서 곱에 대해, i가 2부터 Q+1까지 각각의 최소 스패닝 트리 간선 가중치 합을 구한다.어려움9최소 신장 트리그래프+2아직 제출이 없습니다5초256 MB지문만 제공
전화 통화집들이 이루는 트리 위에 m개의 전화선이 있고, 각 선은 두 경로의 합집합에 속한 서로 다른 두 집이 비용 w로 통화하게 한다. 집 1에서 연락할 수 있는 최대 집 수와 그때의 최소 비용을 구한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB채점 가능
Rikka with Bridgesi와 j 사이에 간선이 없고 둘 모두 k와 인접한 경우 (i,j,k)를 브리지라 할 때, 브리지가 K개 이하인 n개 정점의 무방향 그래프 개수를 m으로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Flow가중 이분 그래프를 k개 이어 붙인 층상 네트워크에서 최대 유량이 수렴하는지 판정하고, 수렴하면 그 극한값을, 아니면 -1을 출력한다.어려움9그래프최단 경로+1아직 제출이 없습니다2초256 MB지문만 제공
Hamilton Path방향 그래프에서 모든 두 정점 사이에 연속한 위치를 잇는 간선만 존재하도록 하는 순열의 개수를 세고, 개수가 n 이하이면 그 값들을 사전순으로 출력한다.어려움9그래프조합론+2아직 제출이 없습니다4초512 MB지문만 제공
Link Cut Digraph간선이 없는 정점 n개짜리 방향 그래프에 간선을 하나씩 추가하면서, 매번 서로 도달 가능한 정점 쌍의 개수를 구한다.어려움9그래프유니온 파인드+2아직 제출이 없습니다3초512 MB지문만 제공
K-matchingm이 4 이하인 n×m 격자 그래프에서 정확히 K개의 간선으로 이루어진 매칭의 최소 가중치 합을 구한다. n은 최대 40000이다.어려움9동적 계획법비트 연산+2아직 제출이 없습니다9초512 MB지문만 제공
Vertex covers정점이 n개인 단순 그래프 가운데 최소 정점 덮개의 크기가 정확히 k인 그래프의 개수를 2로 나눈 나머지를 구한다.어려움9조합론수학+2아직 제출이 없습니다3초512 MB지문만 제공
Harary정점 N개짜리 유향 그래프 중 위상 정렬이 정확히 1개, 2개, 3개인 그래프의 개수를 각각 1e9+7로 나눈 나머지로 구한다.어려움9조합론수학+2아직 제출이 없습니다1초512 MB지문만 제공
Isomorphism주어진 n에 대해, 각 정점의 차수 프로필이 모두 다른 두 연결 그래프를 만들되 두 그래프 전체의 차수 프로필은 같게 하고, 불가능하면 NO를 출력한다.어려움9그래프수학+2아직 제출이 없습니다2초512 MB지문만 제공
Jitterbug꼭짓점 1에서 n까지의 무작위 걷기가 평균 b번 이상 움직이도록 n개 꼭짓점 위의 연결된 단순 그래프를 만든다.어려움9그래프수학+1아직 제출이 없습니다2초256 MB지문만 제공
Cactus Revenge주어진 차수열을 만족하는 선인장 그래프가 존재하는지 판정하고, 존재하면 모든 간선을 경로들의 목록으로 출력하는 문제다.어려움9그래프그리디+2아직 제출이 없습니다3초512 MB지문만 제공
DevOps Best Practices서버 1에서 세 기능을 배포할 때 각 기능이 원하는 서버 집합에만 도달하도록, 264개 이하의 간선으로 방향 그래프와 CT 서버 집합을 설계한다.어려움9그래프DFS+2아직 제출이 없습니다3초512 MB지문만 제공
Konstrukcija꼭짓점 1000개와 간선 1000개 이하의 DAG를 만들어, 1번에서 N번으로 가는 모든 정렬 경로의 부호 합이 주어진 K(절댓값 10^18 이하)가 되도록 구성한다.어려움9그래프동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
Beyond the Rescue가중치 있는 트리에서 경비들이 k개 지점을 도는 순환 경로를 자기 속도로 순찰할 때, 다른 이동 속도를 가진 라이틀라가 경비와 같은 도로에 있지 않으면서 s에서 t로 가는 최소 시간을 998244353으로 나눈 나머지로 구한다.어려움9그래프최단 경로+2아직 제출이 없습니다3초256 MB지문만 제공
Simple APSP Problem크기가 H×W이고 검은 칸이 최대 30개인 격자에서 모든 흰 칸 쌍의 흰 칸만 지나는 최단 거리 합을 1e9+7로 나눈 나머지를 구한다.어려움9그래프최단 경로+2아직 제출이 없습니다3초256 MB지문만 제공
Computing MDSST정점이 n개(2 이상 15 이하)인 완전 가중 그래프에서 모든 정점 쌍 거리의 합이 최소가 되는 신장 트리를 골라 그 값을 출력한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB지문만 제공
I've Got Friends가능한 친구 관계 그래프가 주어질 때, 두 사람이 연결되어 있을 때만 좋아하는 음식 종류를 하나 이상 공유하도록 각 사람에게 음식 두 가지를 배정할 수 있는지 판정한다.어려움9그래프조합론+2아직 제출이 없습니다2초512 MB지문만 제공
Swap주어진 교환 절차를 고정된 재귀 DFS 순서로 실행했을 때 P가 주어진 순열이 되는 n개 정점의 무향 그래프 개수를 구한다.어려움9그래프DFS+2아직 제출이 없습니다2초256 MB지문만 제공
Dogs방향 검사 그래프가 주어질 때, 공집합이 아닌 모든 병든 개 부분집합에 대해 각 마을 사람이 추론하는 발사 일자와 발사 마릿수를 모두 더해 소수로 나눈 나머지를 구한다.어려움9그래프조합론+2아직 제출이 없습니다2초256 MB지문만 제공
Compressed Spanning Subtrees차수가 2인 정점이 없는 숨겨진 트리를, 선택한 정점 집합의 압축 생성 부분트리 정점 수를 묻는 질의로 복원한다.어려움9트리그래프+2아직 제출이 없습니다2초256 MB지문만 제공
Multi-stage Marathon각 플레이어가 진출 간선으로 균등하게 이동하는 유향 그래프 위의 확률 보행에서, 시각 1부터 T까지 정점 n에 있는 플레이어 기대 수의 XOR을 구한다.어려움9그래프행렬+2아직 제출이 없습니다3초512 MB지문만 제공
Kitamasa's Counterattack두 플레이어가 열쇠 가격을 조정하고 모든 상자를 여는 최소 비용 열쇠 집합을 고르는 게임에서 최적 값을 구하고, 무한히 커질 수 있으면 -1을 출력한다.어려움9게임 이론최소 신장 트리+2아직 제출이 없습니다2초256 MB지문만 제공
Eulerian Orientation각 그래프에서 빨간 부분 그래프가 오일러 그래프(모든 정점의 빨간 차수가 짝수)가 되는 모든 변 부분집합에 대해 x^2의 합을 1e9+7로 나눈 나머지를 구한다.어려움9수학조합론+2아직 제출이 없습니다2초512 MB지문만 제공