F - Range Connect MST

Contest Duration: 2024-07-27(Sat) 12:00 - 2024-07-27(Sat) 13:40 (local time) (100 minutes) Back to Home

F - Range Connect MST Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

$N + Q$ 頂点のグラフがあり、頂点には $1, 2, \ldots, N + Q$ の番号がついています。グラフにははじめ辺がありません。

このグラフに対して $i = 1, 2, \ldots, Q$ の順に以下の操作を行います。

$L_i \leq j \leq R_i$ を満たす各整数 $j$ について頂点 $N + i$ と頂点 $j$ の間にコスト $C_i$ の無向辺を追加する

すべての操作を終えた後グラフは連結であるか判定し、連結である場合はこのグラフの最小全域木のコストを求めてください。

ただし、最小全域木とはコストが最小の全域木のことを指し、全域木のコストとは全域木に使われた辺のコストの和のことを指します。

制約

$1 \leq N, Q \leq 2 \times 10^5$
$1 \leq L_i \leq R_i \leq N$
$1 \leq C_i \leq 10^9$
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $Q$ 
 $L_1$   $R_1$   $C_1$ 
 $L_2$   $R_2$   $C_2$ 
 $\vdots$ 
 $L_Q$   $R_Q$   $C_Q$

出力

グラフが連結である場合は最小全域木のコストを出力せよ。そうでない場合は $-1$ を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

以下の辺からなる全域木が最小全域木のひとつとなります。

頂点 $1$ と $5$ を結ぶコスト $2$ の辺
頂点 $2$ と $5$ を結ぶコスト $2$ の辺
頂点 $1$ と $6$ を結ぶコスト $4$ の辺
頂点 $3$ と $6$ を結ぶコスト $4$ の辺
頂点 $3$ と $7$ を結ぶコスト $5$ の辺
頂点 $4$ と $7$ を結ぶコスト $5$ の辺

$2 + 2 + 4 + 4 + 5 + 5 = 22$ であるため、 $22$ を出力します。

入力例 2Copy

Copy

6 2
1 2 10
4 6 10

出力例 2Copy

Copy

-1

グラフは非連結です。

入力例 3Copy

Copy

200000 4
1 200000 1000000000
1 200000 998244353
1 200000 999999999
1 200000 999999999

出力例 3Copy

Copy

199651870599998

Score : $500$ points

Problem Statement

There is a graph with $N + Q$ vertices, numbered $1, 2, \ldots, N + Q$ . Initially, the graph has no edges.

For this graph, perform the following operation for $i = 1, 2, \ldots, Q$ in order:

For each integer $j$ satisfying $L_i \leq j \leq R_i$ , add an undirected edge with cost $C_i$ between vertices $N + i$ and $j$ .

Determine if the graph is connected after all operations are completed. If it is connected, find the cost of a minimum spanning tree of the graph.

A minimum spanning tree is a spanning tree with the smallest possible cost, and the cost of a spanning tree is the sum of the costs of the edges used in the spanning tree.

Constraints

$1 \leq N, Q \leq 2 \times 10^5$
$1 \leq L_i \leq R_i \leq N$
$1 \leq C_i \leq 10^9$
All input values are integers.

Input

The input is given from Standard Input in the following format:

 $N$   $Q$ 
 $L_1$   $R_1$   $C_1$ 
 $L_2$   $R_2$   $C_2$ 
 $\vdots$ 
 $L_Q$   $R_Q$   $C_Q$

Output

If the graph is connected, print the cost of a minimum spanning tree. Otherwise, print $-1$ .

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

The following edges form a minimum spanning tree:

An edge with cost $2$ connecting vertices $1$ and $5$
An edge with cost $2$ connecting vertices $2$ and $5$
An edge with cost $4$ connecting vertices $1$ and $6$
An edge with cost $4$ connecting vertices $3$ and $6$
An edge with cost $5$ connecting vertices $3$ and $7$
An edge with cost $5$ connecting vertices $4$ and $7$

Since $2 + 2 + 4 + 4 + 5 + 5 = 22$ , print $22$ .

Sample Input 2Copy

Copy

6 2
1 2 10
4 6 10

Sample Output 2Copy

Copy

-1

The graph is disconnected.

Sample Input 3Copy

Copy

200000 4
1 200000 1000000000
1 200000 998244353
1 200000 999999999
1 200000 999999999

Sample Output 3Copy

Copy

199651870599998