시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 108 | 42 | 35 | 38.889% |
IOI 国は,N 個の都市からなる国である.これらの都市には 1, 2, . . . , N の番号がついている.JOI 教授 は,IOI 国の道路網が整備された過程について興味を持った.
JOI 教授が,IOI 国の歴史に関する資料を調べたところ,以下のことが分かった.
また,別の文献から,都市 Ai と都市 Bi の間の交通状況の改善計画は次のようなものであることが分 かった.
JOI 教授は,さらなる調査のため,実行されずに放棄された改善計画それぞれに対して,もしその改善 計画のみが追加で実行されていたら,その改善計画において何本の道路を舗装することになっていたかを 計算することにした.
IOI 国の交通状況の改善計画とその実行状況が与えられたとき,実行されずに放棄された改善計画それ ぞれに対して,もしその改善計画が実行されていたら,その改善計画において何本の道路を舗装すること になっていたかを計算するプログラムを作成せよ.
標準入力から以下のデータを読み込め.
標準出力に,実行されずに放棄された改善計画それぞれに対し,もしその改善計画が実行されていたら, その改善計画において舗装することになる道路の本数を 1 行で出力せよ.ただし,その改善計画を実行す ると新しい道路が建設される場合は,-1 を出力せよ.
追加の制限はない.
3 7 1 1 2 2 2 1 2 2 3 1 2 1 2 1 2 1 2 3 2 1 3
1 -1 0 1
この入力例の場合, IOI 国の交通状況の改善計画は以下のように実行されたことになる.
6 8 1 1 3 1 6 1 1 2 5 2 3 6 1 3 6 1 4 1 2 4 3 2 2 5
2 1 1
7 11 1 5 1 1 6 2 1 1 3 1 3 5 1 5 7 1 4 5 1 4 1 2 1 3 2 3 7 2 4 3 2 5 6
0 1 0 -1