問題一覧 > 通常問題

No.2160 みたりのDominator

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 : NachiaNachia / テスター : hotman78hotman78
5 ProblemId : 8234 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-10 16:29:30

問題文

頂点数 $N_1+N_2+N_3+2$ $(=N)$ の無向グラフ $G$ があります。 ここで $N_1,N_2,N_3$ はそれぞれ非負整数で、その値は与えられます。 頂点には頂点 $1$ , 頂点 $2$ , 頂点 $3$ , $\ldots$ というように番号が振られています。 $G$ には多重辺が含まれているかもしれませんが、自己ループは含まれません。

$s=N_1+N_2+N_3+1$ , $t=N_1+N_2+N_3+2$ とします。 グラフ $G$ には辺を共有しない次の $3$ 本のパス( main paths )が含まれています。

  • 頂点 $s$ , 頂点 $1$ , 頂点 $2$ , $\ldots$ , 頂点 $N_1$ , 頂点 $t$
  • 頂点 $s$ , 頂点 $N_1+1$ , 頂点 $N_1+2$ , $\ldots$ , 頂点 $N_1+N_2$ , 頂点 $t$
  • 頂点 $s$ , 頂点 $N_1+N_2+1$ , 頂点 $N_1+N_2+2$ , $\ldots$ , 頂点 $N_1+N_2+N_3$ , 頂点 $t$

$G$ の辺のうち main paths に含まれないものを augmenting edge と呼びます。 augmenting edge の個数を $M$ とします。 各 augmenting edge について、その辺が直接結ぶ $2$ 頂点の番号 $U_i$ , $V_i$ ( $1\leq i \leq M$ )が与えられます。

さて、グラフ $G$ の相異なる $3$ 辺 $x$ , $y$ , $z$ の組であって、 $G$ から辺 $x$ , $y$ , $z$ を除くと $2$ 頂点 $s$ , $t$ が非連結になるようなものはいくつあるでしょうか。 なお、 $x$ , $y$ , $z$ を並べ替えて得られる組は同一視して数えます。

制約

入力は次の制約を満たします。

  • $0 \leq N_i$ $(i=1,2,3)$
  • $N_1+N_2+N_3 \leq 300000$
  • $0 \leq M \leq 300000$
  • $1 \leq U_i \leq N$
  • $1 \leq V_i \leq N$
  • $U_i \neq V_i$
  • 値はすべて整数

$2$ 頂点 $s$ , $t$ は常に存在すること、 main paths によって $G$ には少なくとも $3$ つの辺が存在することに注意してください。

入力

入力は次の形式で与えられます。

$N_1$ $N_2$ $N_3$ $M$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

出力

問題の答えを $1$ 行に出力してください。

サンプル

サンプル1
入力
1 1 1 1
1 2
出力
4

サンプル2
入力
100000 100000 100000 0
出力
1000030000300001

辺は全部で $300003$ 本ありますが、そのどこからでも切れます。

サンプル3
入力
2 2 2 3
1 4
3 6
5 2
出力
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。