cho.sh

문제

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

전체 결과문제 2096개
제목난이도유형정답자시간 제한메모리 제한채점
Gifted Bafuko트리에서 거리가 1 또는 2인 정점을 연결한 그래프가 주어질 때, 차수가 3 이하인 원래 트리를 복원한다.어려움9그래프트리+2아직 제출이 없습니다10초512 MB지문만 제공
동적 지름가중치가 있는 트리에서 간선 가중치가 갱신될 때마다 지름을 출력한다. 각 질의는 직전 답을 이용해 복호화한다.어려움9트리분할 정복+2아직 제출이 없습니다5초512 MB채점 가능
Magic Tree루트가 있는 트리의 각 정점에 하루만 익는 열매가 하나씩 있다. 매일 간선을 잘라 떨어진 부분 트리에서 익은 열매를 수확할 때 얻을 수 있는 최대 주스 양을 구한다.어려움9트리그리디+2아직 제출이 없습니다2초512 MB지문만 제공
Artillery나무 위에서 매 턴 한 칸씩 움직이는 폰을 반드시 명중시키기 위해 매 턴 쏴야 하는 최소 정점 수를 구한다.어려움9트리그리디+2아직 제출이 없습니다2초512 MB지문만 제공
회의임의의 세 정점에 대해 만남 지점(트리 중앙값)을 알려주는 오라클만 주어질 때, 최대 차수가 18인 N개 정점의 트리를 복원한다.어려움9트리분할 정복+2아직 제출이 없습니다2초256 MB채점 가능
특별관광도시각 간선에 방향별 정비 비용이 주어진 트리에서 정확히 k개의 특별관광도시를 고르면, 각 간선마다 특별도시에서 먼 쪽에서 가까운 쪽으로 향하는 노선이 무료로 정비된다. 남은 노선 정비 비용의 최솟값을 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Road Service 1도시 N개로 이루어진 트리가 주어질 때, 모든 도시 쌍 거리의 합을 최소로 만들도록 새 도로 K개를 선택한다.어려움9그래프그리디+2아직 제출이 없습니다1초512 MB지문만 제공
도시0번 도시에서의 깊이가 18 이하인 트리의 각 도시에 작은 정수 코드를 부여하고, 두 코드만으로 어느 도시가 0에서 다른 도시로 가는 경로에 있는지 판별하는 문제다.어려움9트리비트 연산+2아직 제출이 없습니다2초512 MB채점 가능
도로 정비N개 도시와 Q개의 계획 중 일부만 시행된 상황에서, 시행되지 않은 각 계획이 그 시점의 그래프에서 최단 경로 위의 미포장 도로를 몇 개 포장하게 되는지, 새 도로를 건설하면 -1을 구한다.어려움9그래프유니온 파인드+2아직 제출이 없습니다2초256 MB채점 가능
Communication Jamming직선 위에 놓인 N개 마을 위아래로 두 평면 트리 통신망이 주어질 때, 각 쿼리 높이 A에 대해 A보다 위와 B보다 아래의 허브를 제거해도 모든 마을이 연결되는 최대 B를 구한다.어려움9트리기하+2아직 제출이 없습니다2초256 MB지문만 제공
Spaceships각 별이 단방향 우주선을 하나 관리하며 시간에 따라 활성화와 비활성화가 일어난다. 상태 변경 후 두 사람이 주어진 별에서 만날 수 있는지, 만날 수 있다면 우주선 탑승 횟수 합이 최소가 되는 별을 답한다.어려움9연결 리스트트리+2아직 제출이 없습니다10초256 MB지문만 제공
트리와 쿼리 13루트와 부모가 바뀔 수 있는 트리에서 서브트리와 경로에 대한 대입, 덧셈, 최솟값, 최댓값, 합 쿼리를 처리한다.어려움9트리세그먼트 트리+2아직 제출이 없습니다3초512 MB지문만 제공
정기 모임가중치 트리에서 두 정점 사이 거리를 경로 위 간선 가중치의 최댓값으로 정의할 때, 각 구간 [S,E]에 속한 정점들을 한 점 v로 모으는 최대 거리의 최솟값을 Q개의 질의마다 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)N = 2^k - 1개의 가중치 노드를 힙 순서로 번호 매긴 완전 이진 트리에서, 변이 노드를 지나지 않는 축에 평행한 직사각형 안에 들어가는 노드 가중치 합의 최댓값을 구한다.어려움9분할 정복동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
Klasika가중치 간선을 가진 루트 트리에 노드가 하나씩 추가될 때, 주어진 노드에서 특정 노드의 부분트리 안 임의 노드까지 경로 xor의 최댓값을 매 질의마다 구한다.어려움9트라이트리+2아직 제출이 없습니다5초512 MB지문만 제공
Highway modernization마을 n개를 잇는 트리에서 간선 하나를 지우고 새 간선 하나를 추가해 연결성을 유지하면서 지름을 최소화하는 경우와 최대화하는 경우의 간선 선택을 각각 출력한다.어려움9트리그리디+2아직 제출이 없습니다3초512 MB지문만 제공
트리와 쿼리 14트리와 여러 쿼리가 주어지며, 각 쿼리는 중심 정점과 반지름으로 이루어진 k개 조건을 나열하고, 그중 k-1개 이상을 만족하는 정점의 수를 센다.어려움9트리BFS+2아직 제출이 없습니다5초1024 MB지문만 제공
트리와 K번째 지름쿼리마다 두 정점의 번호를 맞바꾼 뒤, 트리의 모든 지름을 인코딩한 수 가운데 K번째로 작은 값을 구한다.어려움9트리수학+2아직 제출이 없습니다3초1024 MB지문만 제공
XOR과 집합과 트리와 쿼리집합을 XOR과 2배 연산으로 닫은 최소 집합을 정의하고, 트리 경로 위 값들의 닫힘에서 가장 작은 원소를 각 쿼리마다 출력한다.어려움9수학비트 연산+2아직 제출이 없습니다2초1024 MB지문만 제공
Airplane Cliques트리와 거리 한계 x가 주어질 때, 모든 두 정점 사이의 거리가 x 이하인 k개 정점 부분집합의 개수를 각 k마다 998244353으로 나눈 나머지로 구한다.어려움9트리분할 정복+2아직 제출이 없습니다2초512 MB지문만 제공
One Goal정점 n개인 트리에서 모든 k-튜플에 대해 그 튜플의 1-중앙값 중 번호가 가장 작은 정점의 번호 합을 998244353으로 나눈 나머지를 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Interactive Vertex트리에서 숨겨진 특별 정점을 찾아야 한다. 각 질의는 정점 x와 정점 집합을 주면 x가 집합의 모든 정점보다 특별 정점에 가깝거나 같은지 알려준다. 질의 횟수는 4*ceil(log2 n) 이하로 제한된다.어려움9트리분할 정복+2아직 제출이 없습니다2초512 MB지문만 제공
Jiry Matchings가중치가 있는 트리에서 각 k=1부터 n-1까지 정확히 k개의 간선을 고르는 매칭의 최대 총 가중치를 구하고, 불가능하면 "?"를 출력한다.어려움9트리동적 계획법+2아직 제출이 없습니다6초512 MB지문만 제공
Find a Tree색수 k인 그래프와 정점 k개짜리 트리가 주어질 때, 트리를 부분그래프로 포함하는 서로 다른 그래프 정점 k개를 찾거나 불가능함을 판별한다.어려움9그래프그리디+2아직 제출이 없습니다4초512 MB지문만 제공
Rooted Subtrees두 루트 r과 p가 주어질 때, r을 루트로 하는 트리의 서브트리와 p를 루트로 하는 트리의 서브트리의 교집합으로 만들 수 있는 서로 다른 공집합이 아닌 집합의 개수를 구한다.어려움9트리DFS+2아직 제출이 없습니다11초512 MB채점 가능
기댓값 비용n개 정점의 레이블 트리를 균일하게 무작위로 고를 때, 한 정점에서 다른 모든 정점까지 거리 합의 최솟값에 대한 기댓값을 소수 모듈로로 구한다.어려움9조합론트리+2아직 제출이 없습니다3초512 MB채점 가능
Salty Fish도둑이 각 카메라의 감시 범위에서 사과를 훔칠 때, 잠글 카메라를 골라 비용을 지불하고 남는 이익이 최대가 되도록 하는 문제입니다.어려움9트리그리디+2아직 제출이 없습니다3초512 MB지문만 제공
Dense Subgraph차수가 5 이하인 트리에서, L 안에서 밀도가 최대인 연결 부분그래프의 밀도가 x 이하가 되는 부분집합 L의 개수를 세어 1e9+7로 나눈 나머지를 구한다.어려움9동적 계획법트리+2아직 제출이 없습니다3초512 MB지문만 제공
Tree Automorphisms정점 n개짜리 트리가 주어질 때, 합성으로 트리의 모든 자기동형사상을 만들어 내는 n개 미만의 순열 집합을 출력한다.어려움9트리DFS+2아직 제출이 없습니다1초512 MB지문만 제공
Goldberg Machine각 노드가 이웃을 순환하며 구슬을 보내는 트리에서, 일부 노드의 활성 간선을 바꾸는 갱신과 x걸음 뒤 구슬의 위치를 묻는 질의를 처리한다.어려움9트리이분 탐색+1아직 제출이 없습니다5초512 MB지문만 제공
Cyclic Distance가중치가 있는 트리에서 서로 다른 k개의 정점을 골라 한 바퀴 도는 경로의 총 길이가 최대가 되도록 할 때 그 최댓값을 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다3초512 MB지문만 제공
Delegation (Platinum)트리의 간선을 경로들로 분할할 때 가능한 최소 경로 길이의 최댓값을 구한다.어려움9트리DFS+2아직 제출이 없습니다2초512 MB지문만 제공
트리와 쿼리 15가중치가 1인 정점 N개의 트리에서 각 쿼리마다 중심 vi와 반지름 ri로 주어지는 k개의 공 중 하나 이상에 속하는 정점의 수를 구한다.어려움9트리DFS+2아직 제출이 없습니다5초1024 MB지문만 제공
가라오케 모임가중치가 있는 트리에서 일부 정점이 집으로 표시되어 있습니다. 각 정점마다 가장 가까운 집까지의 거리와 가장 먼 집까지의 거리의 비율을 계산하고, 그 최댓값을 기약분수로 출력합니다.어려움9트리DFS+2아직 제출이 없습니다8초512 MB채점 가능
Circus트리 위에 K마리의 소를 서로 다른 정점에 배치할 때, 빈 인접 정점으로 소를 옮겨 서로 도달할 수 있는 배치들을 같은 부류로 묶는다. 각 K마다 배치 부류의 개수를 10^9+7로 나눈 나머지를 구한다.어려움9트리DFS+2아직 제출이 없습니다1초512 MB지문만 제공
New Year and Social Network같은 n개 정점 위의 두 신장 트리 T1, T2가 주어질 때, T1의 간선들을 서로 다른 T2의 간선으로 교체해도 트리가 유지되도록 하는 최대 매칭을 찾아 그 쌍들을 출력한다.어려움9그래프유니온 파인드+2아직 제출이 없습니다4초512 MB지문만 제공
트리와 쿼리 16간선이 하나씩 추가되는 포레스트에서 정점 u와 거리가 k인 정점의 개수를 구하는 쿼리를 처리한다.어려움9트리유니온 파인드+1아직 제출이 없습니다8초512 MB지문만 제공
트리 평균 가중치일부 차수가 자유로운 차수 수열이 주어질 때, 레이블 트리를 균등하게 무작위로 골라 가중치 u*sz(u)+v*sz(v)의 기댓값의 정수 부분을 구한다.어려움9조합론트리+2아직 제출이 없습니다1초256 MB채점 가능
전화 통화집들이 이루는 트리 위에 m개의 전화선이 있고, 각 선은 두 경로의 합집합에 속한 서로 다른 두 집이 비용 w로 통화하게 한다. 집 1에서 연락할 수 있는 최대 집 수와 그때의 최소 비용을 구한다.어려움9그래프최소 신장 트리+2아직 제출이 없습니다1초512 MB채점 가능
Maximum Weighted Matching에지를 복사하고 세분화하는 과정으로 만들어진 그래프에서 최대 가중 매칭의 가중치 합과 그러한 최대 매칭의 개수를 10^9+7로 나눈 나머지를 구한다.어려움9동적 계획법트리+2아직 제출이 없습니다4초256 MB지문만 제공
RMQ 유사 수열수열 A가 주어질 때, 모든 부분 구간에서 A와 같은 RMQ 결과를 내는 [0,1] 구간의 무작위 실수 수열 B의 기댓값 합을 1e9+7로 나눈 나머지를 구한다.어려움9트리조합론+2아직 제출이 없습니다2초256 MB채점 가능
Rikka with Tree Game루트가 있는 트리에서 두 사람이 번갈아 토큰을 자식으로 옮기고 점수는 마지막 깊이가 될 때, 잎에 새 노드를 붙이는 연산을 반복해 최적 점수가 정확히 k가 되게 하는 최소 연산 수 f(k)의 극한 f(k)/k를 구한다.어려움9게임 이론트리+2아직 제출이 없습니다2초512 MB채점 가능
택시가중치가 있는 트리에 M대의 택시와 M명의 손님을 배치하는 모든 경우에 대해, 최대 비용 완전 매칭의 총 거리 합을 10^9+7로 나눈 나머지를 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다1.5초256 MB채점 가능
Rat-O-Matic사각 고리 모양 프레임들이 서로 겹치지 않게 중첩되어 있을 때, 특정 프레임까지 이동하며 지나는 활성 프레임의 최소 경로 문자열을 구하고 이를 부분 문자열로 포함하는 데이터베이스 멜로디의 수를 센다.어려움9트리문자열+2아직 제출이 없습니다3초256 MB지문만 제공
Ants가중치가 있는 트리와, 각자 시각 t_i에 a_i에서 b_i로 가는 유일한 경로를 걷는 개미 m마리가 주어진다. 각 개미마다 한 점에서 한 순간에 만날 수 있는 다른 개미 수의 최댓값을 구한다.어려움9트리누적 합+2아직 제출이 없습니다5초256 MB지문만 제공
주 대가와 리카각 정점에 값이 있는 루트 트리에서, 서브트리나 경로 위에서 정확히 a번 나타나는 값들의 합과 정확히 b번 나타나는 값들의 합의 최대공약수를 구하는 질의에 답한다.어려움9트리DFS+2아직 제출이 없습니다3초512 MB채점 가능
Fulkerson트리가 주어질 때, 각 k에 대해 k개 정점을 골랐을 때 임의의 정점에서 가장 가까운 선택 정점까지의 최대 거리를 최소화한 값을 구해 N개의 값을 모두 출력한다.어려움9트리동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Beyond the Rescue가중치 있는 트리에서 경비들이 k개 지점을 도는 순환 경로를 자기 속도로 순찰할 때, 다른 이동 속도를 가진 라이틀라가 경비와 같은 도로에 있지 않으면서 s에서 t로 가는 최소 시간을 998244353으로 나눈 나머지로 구한다.어려움9그래프최단 경로+2아직 제출이 없습니다3초256 MB지문만 제공
Short Random Problem각 간선 길이가 [0,1]에서 독립적으로 균등하게 정해지는 트리에서 지름의 기댓값을 1e9+7로 나눈 나머지로 구한다.어려움9트리확률+2아직 제출이 없습니다6초512 MB지문만 제공
Connected Subgraph트리에 최대 10개의 간선을 추가한 그래프에서, 간선을 일부 제거한 뒤에도 그래프가 연결되는 경우의 수를 998244353으로 나눈 나머지를 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다1초256 MB지문만 제공
Compressed Spanning Subtrees차수가 2인 정점이 없는 숨겨진 트리를, 선택한 정점 집합의 압축 생성 부분트리 정점 수를 묻는 질의로 복원한다.어려움9트리그래프+2아직 제출이 없습니다2초256 MB지문만 제공
Prefix-free Queries각 질의마다 주어진 부분 문자열들의 부분집합 중 서로 접두사 관계가 없는 것의 개수를 세고, 같은 부분 문자열도 인덱스별로 따로 센 뒤 m으로 나눈 나머지를 구한다.어려움9트라이트리+2아직 제출이 없습니다2초256 MB지문만 제공
Randomized Binary Search Tree무작위 키와 우선순위를 가진 N개의 원소를 트립에 삽입할 때, 최종 높이가 h가 될 확률을 각 h마다 구한다.어려움9확률동적 계획법+2아직 제출이 없습니다2.5초512 MB지문만 제공
Defense Tower트리에서 각 도시의 보호자는 a_i에서 거리를 뺀 값이 최대인 탑이고 동률이면 오래된 탑이며, 갱신 명령마다 보호자 번호 합을 출력한다.어려움9트리분할 정복+2아직 제출이 없습니다6초512 MB지문만 제공
Values on a Tree가중치 없는 트리에서 지름이 정확히 K인 비어 있지 않은 정점 부분집합의 개수를 K=0부터 n-1까지 998244353으로 나눈 나머지로 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
Flight트리에서 u, v, d가 주어지는 강제 온라인 질의마다, 거리가 d 이상인 두 정점 사이만 이동할 수 있을 때 u에서 v로 가는 최소 이동 횟수를 구한다.어려움9트리그래프+2아직 제출이 없습니다1초256 MB지문만 제공
숭고한 마라톤 대회트리에 간선 두 개를 추가해 어떤 두 교차로 사이에 내부 정점을 공유하지 않는 세 경로가 존재하도록 만드는 방법의 수를 센다.어려움9트리조합론+2아직 제출이 없습니다2초512 MB지문만 제공
애완 트리트리의 각 간선 길이를 주어진 범위에서 정할 때 지름이 S 이상 E 이하가 되는 조합의 수를 세어 1e9+7로 나눈 나머지를 구한다.어려움9동적 계획법트리+2아직 제출이 없습니다8초1024 MB채점 가능
관광 사업가중치 트리에서 각 질의마다 서로소인 후보 도시 집합 A, B와 인구가 주어질 때, X는 A에서 Y는 B에서 골라 (C_X+C_Y)*dist(X,Y)를 최대로 만드는 값을 구한다.어려움9트리분할 정복+2아직 제출이 없습니다5초1024 MB지문만 제공
즐거운 행로차수가 3 이하인 미지의 트리에서 거리와, X에서 어떤 정점으로 가는 경로가 Y를 지나는 정점의 수를 Q번 이하의 질의로 구한다.어려움9트리분할 정복+1아직 제출이 없습니다2초512 MB지문만 제공
Firefighting가중치가 있는 트리에서 모든 마을이 선택한 마을 중 하나로부터 거리 K 이내에 있도록 최소 개수의 마을을 소방서로 골라, 그 개수와 한 가지 배치를 출력한다.어려움9트리그리디+2아직 제출이 없습니다3초512 MB지문만 제공
Star Trek나무의 D개 평행 우주 사본에 포털을 배치할 때, 새로운 행성을 방문하는 게임에서 선공이 이기는 배치의 수를 구한다.어려움9트리게임 이론+2아직 제출이 없습니다1초32 MB지문만 제공
섬N개의 마을이 잎이고 내부 정점의 차수가 모두 3 이상인 트리의 간선 목록이 주어질 때, 바깥 면으로 실현 가능한 잎들의 서로 다른 원형 순서의 개수를 세어 소인수 거듭제곱의 곱으로 출력한다. 이때 회전은 같은 순서로 본다. 요구되는 출력 형식에 맞춰 지수를 곱해 정리한다.어려움9트리DFS+2아직 제출이 없습니다1초512 MB채점 가능
Circuit단일 전선 네트워크를 직렬 및 병렬로 합성해 만든 그래프가 주어질 때, 전선을 제거해 신장 트리를 만드는 경우의 수를 998244353으로 나눈 나머지를 구한다.어려움9그래프트리+2아직 제출이 없습니다1초512 MB지문만 제공
Connecting Supertrees모든 노드 쌍 사이의 서로 다른 경로 수(0에서 3)가 주어질 때, 그 값을 만족하는 단순 무향 그래프를 만들거나 불가능함을 판정한다.어려움9그래프유니온 파인드+1아직 제출이 없습니다1초1024 MB지문만 제공
트리와 쿼리 17루트 있는 트리에서 서브트리 증가와 경로 증가 쿼리를 처리한 뒤, 매번 가중 1-중앙값 정점을 출력한다.어려움9트리누적 합+2아직 제출이 없습니다2초1024 MB지문만 제공
Nowruz 3바위가 있는 격자에서 자유 칸 일부를 덤불로 막아 남은 자유 칸이 트리를 이루도록 만들고, 아이가 숨을 수 있는 잎 칸을 최대한 많이 확보하는 문제다.어려움9그래프트리+2아직 제출이 없습니다1초512 MB지문만 제공
Nowruz 9일부 칸이 막힌 격자에서 자유 칸을 지워 남은 자유 칸들이 트리(임의의 두 칸 사이 단순 경로가 정확히 하나)를 이루도록 하면서, 자유 이웃을 정확히 하나 가진 칸의 수를 최대화한다.어려움9그래프트리+2아직 제출이 없습니다1초512 MB지문만 제공
Nowruz 10바위가 있는 격자에서 빈 칸에 덤불을 심어 남은 빈 칸들이 트리를 이루도록 만들고, 자유 이웃이 정확히 하나인 칸의 수를 최대화한다.어려움9그래프트리+2아직 제출이 없습니다1초512 MB지문만 제공
트리와 쿼리 18루트가 바뀌는 상황에서 서브트리 덧셈, 경로 덧셈, 그리고 한 정점에서의 거리 가중 합을 구하는 트리 쿼리 문제다.어려움9트리세그먼트 트리+2아직 제출이 없습니다5초512 MB지문만 제공
Treasure Hunt경로가 단계적으로 확장되며 자라는 트리에서, 두 정점을 잇는 유일한 경로의 중간점을 매 질의마다 구한다.어려움9트리이분 탐색+2아직 제출이 없습니다2초512 MB지문만 제공
거리의 기댓값새 정점을 이전 정점에 a_j에 비례하는 확률로 붙여 트리를 만들 때, 두 정점 사이 거리의 기댓값을 10^9+7로 나눈 나머지로 구하는 문제다.어려움9트리확률+2아직 제출이 없습니다4초1024 MB지문만 제공
둥둥섬 다리 재정비하기모든 간선 비용이 2인 트리에서 정확히 a개의 간선을 비용 1로 재정비할 때, 각 쿼리 (수도 u, 개수 a)마다 모든 섬에서 u까지 거리 합의 최솟값을 구한다.어려움9트리DFS+2아직 제출이 없습니다3초1024 MB지문만 제공
정기 모임 2정점 1부터 i까지로 이루어진 각 모임에서, 모임을 X개의 장소로 나눌 때 가능한 최대 이동 거리의 최솟값을 X=1부터 K까지 더한 값을 모든 i에 대해 구한다. 두 정점 사이 거리는 경로 위 간선 가중치의 최댓값이다.어려움9트리그리디+2아직 제출이 없습니다3초1024 MB지문만 제공
트리와 쿼리 19흰색과 검정색 정점으로 이루어진 루트 트리에서 정점 하나의 색을 바꿀 때마다 모든 흰색 정점 쌍의 LCA 레벨 합을 구하고, 초기 상태의 값도 출력한다.어려움9트리동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Tokens on the Tree트리 위에서 토큰을 미끄러뜨려 옮길 때 생기는 흰색/검은색 배치의 동치류 개수를 모든 개수 조합에 대해 가중 합으로 구한다.어려움9트리DFS+2아직 제출이 없습니다1초256 MB지문만 제공
Towns and Roads열리고 닫히는 간선을 가진 트리에서 로봇이 열린 간선만 따라 이동하며, 각 질의 후 로봇 위치에서 가장 먼 마을을 모두 오름차순으로 출력한다.어려움9트리DFS+2아직 제출이 없습니다2초512 MB지문만 제공
Wind of Change 2020같은 N개 정점 위의 두 가중치 트리가 주어질 때, 모든 쌍 x, y에 대해 depth1(x)+depth1(y)-depth1(LCA1(x,y))-depth2(LCA2(x,y))의 최댓값을 구한다.어려움9트리분할 정복+2아직 제출이 없습니다12초1024 MB지문만 제공
Rikka with Storehouse완전 이진 트리 마지막 절반 노드의 높이가 고정되어 있을 때 나머지 노드의 높이를 정해 모든 간선 높이 차의 제곱합을 최소화하고, 갱신마다 답을 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Rikka with Generals번호가 인접한 장군끼리 도로로 이어진 도시를 교환할 수 있을 때, 처음 배정에서 도달 가능한 배정의 가짓수를 998244353으로 나눈 나머지로 구한다.어려움9그래프조합론+2아직 제출이 없습니다2초512 MB지문만 제공
Social Distancing트리 위에서 k명의 학생과 k대의 컴퓨터가 각각 서로 인접하지 않은 방에 놓여 있을 때, 학생들이 항상 서로 인접하지 않도록 한 칸씩 이동해 모든 학생을 컴퓨터 방으로 옮길 수 있는지 판정하고, 4n^2 이내의 이동 순서를 출력한다.어려움9트리그래프+2아직 제출이 없습니다10초512 MB지문만 제공
Game on a Tree각 노드에 색 카드가 놓인 트리에서 m번의 라운드마다 경로 위 색을 모든 참가자의 덱에 토글하고 GCD 기반 점수를 합산한 뒤 노드 하나의 색을 바꾼다.어려움9트리수학+2아직 제출이 없습니다5초512 MB지문만 제공
Königsberg Bridges그래프에 간선을 추가해 어떤 단순 경로가 모든 다리를 지나도록 만들 때, 결과 그래프가 가질 수 있는 다리 개수의 최댓값을 구한다.어려움9그래프DFS+2아직 제출이 없습니다3초512 MB지문만 제공
Binary Search Tree여러 BST에 서로 다른 값을 구간 삽입하고, 특정 값을 찾을 때 방문하는 노드 값의 합을 구한다.어려움9트리세그먼트 트리+2아직 제출이 없습니다2초256 MB지문만 제공
Colorful Componentsn개 정점에 색이 주어질 때, 서로 다른 색을 잇는 간선을 지운 뒤 남는 각 단색 연결 성분의 크기가 k 이하가 되도록 하는 연결 그래프(트리)의 개수를 세어 10^9+7로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Find the LCA부모 p_i가 i보다 작은 N개 정점의 모든 루트 트리에 대해, 정점 N-1과 N의 최소 공통 조상 x를 루트로 하는 부분 트리에 속한 A_v의 곱을 모두 더해 998244353으로 나눈 나머지를 구한다.어려움9조합론수학+2아직 제출이 없습니다7초1024 MB지문만 제공
Kingdom Division가중치가 있는 트리를 P명의 영주에게 나눠 줄 때, 각 부분이 연결되어 있고 값의 합이 모두 같도록 분할하는 문제입니다.어려움9트리동적 계획법+2아직 제출이 없습니다2초1024 MB지문만 제공
Вышивка жемчугом구슬 자수 그래프가 주어지고, 각 질의 직사각형 영역 안에서 연결 요소 개수를 세는 문제다. 그래프는 구슬을 차례로 붙여 만든 트리 구조다.어려움9그래프트리+2아직 제출이 없습니다2초1024 MB지문만 제공
Meetings 2나무에서 j명의 참가자가 모일 때 거리 합을 최소로 하는 섬의 개수의 최댓값을 모든 j에 대해 구한다.어려움9트리DFS+2아직 제출이 없습니다4초256 MB지문만 제공
Road Service 2도시 N개로 이루어진 트리가 주어질 때, 모든 도시 쌍 사이 거리의 합이 최소가 되도록 추가할 K개의 도로를 출력한다.어려움9트리그리디+2아직 제출이 없습니다1초512 MB지문만 제공
Road Service 4N개 정점으로 이루어진 트리가 주어질 때 모든 정점 쌍 거리의 합이 최소가 되도록 K개의 간선을 추가하는 계획을 출력하는 문제로, 정답의 정확성보다 출력의 품질로 점수를 매긴다.어려움9트리그래프+2아직 제출이 없습니다1초512 MB지문만 제공
Road Service 5N개 도시로 이루어진 트리가 주어질 때, K개의 간선을 추가해 모든 도시 쌍 사이 거리의 합이 최소가 되도록 하는 계획을 출력한다.어려움9트리그리디+2아직 제출이 없습니다1초512 MB지문만 제공
Road Service 6N개 도시로 이루어진 트리가 주어질 때, 모든 도시 쌍 사이 거리의 합이 최소가 되도록 K개의 도로를 새로 지어야 한다. 정답을 채점하는 출력 전용 최적화 문제이다.어려움9트리그리디+2아직 제출이 없습니다1초512 MB지문만 제공
Through Another Maze Darkly각 방의 포인터가 이웃을 정해진 순서로 순환하는 트리에서, 방 1에서 출발해 정확히 K번 이동한 뒤 도착하는 방을 구하는 질의에 답한다. K는 10^15까지 커질 수 있다.어려움9트리시뮬레이션+2아직 제출이 없습니다8초512 MB지문만 제공
Inside information트리 구조의 서버들이 간선을 따라 데이터를 공유할 때, 각 공유 연산 이후 특정 서버가 데이터 조각을 보유하는지 또는 몇 개의 서버가 보유하는지를 답하는 문제입니다.어려움9트리유니온 파인드+2아직 제출이 없습니다2초512 MB지문만 제공
밀림 점프오랑우탄이 현재 나무에서 왼쪽이나 오른쪽으로 가장 가까운 더 높은 나무로만 점프할 수 있을 때, 시작 구간과 도착 구간이 주어지면 최소 점프 횟수를 구한다.어려움9트리이분 탐색+2아직 제출이 없습니다3초1024 MB지문만 제공
Balanced Tree일부 색이 정해진 트리에서 남은 노드의 색을 정해 같은 색 노드가 거리 D 안에 있도록 만들고, D를 최소로 하는 색칠을 출력한다.어려움9트리그리디+2아직 제출이 없습니다2초512 MB지문만 제공
철도라벨이 있는 트리에 가짜 간선 K개와 특별한 표시 하나를 더해 그린 그림만으로 원래 트리를 복원하는 인코더와 디코더를 설계하는 문제다.어려움9트리그래프+1아직 제출이 없습니다1초1024 MB지문만 제공
Налог на проезд트리의 각 간선에 세금을 정해 모든 최단 경로 이동의 총 수입이 정확히 m이 되는 경우의 수를 1e9+7로 나눈 나머지로 구한다.어려움9트리DFS+2아직 제출이 없습니다2초256 MB지문만 제공
Truck각 간선에 통행료가 있는 가중치 트리에서 통행료 변경 갱신과, G개의 금과 통행료를 함께 옮길 때 드는 최소 연료를 경로마다 구해 1e9+7로 나눈 나머지를 출력한다.어려움9트리동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공