問題一覧 > 通常問題

No.2288 Somen Sliders

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 8
作問者 : みここみここ / テスター : cureskolcureskol 👑 potato167potato167
3 ProblemId : 9172 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-28 21:20:13

問題文

$0, 1, \cdots, N, N + 1$ の $N + 2$ 頂点をもつ有向グラフ上の、端点以外頂点素な $0(N+1)$ パス集合 $\mathcal{P} = \{P_1, \cdots, P_X\}, \mathcal{Q} = \{Q_1, \cdots, Q_Y\}$ が与えられます。$1 \le i \le X$ に対して、$P_i$ に含まれる辺の数は $K_i$ 本で、$j$ 番目の頂点($0$ 番目の頂点から始まるとします)は $u_{i, j}$ です。また、$1 \le i \le Y$ に対して、$Q_i$ に含まれる辺の数は $L_i$ 本で、$j$ 番目の頂点($0$ 番目の頂点から始まるとします)は $v_{i, j}$ です。ここで、$\mathcal{P}$ のパスと $\mathcal{Q}$ のパスは共通の辺をもたないものとします。ただし、$\mathcal{P}$ のパスと $\mathcal{Q}$ のパスの間に平行辺が存在することはあり得ます(すなわち、ある $2$ 頂点 $u, v$ に対して、$u$ から $v$ への辺が $\mathcal{P}$ と $\mathcal{Q}$ のどちらにも含まれていることはあり得ますが、これらは別の辺として扱います)。更に、$\mathcal{P}, \mathcal{Q}$ のすべてのパスの長さは $2$ 以上であるものとします

これらの $\mathcal{P}, \mathcal{Q}$ から、あなたは以下を満たすパス集合 $\mathcal{R}$ を構成したいと思いました。

  • $\mathcal{R}$ は端点以外頂点素な $0(N+1)$ パス集合。
  • 各 $R \in \mathcal{R}$ に対して $R$ 上のある頂点 $u$ が存在し,$R$ の $u$ 以前の辺は $E(\mathcal{P})$ に含まれ,$u$ 以降の辺は $E(\mathcal{Q})$ に含まれる。
  • 各 $P \in \mathcal{P}$ に対して,$P$ の始辺は $E(\mathcal{R})$ に含まれる。
  • 各 $Q \in \mathcal{Q}$ に対して,$Q$ の終辺は $E(\mathcal{R})$ に含まれる。

ただし、パス集合 $\mathcal{X}$ に対して、$E(\mathcal{X})$ は $\mathcal{X}$ のどれかのパスに含まれる辺全体の集合とします。

このような $\mathcal{R}$ が存在するか判定し、存在するならば $|E(\mathcal{P}) \cap E(\mathcal{R})|$ が最大となるときの値を求めてください。

端点以外頂点素な $0(N+1)$ パス集合とは(クリックすると説明が出ます)

パス集合 $\mathcal{X}$ が以下を満たすとき,$\mathcal{X}$ は端点以外頂点素な $0(N+1)$ パス集合であるという。

  • すべての $P \in \mathcal{X}$ の始点が $0$ かつ終点が $N + 1$。
  • すべての $P \in \mathcal{X}$ が閉路をもたない。
  • すべての相異なる $P, Q \in \mathcal{X}$ が $0, N + 1$ 以外の共通頂点をもたない。

入力

$N \ X \ Y$
$K_1$
$u_{1,0} \ u_{1,1} \ \cdots \ u_{1, K_1}$
$\vdots$
$K_X$
$u_{X,0} \ u_{X,1} \ \cdots \ u_{X, K_X}$
$L_1$
$v_{1,0} \ v_{1,1} \ \cdots \ v_{1, L_1}$
$\vdots$
$L_Y$
$v_{Y,0} \ v_{Y,1} \ \cdots \ v_{Y, L_Y}$
  • 入力される値はすべて整数
  • $1 \le N \le 10^5$
  • $1 \le X, Y \le N$
  • $2 \le K_i \le N + 1$
  • $u_{i,0} = 0$ かつ $u_{i,K_i} = N + 1$
  • $1 \le j < K_i$ に対して、$1 \le u_{i,j} \le N$
  • $1 \le j < K_i, 1 \le j' < K_{i'}$ に対して、$i \neq i'$ または $j \neq j'$ ならば $u_{i,j} \neq u_{i', j'}$
  • $2 \le L_i \le N + 1$
  • $v_{i,0} = 0$ かつ $v_{i,L_i} = N + 1$
  • $1 \le j < L_i$ に対して、$1 \le v_{i,j} \le N$
  • $1 \le j < L_i, 1 \le j' < L_{i'}$ に対して、$i \neq i'$ または $j \neq j'$ ならば $v_{i,j} \neq v_{i', j'}$

出力

条件を満たすパス集合 $\mathcal{R}$ が存在するとき、$|E(\mathcal{P}) \cap E(\mathcal{R})|$ の最大値を出力してください。そうでないとき、$-1$ を出力してください。

サンプル

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

条件を満たすパス集合としては $\mathcal{R}_1 = \{0→_\mathcal{P}3→_\mathcal{P}1→_\mathcal{Q}5, 0→_\mathcal{P}2→_\mathcal{P}4→_\mathcal{Q}5\}, \mathcal{R}_2 = \{0→_\mathcal{P}3→_\mathcal{Q}4→_\mathcal{Q}5, 0→_\mathcal{P}2→_\mathcal{Q}1→_\mathcal{Q}5\}$ があり、 $|\mathcal{P} \cap \mathcal{R}_1| = 4, |\mathcal{P} \cap \mathcal{R}_2| = 2$ なので答えは $4$ となります。

サンプル2
入力
2 1 1
2
0 1 3
2
0 2 3
出力
2

条件を満たすパス集合は $\{0→_\mathcal{P}1→_\mathcal{P}3, 0→_\mathcal{Q}2→_\mathcal{Q}3\}$ となります。二つ目の条件における $u$ は $0$ または $N + 1$ でも構わないことに注意してください。

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

条件を満たすパス集合には $\{0→_\mathcal{P}1→_\mathcal{P}2→_\mathcal{P}3→_\mathcal{P}4→_\mathcal{Q}5\}$ や $\{0→_\mathcal{P}1→_\mathcal{P}2→_\mathcal{Q}3→_\mathcal{Q}4→_\mathcal{Q}5\}$ などがあります。$\{0→_\mathcal{P}1→_\mathcal{P}2→_\mathcal{P}3→_\mathcal{P}4→_\mathcal{P}5\}$ は条件を満たさないことに注意してください。

サンプル4
入力
19 3 3
4
0 1 2 3 20
8
0 4 5 6 7 8 9 10 20
4
0 11 12 13 20
6
0 14 3 15 8 16 20
5
0 17 2 9 18 20
4
0 19 12 7 20
出力
10

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