| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 98 | 54 | 50 | 53.191% |
현대오토에버는 자율주행차의 안전성 확보에 관한 국제 표준인 SOTIF(Safety Of The Intended Functionality) 인증을 국내 최초로 획득하며, 차량 소프트웨어 분야에서 선도적인 위치를 확고히 하고 있다. SOTIF 인증을 위해서는 발생 가능한 모든 위험 상황을 분석하고, 각 상황에 맞는 안전 요구사항을 정의하며, 실제 도로 환경을 고려한 체계적인 해결책을 검증해야 한다. 현대오토에버는 이와 같은 엄격한 절차를 통해, 차량 소프트웨어 플랫폼 ‘모빌진 클래식’ 2.0으로 ‘A-SPICE CL3’ 및 ‘ISO 26262 ASIL-D’ 인증과 같은 다양한 국제 표준 인증을 연달아 획득했다.
이러한 성과의 바탕에는 자율주행차의 안전성을 확인하기 위한 다양한 테스트들이 있다. 그중 하나는 실제 도로와 유사한 환경을 구성한 테스트 부지에서 자율주행차가 안전하게 주행할 수 있는지 평가하는 것이다.
테스트 부지는 $N$개의 체크포인트와 이들을 연결하는 양방향 도로 $M$개로 이루어진 그래프로 표현된다. 각 체크포인트는 1ドル$부터 $N$까지 번호가 매겨져 있으며, 1ドル$번 체크포인트는 자율 주행 자동차들이 출발하는 차고지이다. 각 도로는 1ドル$부터 $M$까지 번호가 매겨져 있고, $i$번 도로는 체크포인트 $u_i$와 $v_i$를 연결하고 있다. 테스트 매니저인 당신의 임무는 모든 $M$개의 도로의 길이를 결정하는 것이다. $i$번 도로의 길이는 $L_i \leq x \leq R_i$를 만족하는 정수 $x$로 설정할 수 있다.
실험에서는 2ドル$번부터 $N$번까지의 자동차가 동시에 차고지(1ドル$번 체크포인트)에서 출발하여 각자의 번호에 맞는 체크포인트($i$번 자동차는 $i$번 체크포인트)를 목적지로 최단 경로로 이동한다. 이곳의 테스트 매니저인 당신은 $i$번 자동차가 정확히 $D_i$만큼의 거리를 주행하도록 도로들의 길이를 설정하려고 한다.
당신은 도로의 길이를 정하는 모든 방법 중, 조건을 만족하도록 도로의 길이를 정하는 방법의 가짓수가 문득 궁금해졌다. 도로의 길이를 정하는 방법의 가짓수를 출력하시오.
첫 번째 줄에 체크포인트의 수 $N,ドル 도로의 수 $M$이 공백으로 구분되어 주어진다. $(2 \leq N \leq 200,000円; 1 \leq M \leq 400,000円)$
두 번째 줄에 $i(2\leq i \leq N)$번째 차가 주행하게 하고 싶은 거리 $D_2, \cdots, D_N$가 공백으로 구분되어 주어진다. $(1 \leq D_i \leq 10^{15})$
세 번째 줄부터 $M$개의 줄에 걸쳐 $i$번 도로에 대한 정보 $u_i, v_i, L_i, R_i$가 공백으로 구분되어 주어진다.
1ドル$번 체크포인트에서 다른 모든 체크포인트로 이동하는 경로가 하나 이상 있음이 보장되며, 임의의 두 체크포인트를 잇는 도로는 2ドル$개 이상일 수도 있다.
조건을 만족하도록 도로의 길이를 정하는 방법의 가짓수를 출력하시오. 단, 가짓수가 매우 클 수 있으므로 1ドル,000円,000円,007円$으로 나눈 나머지를 출력한다.
4 5 4 8 7 1 2 3 6 1 3 10 12 2 3 3 5 2 4 2 5 3 4 6 8
9
도로의 길이를 오른쪽 그림과 같이 설정하면, 2ドル,ドル 3ドル,ドル 4ドル$번 차는 각각 4ドル,ドル 8ドル,ドル 7ドル$만큼의 거리를 주행하게 되고, 이는 조건을 만족하도록 도로의 길이를 정하는 방법 중 하나이다.
3 2 10 17 1 2 11 20 1 3 9 21
0