시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB18911310058.140%

문제

축제가 한창인 홍익대학교에서 학생회 소속의 네트워크 관리자 홍익이는 축제 기간 동안 캠퍼스 곳곳에 설치된 $N$개의 행사 부스를 관리합니다. 각 부스는 1번부터 $N$번까지의 번호를 가집니다.

원활한 행사 진행을 위해, 홍익이는 $M$개의 임시 무선 라우터를 대여했습니다. 각 라우터는 특정 두 부스를 지정된 시간 동안만 연결할 수 있습니다. 예를 들어, $i$번째 라우터는 $u_i$번 부스와 $v_i$번 부스를 축제 시작 후 $s_i$초부터 축제가 끝나는 $T$초까지 계속 연결합니다.

홍익이는 전체 네트워크의 안정성을 실시간으로 파악하기 위해 불안정 점수를 도입했습니다. 특정 시각 $t$에서의 불안정 점수는, 해당 시각에 서로 연결된 부스들의 묶음의 개수, 즉 연결 요소(Connected Components)의 개수로 정의됩니다. 불안정 점수가 높을수록 네트워크가 여러 묶음으로 나뉘어 불안정하게 됩니다.

홍익이는 1부터 $T$까지의 각 정수 시각 $t$에 대한 불안정 점수를 모두 더한 총합을 계산하여 축제 기간 동안 네트워크의 안정성을 체크하려고 합니다. 바쁜 홍익이를 도와 네트워크 안정성을 대신 측정해 주세요!

입력

첫째 줄에 부스의 수 $N$, 임시 라우터의 수 $M$, 축제 기간 $T$가 공백으로 구분되어 주어집니다. ($2 \le N \le 100\ 000,\ 1 \le M \le 100\ 000,\ 2 \le T \le 10^9$)

다음 $M$개의 줄에 걸쳐 각 라우터의 정보 $u, v, s$가 주어집니다. 이는 $u$번 부스와 $v$번 부스가 $s$초부터 $T$초까지 연결됨을 의미합니다. ($1 \le u, v \le N,\ u \ne v,\ 1 \le s < T$)

출력

1부터 $T$까지의 각 정수 시각 $t$에 대한 불안정 점수의 총합을 출력합니다.

예제 입력 1

3 2 10
1 2 4
2 3 7

예제 출력 1

19

예제 입력 2

5 4 20
1 2 3
3 4 8
2 3 12
4 5 12

예제 출력 2

51

예제 입력 3

6 7 25
3 4 5
1 2 1
1 3 5
5 6 10
2 3 1
2 1 10
4 3 12

예제 출력 3

63

출처

University > 홍익대학교 > 2025 HICON 홍익대학교 프로그래밍 경진대회 F번