実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
3 桁の正整数 N が与えられます。 N を十進法で表したとき、すべての桁の数字が同じであるかどうかを判定してください。
制約
- 100 \leq N \leq 999
- 入力される値は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N を十進法で表したとき、すべての桁の数字が同じであるならば Yes を、同じでないならば No を 1 行で出力せよ。
入力例 1
444
出力例 1
Yes
444 の各桁の数字は 4,4,4 で同じなので Yes を出力してください。
入力例 2
160
出力例 2
No
160 の各桁の数字は 1,6,0 で同じではないので、No を出力してください。
入力例 3
999
出力例 3
Yes
Score : 100 points
Problem Statement
You are given a 3-digit positive integer N. Determine whether all digits are the same when N is represented in decimal.
Constraints
- 100 \leq N \leq 999
- The input value is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
If all digits are the same when N is represented in decimal, output Yes in one line; otherwise, output No.
Sample Input 1
444
Sample Output 1
Yes
The digits of 444 are 4,4,4, which are the same, so output Yes.
Sample Input 2
160
Sample Output 2
No
The digits of 160 are 1,6,0, which are not the same, so output No.
Sample Input 3
999
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
面積が正である三角形 ABC があります。
三角形 ABC の三辺の長さはそれぞれ a,b,c です。
三角形 ABC が二等辺三角形であるか判定してください。
制約
- 1 \leq a,b,c \leq 10
- 三辺の長さが a,b,c であるような三角形が存在し、その面積は正である。
- a,b,c は整数
入力
入力は以下の形式で標準入力から与えられる。
a b c
出力
三角形 ABC が二等辺三角形であるならば Yes を、そうでないならば No を出力せよ。
入力例 1
4 2 4
出力例 1
Yes
a=c であるため、三角形 ABC は二等辺三角形です。
よって、Yes を出力します。
入力例 2
3 4 5
出力例 2
No
三角形 ABC の三辺の長さはすべて異なるため、二等辺三角形ではありません。
よって、No を出力します。
入力例 3
10 10 10
出力例 3
Yes
正三角形も二等辺三角形の一種であることに注意してください。
Score : 100 points
Problem Statement
There is a triangle ABC with positive area.
The lengths of the three sides of triangle ABC are a,b,c.
Determine whether triangle ABC is isosceles.
Constraints
- 1 \leq a,b,c \leq 10
- A triangle with side lengths a,b,c exists, and its area is positive.
- a,b,c are integers.
Input
The input is given from Standard Input in the following format:
a b c
Output
If triangle ABC is isosceles, output Yes; otherwise, output No.
Sample Input 1
4 2 4
Sample Output 1
Yes
Since a=c, triangle ABC is isosceles.
Thus, output Yes.
Sample Input 2
3 4 5
Sample Output 2
No
Since the three side lengths of triangle ABC are all different, it is not isosceles.
Thus, output No.
Sample Input 3
10 10 10
Sample Output 3
Yes
Note that an equilateral triangle is a kind of isosceles triangle.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
選挙が行われています。
N 人が投票を行い、i\,(1 \leq i \leq N) 番目の人は S_i という名前の候補者に投票しました。
得票数が最大の候補者の名前を答えてください。なお、与えられる入力では得票数が最大の候補者は一意に定まります。
制約
- 1 \leq N \leq 100
- S_i は英小文字からなる長さ 1 以上 10 以下の文字列
- N は整数
- 得票数が最大の候補者は一意に定まる
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
得票数が最大の候補者の名前を出力せよ。
入力例 1
5 snuke snuke takahashi takahashi takahashi
出力例 1
takahashi
takahashi は 3 票、snuke は 2 票獲得しました。よって takahashi を出力します。
入力例 2
5 takahashi takahashi aoki takahashi snuke
出力例 2
takahashi
入力例 3
1 a
出力例 3
a
Score : 200 points
Problem Statement
An election is taking place.
N people voted. The i-th person (1 \leq i \leq N) cast a vote to the candidate named S_i.
Find the name of the candidate who received the most votes. The given input guarantees that there is a unique candidate with the most votes.
Constraints
- 1 \leq N \leq 100
- S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
- N is an integer.
- There is a unique candidate with the most votes.
Input
Input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the name of the candidate who received the most votes.
Sample Input 1
5 snuke snuke takahashi takahashi takahashi
Sample Output 1
takahashi
takahashi got 3 votes, and snuke got 2, so we print takahashi.
Sample Input 2
5 takahashi takahashi aoki takahashi snuke
Sample Output 2
takahashi
Sample Input 3
1 a
Sample Output 3
a
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
N 人の人がいます。i \, (1 \leq i \leq N) 人目の人の姓は S_i、名は T_i です。
同姓同名であるような人の組が存在するか、すなわち 1 \leq i \lt j \leq N かつ S_i=S_j かつ T_i=T_j を満たすような整数対 (i,j) が存在するか判定してください。
制約
- 2 \leq N \leq 1000
- N は整数
- S_i,T_i は英小文字のみからなる長さ 1 以上 10 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
N
S_1 T_1
S_2 T_2
\hspace{0.6cm}\vdots
S_N T_N
出力
同姓同名であるような人の組が存在するなら Yes を、存在しないなら No を出力せよ。
入力例 1
3 tanaka taro sato hanako tanaka taro
出力例 1
Yes
1 人目の人と 3 人目の人が同姓同名です。
入力例 2
3 saito ichiro saito jiro saito saburo
出力例 2
No
同姓同名であるような人の組は存在しません。
入力例 3
4 sypdgidop bkseq bajsqz hh ozjekw mcybmtt qfeysvw dbo
出力例 3
No
Score : 200 points
Problem Statement
There are N people. The family name and given name of the i-th person (1 \leq i \leq N) are S_i and T_i, respectively.
Determine whether there is a pair of people with the same family and given names. In other words, determine whether there is a pair of integers (i,j) such that 1 \leq i \lt j \leq N, S_i=S_j, and T_i=T_j.
Constraints
- 2 \leq N \leq 1000
- N is an integer.
- Each of S_i and T_i is a string of length between 1 and 10 (inclusive) consisting of English lowercase letters.
Input
Input is given from Standard Input in the following format:
N
S_1 T_1
S_2 T_2
\hspace{0.6cm}\vdots
S_N T_N
Output
If there is a pair of people with the same family and given names, print Yes; otherwise, print No.
Sample Input 1
3 tanaka taro sato hanako tanaka taro
Sample Output 1
Yes
The first and third persons have the same family and given names.
Sample Input 2
3 saito ichiro saito jiro saito saburo
Sample Output 2
No
No two persons have the same family and given names.
Sample Input 3
4 sypdgidop bkseq bajsqz hh ozjekw mcybmtt qfeysvw dbo
Sample Output 3
No
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
N 行 N 列のグリッドが与えられます。ここで、N は偶数です。グリッドの上から i 行目、左から j 列目のマスをマス (i, j) と表記します。
グリッドの各マスは黒か白のいずれかで塗られており、A_{i, j} = # のときマス (i, j) は黒、A_{i, j} = . のときマス (i, j) は白で塗られています。
i = 1, 2, \ldots, \frac{N}{2} の順に以下の操作を行った後のグリッドの各マスの色を求めてください。
- i 以上 N + 1 - i 以下の整数 x, y について、マス (y, N + 1 - x) の色をマス (x, y) の色で置き換える。この置き換えは条件を満たすすべての整数 x, y について同時に行う。
制約
- N は 2 以上 3000 以下の偶数
- A_{i, j} は
#または.
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1, 1}A_{1, 2}\ldotsA_{1, N}
A_{2, 1}A_{2, 2}\ldotsA_{2, N}
\vdots
A_{N, 1}A_{N, 2}\ldotsA_{N, N}
出力
すべての操作を終えた後、マス (i, j) の色が黒であるとき B_{i, j} = #、マス (i, j) の色が白であるとき B_{i, j} = . として以下の形式で出力せよ。
B_{1, 1}B_{1, 2}\ldotsB_{1, N}
B_{2, 1}B_{2, 2}\ldotsB_{2, N}
\vdots
B_{N, 1}B_{N, 2}\ldotsB_{N, N}
入力例 1
8 .......# .......# .####..# .####..# .##....# .##....# .####### .#######
出力例 1
........ #######. #.....#. #.###.#. #.#...#. #.#####. #....... ########
操作によってグリッドの各マスの色は以下のように変化します。
.......# ........ ........ ........ ........ .......# ######.. #######. #######. #######. .####..# ######.. #....##. #.....#. #.....#. .####..# → ##..##.. → #....##. → #.##..#. → #.###.#. .##....# ##..##.. #..####. #.##..#. #.#...#. .##....# ##...... #..####. #.#####. #.#####. .####### ##...... #....... #....... #....... .####### ######## ######## ######## ########
入力例 2
6 .#.#.# ##.#.. ...### ###... ..#.## #.#.#.
出力例 2
#.#.#. .#.#.# #.#.#. .#.#.# #.#.#. .#.#.#
入力例 3
12 .......#.### #...#...#..# ###.#..##### ..#.#.#.#... .#.....#.### .......#.#.. #...#..#.... #####....... ...#...#.#.# ..###..#..## #..#.#.#.#.# .####.......
出力例 3
.#..##...##. #.#.#.#.#... ###.##..#... #.#.#.#.#... #.#.##...##. ............ ............ .###.###.### ...#...#.#.. .###...#.### ...#...#...# .###...#.###
Score : 400 points
Problem Statement
You are given a grid with N rows and N columns, where N is an even number. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
Each cell is painted black or white. If A_{i, j} = #, cell (i, j) is black; if A_{i, j} = ., it is white.
Find the color of each cell after performing the following operation for i = 1, 2, \ldots, \frac{N}{2} in this order.
- For all pairs of integers x, y between i and N + 1 - i, inclusive, replace the color of cell (y, N + 1 - x) with the color of cell (x, y). Perform these replacements simultaneously for all such pairs x, y.
Constraints
- N is an even number between 2 and 3000, inclusive.
- Each A_{i, j} is
#or..
Input
The input is given from Standard Input in the following format:
N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}
Output
After all operations, let B_{i, j} = # if cell (i, j) is black, and B_{i, j} = . if it is white. Print the grid in the following format:
B_{1,1}B_{1,2}\ldots B_{1,N}
B_{2,1}B_{2,2}\ldots B_{2,N}
\vdots
B_{N,1}B_{N,2}\ldots B_{N,N}
Sample Input 1
8 .......# .......# .####..# .####..# .##....# .##....# .####### .#######
Sample Output 1
........ #######. #.....#. #.###.#. #.#...#. #.#####. #....... ########
The operations change the colors of the grid cells as follows:
.......# ........ ........ ........ ........ .......# ######.. #######. #######. #######. .####..# ######.. #....##. #.....#. #.....#. .####..# → ##..##.. → #....##. → #.##..#. → #.###.#. .##....# ##..##.. #..####. #.##..#. #.#...#. .##....# ##...... #..####. #.#####. #.#####. .####### ##...... #....... #....... #....... .####### ######## ######## ######## ########
Sample Input 2
6 .#.#.# ##.#.. ...### ###... ..#.## #.#.#.
Sample Output 2
#.#.#. .#.#.# #.#.#. .#.#.# #.#.#. .#.#.#
Sample Input 3
12 .......#.### #...#...#..# ###.#..##### ..#.#.#.#... .#.....#.### .......#.#.. #...#..#.... #####....... ...#...#.#.# ..###..#..## #..#.#.#.#.# .####.......
Sample Output 3
.#..##...##. #.#.#.#.#... ###.##..#... #.#.#.#.#... #.#.##...##. ............ ............ .###.###.### ...#...#.#.. .###...#.### ...#...#...# .###...#.###
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
子供と大人があわせて N 人います。i 番目の人の体重は W_i です。
それぞれの人が子供か大人かは、0 と 1 からなる長さ N の文字列 S によって表され、
S の i 文字目が 0 であるとき i 番目の人が子供であることを、1 であるとき i 番目の人が大人であることをさします。
ロボットである高橋君に対して実数 X を設定すると、
高橋君はそれぞれの人に対して、体重が X 未満なら子供、X 以上なら大人と判定します。
実数 X に対してf(X) を、高橋君に X を設定したときに N 人のうち子供か大人かを正しく判定できる人数で定めます。
X が実数全体を動くとき、f(X) の最大値を求めてください。
制約
- 1\leq N\leq 2\times 10^5
- S は
0と1からなる長さ N の文字列 - 1\leq W_i\leq 10^9
- N,W_i は整数
入力
入力は以下の形式で標準入力から与えられる。
N S W_1 W_2 \ldots W_N
出力
f(X) の最大値を整数で一行に出力せよ。
入力例 1
5 10101 60 45 30 40 80
出力例 1
4
X=50 と設定すると、高橋君は 2,3,4 番目の人を子供、 1,5 番目の人を大人と判定します。
実際には 2,4 番目の人が子供、 1,3,5 番目の人が大人であるので、このとき、1,2,4,5 番目の合計 4 人に対して正しく判定できています。
よって、f(50)=4 です。
5 人全員に対して正しく判定できるような X は存在しないのでこのときが最大です。よって、4 を出力します。
入力例 2
3 000 1 2 3
出力例 2
3
例えば、X=10 とすると最大値 f(10)=3 を達成します。
全員が大人、または全員が子供である可能性もあることに注意してください。
入力例 3
5 10101 60 50 50 50 60
出力例 3
4
例えば、X=55 とすると最大値 f(55)=4 を達成します。
同じ体重の人が複数人存在する可能性もあることに注意してください。
Score : 300 points
Problem Statement
There are N people, each of whom is either a child or an adult. The i-th person has a weight of W_i.
Whether each person is a child or an adult is specified by a string S of length N consisting of 0 and 1.
If the i-th character of S is 0, then the i-th person is a child; if it is 1, then the i-th person is an adult.
When Takahashi the robot is given a real number X,
Takahashi judges a person with a weight less than X to be a child and a person with a weight more than or equal to X to be an adult.
For a real value X, let f(X) be the number of people whom Takahashi correctly judges whether they are children or adults.
Find the maximum value of f(X) for all real values of X.
Constraints
- 1\leq N\leq 2\times 10^5
- S is a string of length N consisting of
0and1. - 1\leq W_i\leq 10^9
- N and W_i are integers.
Input
Input is given from Standard Input in the following format:
N S W_1 W_2 \ldots W_N
Output
Print the maximum value of f(X) as an integer in a single line.
Sample Input 1
5 10101 60 45 30 40 80
Sample Output 1
4
When Takahashi is given X=50, it judges the 2-nd, 3-rd, and 4-th people to be children and the 1-st and 5-th to be adults.
In reality, the 2-nd and 4-th are children, and the 1-st, 3-rd, and 5-th are adults, so the 1-st, 2-nd, 4-th, and 5-th people are correctly judged.
Thus, f(50)=4.
This is the maximum since there is no X that judges correctly for all 5 people. Thus, 4 should be printed.
Sample Input 2
3 000 1 2 3
Sample Output 2
3
For example, X=10 achieves the maximum value f(10)=3.
Note that the people may be all children or all adults.
Sample Input 3
5 10101 60 50 50 50 60
Sample Output 3
4
For example, X=55 achieves the maximum value f(55)=4.
Note that there may be multiple people with the same weight.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 425 点
問題文
H 行 W 列のマス目があります。 上から i 行目 (1\leq i\leq H)、左から j 列目 (1\leq j\leq W) のマスをマス (i,j) と呼ぶことにします。
マス (i,j)\ (1\leq i\leq H,1\leq j\leq W) には非負整数 A _ {i,j} が書かれています。
このマス目にドミノを 0 個以上置きます。 1 つのドミノは隣り合う 2 つのマス、つまり
- 1\leq i\leq H,1\leq j\lt W に対するマス (i,j) とマス (i,j+1)
- 1\leq i\lt H,1\leq j\leq W に対するマス (i,j) とマス (i+1,j)
のどれかに置くことができます。
ただし、同じマスに対して複数のドミノを置くことはできません。
ドミノの置き方に対して、置き方のスコアをドミノが置かれていないマスに書かれた整数すべてのビットごとの排他的論理和として定めます。
ドミノの置き方のスコアとしてありうる最大値を求めてください。
ビットごとの排他的論理和とは
非負整数 A, B のビットごとの排他的論理和 A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。
制約
- 1\leq H
- 1\leq W
- HW\leq20
- 0\leq A _ {i,j}\lt 2 ^ {60}\ (1\leq i\leq H,1\leq j\leq W)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W
A _ {1,1} A _ {1,2} \ldots A _ {1,W}
A _ {2,1} A _ {2,2} \ldots A _ {2,W}
\vdots
A _ {H,1} A _ {H,2} \ldots A _ {H,W}
出力
答えを出力せよ。
入力例 1
3 4 1 2 3 8 4 0 7 10 5 2 4 2
出力例 1
15
与えられたマス目は以下のようになります。
例えば、次のようにドミノを置くことでスコアを 15 とすることができます。
スコアを 16 以上にすることはできないため、15 を出力してください。
入力例 2
1 11 1 2 4 8 16 32 64 128 256 512 1024
出力例 2
2047
ドミノを 1 枚も置かないこともできます。
入力例 3
4 5 74832 16944 58683 32965 97236 52995 43262 51959 40883 58715 13846 24919 65627 11492 63264 29966 98452 75577 40415 77202
出力例 3
131067
Score : 425 points
Problem Statement
There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top (1\leq i\leq H) and the j-th column from the left (1\leq j\leq W).
Cell (i,j)\ (1\leq i\leq H,1\leq j\leq W) has a non-negative integer A_{i,j} written on it.
Let us place zero or more dominoes on the grid. A domino covers two adjacent cells, namely one of the following pairs:
- cells (i,j) and (i,j+1) for 1\leq i\leq H,1\leq j\lt W;
- cells (i,j) and (i+1,j) for 1\leq i\lt H,1\leq j\leq W.
No cell may be covered by more than one domino.
For a placement of dominoes, define its score as the bitwise XOR of all integers written in cells not covered by any domino.
Find the maximum possible score.
What is bitwise XOR?
For non-negative integers A and B, their bitwise XOR A \oplus B is defined as follows:
- In binary, the 2^k bit (k \ge 0) of A \oplus B is 1 if exactly one of A and B has 1 in that bit, and 0 otherwise.
For k non-negative integers p_1, p_2, p_3, \dots, p_k, their bitwise XOR is (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), which can be proved to be independent of the order of the operands.
Constraints
- 1 \le H
- 1 \le W
- HW \le 20
- 0 \le A_{i,j} < 2^{60} (1 \le i \le H,\ 1 \le j \le W)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
H W
A _ {1,1} A _ {1,2} \ldots A _ {1,W}
A _ {2,1} A _ {2,2} \ldots A _ {2,W}
\vdots
A _ {H,1} A _ {H,2} \ldots A _ {H,W}
Output
Output the answer.
Sample Input 1
3 4 1 2 3 8 4 0 7 10 5 2 4 2
Sample Output 1
15
The grid is as follows:
For example, the placement below yields a score of 15.
No placement achieves a score of 16 or higher, so output 15.
Sample Input 2
1 11 1 2 4 8 16 32 64 128 256 512 1024
Sample Output 2
2047
You may also choose to place no dominoes.
Sample Input 3
4 5 74832 16944 58683 32965 97236 52995 43262 51959 40883 58715 13846 24919 65627 11492 63264 29966 98452 75577 40415 77202
Sample Output 3
131067
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 425 点
問題文
N 頂点 M 辺の有向グラフが与えられます。 i 番目 (1\leq i\leq M) の辺は頂点 u _ i から頂点 v _ i への有向辺です。
はじめ、あなたは頂点 1 におり、以下の操作を繰り返して頂点 N にたどり着きたいです。
- 次の操作のうちのいずれかを行う。
- 今いる頂点から辺をたどって移動する。コストが 1 かかる。より厳密には、今いる頂点を v として、v から u への有向辺が存在するような u を 1 つ選び、頂点 u へ移動する。
- すべての辺の向きを反転する。コストが X かかる。より厳密には、この操作の直前に v から u への有向辺が存在しているとき、かつそのときに限り、この操作の直後に u から v への有向辺が存在する。
与えられるグラフにおいて、上の操作を繰り返して頂点 1 から頂点 N にたどり着くことができることが保証されます。
頂点 N にたどりつくまでにかかるコストの総和の最小値を求めてください。
制約
- 2\leq N\leq2\times10 ^ 5
- 1\leq M\leq2\times10 ^ 5
- 1\leq X\leq10 ^ 9
- 1\leq u _ i\leq N\ (1\leq i\leq M)
- 1\leq v _ i\leq N\ (1\leq i\leq M)
- 与えられるグラフにおいて、上記の操作を繰り返して頂点 1 から頂点 N にたどり着くことができる。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M X u _ 1 v _ 1 u _ 2 v _ 2 \vdots u _ M v _ M
出力
頂点 N にたどりつくまでにかかるコストの総和の最小値を出力せよ。
入力例 1
5 6 5 1 2 2 4 3 1 3 5 4 3 5 2
出力例 1
4
与えられたグラフは以下のようになります。
次のように操作を行うことで、コストの総和を 4 として頂点 5 にたどり着くことができます。
- コストを 1 かけて頂点 2 に移動する。
- コストを 1 かけて頂点 4 に移動する。
- コストを 1 かけて頂点 3 に移動する。
- コストを 1 かけて頂点 5 に移動する。
コストの総和を 3 以下として頂点 5 にたどり着くことはできないため、4 を出力してください。
入力例 2
5 6 1 1 2 2 4 3 1 3 5 4 3 5 2
出力例 2
3
与えられたグラフは入出力例 1 と同じですが、辺を反転させるのにかかるコストが異なります。
次のように操作を行うことで、コストの総和を 3 として頂点 5 にたどり着くことができます。
- コストを 1 かけて頂点 2 に移動する。
- コストを 1 かけてすべての辺を反転させる。
- コストを 1 かけて頂点 5 に移動する。
コストの総和を 2 以下として頂点 5 にたどり着くことはできないため、3 を出力してください。
入力例 3
8 7 613566756 2 1 2 3 4 3 4 5 6 5 6 7 8 7
出力例 3
4294967299
答えが 32\operatorname{bit} 整数に収まらない場合があることに注意してください。
入力例 4
20 13 5 1 3 14 18 18 17 12 19 3 5 4 6 13 9 8 5 14 2 20 18 8 14 4 9 14 8
出力例 4
21
Score : 425 points
Problem Statement
You are given a directed graph with N vertices and M edges. The i-th edge (1 \leq i \leq M) is a directed edge from vertex u _ i to vertex v _ i.
Initially, you are at vertex 1. You want to repeat the following operations until you reach vertex N:
- Perform one of the two operations below:
- Move along a directed edge from your current vertex. This incurs a cost of 1. More precisely, if you are at vertex v, choose a vertex u such that there is a directed edge from v to u, and move to vertex u.
- Reverse the direction of all edges. This incurs a cost of X. More precisely, if and only if there was a directed edge from v to u immediately before this operation, there is a directed edge from u to v immediately after this operation.
It is guaranteed that, for the given graph, you can reach vertex N from vertex 1 by repeating these operations.
Find the minimum total cost required to reach vertex N.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq X \leq 10^9
- 1 \leq u _ i \leq N \ (1 \leq i \leq M)
- 1 \leq v _ i \leq N \ (1 \leq i \leq M)
- For the given graph, it is guaranteed that you can reach vertex N from vertex 1 by the operations described.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M X u _ 1 v _ 1 u _ 2 v _ 2 \vdots u _ M v _ M
Output
Print the minimum total cost required to reach vertex N.
Sample Input 1
5 6 5 1 2 2 4 3 1 3 5 4 3 5 2
Sample Output 1
4
The given graph looks like this:
You can reach vertex 5 with a total cost of 4 by doing the following:
- Move to vertex 2 at a cost of 1.
- Move to vertex 4 at a cost of 1.
- Move to vertex 3 at a cost of 1.
- Move to vertex 5 at a cost of 1.
It is impossible to reach vertex 5 with a total cost of 3 or less, so print 4.
Sample Input 2
5 6 1 1 2 2 4 3 1 3 5 4 3 5 2
Sample Output 2
3
The graph is the same as in Sample 1, but the cost to reverse edges is different.
You can reach vertex 5 with a total cost of 3 as follows:
- Move to vertex 2 at a cost of 1.
- Reverse all edges at a cost of 1.
- Move to vertex 5 at a cost of 1.
It is impossible to reach vertex 5 with a total cost of 2 or less, so print 3.
Sample Input 3
8 7 613566756 2 1 2 3 4 3 4 5 6 5 6 7 8 7
Sample Output 3
4294967299
Note that the answer may exceed the 32-bit integer range.
Sample Input 4
20 13 5 1 3 14 18 18 17 12 19 3 5 4 6 13 9 8 5 14 2 20 18 8 14 4 9 14 8
Sample Output 4
21
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 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 を出力せよ。
入力例 1
4 3 1 2 2 1 3 4 2 4 5
出力例 1
22
以下の辺からなる全域木が最小全域木のひとつとなります。
- 頂点 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 を出力します。
入力例 2
6 2 1 2 10 4 6 10
出力例 2
-1
グラフは非連結です。
入力例 3
200000 4 1 200000 1000000000 1 200000 998244353 1 200000 999999999 1 200000 999999999
出力例 3
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 1
4 3 1 2 2 1 3 4 2 4 5
Sample Output 1
22
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 2
6 2 1 2 10 4 6 10
Sample Output 2
-1
The graph is disconnected.
Sample Input 3
200000 4 1 200000 1000000000 1 200000 998244353 1 200000 999999999 1 200000 999999999
Sample Output 3
199651870599998