시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB756511.628%

문제

FXC 나라 국가대표 코치 희승이는 육상선수 제이의 훈련을 하기 위해 아브레 선수촌에 도착하였다. 아브레 선수촌은 $N$개의 구역을 $N-1$개의 양방향 도로로 이어서 모든 구역을 직ㆍ간접적으로 연결하고 있다. 모든 구역에는 $0$ 이상 $N-1$ 이하의 서로 다른 정수 번호가 붙어있다.

희승이는 육상 연습을 위해 선수촌의 일부 구역에 허들을 설치하려 한다. 허들이 너무 빼곡하게 배치되어 있으면 제이의 연습 효율이 낮아지기 때문에 도로로 직접 연결된 두 구역에 동시에 허들을 배치할 수 없다.

희승이는 아브레 선수촌에 미리 허들을 설치한 다음 가능한 모든 종류의 연습 코스를 만들 것이다. 연습 코스는 다음 조건을 만족해야 한다.

  • 연습 코스는 $2$개 이상의 구역을 포함하는 경로이다.
  • 같은 구역을 여러 번 지날 수 없다.
  • 연습 코스는 최대한 많은 구역을 지나야 한다.

희승이는 제이가 선수촌을 둘러보면서 하나 이상의 연습 코스에 포함되는 구역이 몇 개인지 파악할 수 있으면 좋겠다고 한다. 그러나 제이는 선수촌 지도가 없어서 각 구역마다 자신 및 자신과 인접한 구역에 있는 허들의 수를 센 다음 답을 예측해야 한다. 희승이가 선수촌에 허들을 배치하고 제이가 답을 예측하는 방법을 구현하는 프로그램을 작성하여라.

함수 목록 및 정의

여러분은 아래 두 함수를 구현해야 한다.

int[] assign_hurdles(int[] S, int[] E)}
  • $S, E$: 길이가 $N-1$인 배열. 선수촌의 $i+1$번째 도로는 $S[i]$번 구역과 $E[i]$번 구역을 연결한다. ($0 \leq S[i], E[i] < N$)
  • 이 함수는 크기가 $N$인 배열 $H$를 반환해야 한다. 희승이가 $i$번 구역에 허들을 설치한다면 $H[i] = 1$, 그렇지 않다면 $H[i] = 0$이어야 한다.
int find_useful_zones(int[] A)
  • $A$: 길이가 $N$인 배열. $A[i]$는 $i$번 구역 및 $i$번 구역과 인접한 구역에 있는 허들의 수이다.
  • 이 함수는 하나 이상의 연습 코스에 포함되는 구역의 수를 반환해야 한다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

여러분의 프로그램은 두 번 실행된다. 첫 번째 실행에서는 assign_hurdles 함수만 호출하며 두 번째 실행에서는 find_useful_zones 함수만 호출한다. 프로그램의 실행 시간은 두 번의 실행 시간을 합한 값이며 메모리 사용량은 두 번의 사용 메모리 중 최댓값으로 계산된다.

서브태스크

모든 데이터에 대해서, $2 ≤ N ≤ 10^6$을 만족한다.

번호배점제한
11

$0$이 아닌 모든 $i$에 대하여 $S[i] = i, E[i] = i+1$를 만족한다. $i = 0$일 때에는 조건을 만족하지 않을 수 있음에 유의하여라.

21

$N \leq 1\,000$

31

추가 제약조건은 없다.

예제 1

선수촌의 도로 정보 S = [0, 2, 3, 1, 1], E = [1, 4, 5, 2, 3]인 경우를 생각해보자. $0$번 구역을 제외한 모든 구역이 하나 이상의 연습 코스에 포함된다.

그레이더는 처음에 assign_hurdles([0, 2, 3, 1, 1], [1, 4, 5, 2, 3])을 호출한다. 희승이가 $2$, $3$번 구역에 허들을 설치한다면 assign_hurdles 함수는 [0, 0, 1, 1, 0, 0]을 반환한다.

이후 그레이더는 find_useful_zones([0, 2, 1, 1, 1, 1])를 호출한다. 여러분은 해당 함수에서 $5$를 반환해야 한다.

샘플 그레이더

샘플 그레이더는 첫 번째 줄에 $N$을 입력받는다. 두 번째 줄부터 $N-1$개의 줄에는 $S[i], E[i]$를 입력받는다.

샘플 그레이더는 첫 번째 줄에 find_useful_zones의 반환값을 출력한다.

실제 채점에서 사용하는 그레이더는 샘플 그레이더와 다를 수 있음에 유의하여라.

출처

Contest > BOJ User Contest > FunctionCup > FunctionCup 2023 IJ번

제출할 수 있는 언어

C++17, C++20, C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.