25299번 - 산유국 서브태스크언어 제한함수 구현

문제

아제르바이잔은 지하자원이 풍부한 나라로 석유가 생산되어 국민들은 휘발유를 아주 저렴하게 사용할 수 있다. 아제르바이잔의 수도 바쿠에는 $N$개의 교차로와 $M+N-1$개의 양방향 도로가 있다 바쿠는 남북으로 길이가 긴 도시이다. 교차로는 남북 방향으로 일직선으로 늘어서 있는데, 제일 북쪽 교차로에서 시작하여 1ドル$번부터 $N$번까지 번호가 붙어 있다. 도로는 오래된 도로와 신설 도로들이 있다. $N-1$개의 오래된 도로는 각 $i$ (1ドル \le i < N$)에 대해서 $i$번 교차로와 $i+1$번 교차로를 연결한다. $M$개의 신설 도로는 각각 오래된 도로로 연결되지 않은 서로 다른 교차로 두 개를 연결한다. 한 쌍의 교차로를 연결하는 도로는 최대 1ドル$개이다.

수도 바쿠는 재정이 최근 좋지 않아 도로 중 일부에 톨게이트를 설치해서 통행료를 받기로 했다. 너무 많은 도로에서 통행료를 받으면 시민들의 불만이 생길 수 있으므로 정확히 2ドル$개의 도로에서 통행료를 받을 것이다. 통행료는 차 한 대가 톨게이트를 한번 지나갈 때 마다 1ドル$마나트(아제르바이잔 화폐 단위)를 받는다. 한 자동차가 톨게이트 두 개를 지나간다면, 두 번 모두 통행료를 내야 한다.

모든 교차로에는 각각 $N-1$대의 자동차가 있다. 한 교차로의 자동차들은 모두 현재 위치한 교차로가 아닌 서로 다른 교차로로 갈 것이다. 교차로 $u$에서 교차로 $v$로 갈 때, 운전자는 최소의 통행료를 내는 경로를 선택한다. (이 나라는 휘발유가 저렴하다.)

모든 자동차들이 자신의 목적지로 이동했을 때, 가장 많은 통행료를 받을 수 있는 두 도로를 알아내는 프로그램을 작성하라.

여러분은 다음 함수를 작성하여야 한다.

• long long findEdges( int N, int A[], int B[] ) ; 최초에 한번만 호출되는 함수이다. 교차로와 도로들의 형태를 알려준다. $N$은 교차로의 개수이다. $A$와 $B$는 각각 크기 $M$인 배열(vector)이다. 교차로 $A[i]$번과 교차로 $B[i]$번이 신설 도로로 이어져 있다는 의미이다. 단, $i$는 0ドル$ 이상 $M-1$ 이하이다. 주어진 교차로와 도로 상황에서 두 개의 도로에 톨게이트를 만들어서 받을 수 있는 가장 많은 통행료의 값을 리턴해야 한다.

구현 세부사항

여러분은 oil.cpp라는 이름의 정확히 하나의 파일을 제출해야 한다. 이 파일에는 다음의 함수가 구현되어 있어야 한다.

• long long findEdges( int N, int A[], int B[] ) ;

이 함수는 위에서 설명한 것과 같이 동작하여야 한다. 물론 다른 함수들을 만들어서 내부적으로 사용할 수 있다. 제출한 코드는 입출력을 수행하거나 다른 파일에 접근하여서는 안 된다.

그레이더 예시

주어지는 그레이더는 다음과 같은 형식으로 입력을 받는다.

• line 1ドル$: $N$ $M$
• 다음 $M$개의 줄: 2ドル$개의 자연수, 주어진 두 번호의 교차로가 신설 도로로 이어져 있다.

주어진 그레이더는 여러분의 코드가 findEdges() 함수에서 리턴한 값을 출력한다.

입력

출력

제한

서브태스크

힌트

첨부

• oil_public.zip