33610번 - 넘버링 서브태스크언어 제한함수 구현

문제

KOI 도시는 $N$개의 교차로와 $M$개의 양방향 도로로 이루어져 있으며, 임의의 서로 다른 두 교차로를 도로만을 사용하여 오갈 수 있다. 같은 두 교차로를 잇는 양방향 도로가 2개 이상 있을 수도 있다.

각각의 교차로에는 0ドル$부터 $N-1$까지의 서로 다른 번호가 붙어 있고, 각각의 양방향 도로에는 0ドル$부터 $M-1$까지의 서로 다른 번호가 붙어 있다.

길이가 $N$인 정수 배열 $a[0],ドル $a[1],ドル $\cdots,ドル $a[N-1]$이 아래 조건을 만족한다면, $a$는 굿 넘버링이다.

• 동일한 도로를 두 번 이상 지나지 않는 임의의 경로에 대해서, 경로에서 방문한 순서대로 교차로의 번호를 나열한 수열을 $u_0, u_1, \ldots, u_{l-1}$이라 할 때 $a[u_0] \le a[u_1] \le \ldots \le a[u_{l-1}]$ 또는 $a[u_0] \ge a[u_1] \ge \ldots \ge a[u_{l-1}]$가 성립한다. 경로에서 동일한 교차로는 두 번 이상 지날 수 있음에 유의하라.

길이가 $N$인 정수 배열 $a[0],ドル $a[1],ドル $\cdots,ドル $a[N-1]$의 다양성은 $a[u] \neq a[v]$이면서 0ドル \leq u < v \leq N-1$을 만족하는 $(u, v)$ 쌍의 개수이다.

도로망 구조가 주어졌을 때, 모든 굿 넘버링 중 다양성의 최댓값을 구하는 프로그램을 작성하라.

함수 목록 및 정의

다음 함수를 구현해야 한다:

long long max_diversity(int N, int M, vector<int> U, vector<int> V)

• $N$: 교차로의 개수
• $M$: 도로의 개수
• $U,ドル $V$: 모든 0ドル \le i \le M-1$에 대해, $i$번 도로는 $U[i]$번 교차로와 $V[i]$번 교차로 ($U[i] \neq V[i]$)를 잇는다.
• 이 함수는 모든 굿 넘버링 중 다양성의 최댓값을 반환해야 한다.

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

입력

출력

제한

• 2ドル \le N \le 1,000円,000円$
• 1ドル \le M \le 2,000円,000円$
• $U[i] \neq V[i]$ (모든 0ドル \leq i \leq M-1$)
• 0ドル \le U[i], V[i] \le N-1$ (모든 0ドル \le i \le M-1$)

서브태스크 1 (1점)

• $M = N-1$
• 4ドル$개 이상의 도로와 인접한 교차로가 존재하지 않음
• $N \le 500$

서브태스크 2 (4점)

• $M = N-1$
• 4ドル$개 이상의 도로와 인접한 교차로가 존재하지 않음
• $N \le 5000$

서브태스크 3 (5점)

• $M = N-1$
• 4ドル$개 이상의 도로와 인접한 교차로가 존재하지 않음

서브태스크 4 (3점)

• $M = N-1$
• $N \le 500$

서브태스크 5 (5점)

• $M = N-1$
• $N \le 5000$

서브태스크 6 (28점)

• $M = N-1$

서브태스크 7 (6점)

• $N \le 500$
• $M \le 1000$

서브태스크 8 (10점)

• $N \le 5000$
• $M \le 10000$

서브태스크 9 (38점)

• 추가 제약 조건 없음

힌트

예제 1

$N = 5,ドル $M = 5,ドル $U= [0, 0, 1, 1, 2],ドル $[1, 2, 2, 3, 4]$인 경우를 생각해 보자.

그레이더는 다음과 같이 함수를 호출한다.

$a = [2, 1, 1, 3, 1]$는 굿 넘버링이 아니다. $u_0 = 0, u_1 = 1, u_2 = 3$일 때, $a[u_0] = 2,ドル $a[u_1] = 1,ドル $a[u_2] = 3$이므로, $a[u_0] \le a[u_1] \le a[u_2]$와 $a[u_0] \ge a[u_1] \ge a[u_2]$ 모두 만족하지 않기 때문이다.

$[1, 1, 1, 1, 1]$는 굿 넘버링이고, 그 다양성은 0이다.

$[2, 2, 2, 3, 0]$는 굿 넘버링이고, 그 다양성은 7이다.

이외에도 다양한 굿 넘버링이 있을 수 있다. 위와 같은 방식으로 모든 굿 넘버링의 다양성을 구하면, 그 중 최댓값은 7이다. 따라서, 함수는 7을 반환해야 한다.

예제 1

Sample grader는 아래와 같은 형식으로 입력을 받는다.

• Line 1ドル$: $N$ $M$
• Line 2ドル+i$ $(0 \le i \le M-1)$: $U[i]$ $V[i]$

Sample grader는 다음을 출력한다.

• Line 1ドル$: 함수 max_diversity의 반환값

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

첨부

• numbering_public.zip