問題一覧 > 通常問題

No.2288 Somen Sliders

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

問題文

0,1,⋯ ,N,N+10, 1, \cdots, N, N + 1 の N+2N + 2 頂点をもつ有向グラフ上の、端点以外頂点素な 0(N+1)0(N+1) パス集合 P={P1,⋯ ,PX},Q={Q1,⋯ ,QY}\mathcal{P} = \{P_1, \cdots, P_X\}, \mathcal{Q} = \{Q_1, \cdots, Q_Y\} が与えられます。1≤i≤X1 \le i \le X に対して、PiP_i に含まれる辺の数は KiK_i 本で、jj 番目の頂点（00 番目の頂点から始まるとします）は ui,ju_{i, j} です。また、1≤i≤Y1 \le i \le Y に対して、QiQ_i に含まれる辺の数は LiL_i 本で、jj 番目の頂点（00 番目の頂点から始まるとします）は vi,jv_{i, j} です。ここで、P\mathcal{P} のパスと Q\mathcal{Q} のパスは共通の辺をもたないものとします。ただし、P\mathcal{P} のパスと Q\mathcal{Q} のパスの間に平行辺が存在することはあり得ます（すなわち、ある 22 頂点 u,vu, v に対して、uu から vv への辺が P\mathcal{P} と Q\mathcal{Q} のどちらにも含まれていることはあり得ますが、これらは別の辺として扱います）。更に、P,Q\mathcal{P}, \mathcal{Q} のすべてのパスの長さは 22 以上であるものとします。

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

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

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

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

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

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

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

入力

N X YN \ X \ Y
K1K_1
u1,0 u1,1 ⋯ u1,K1u_{1,0} \ u_{1,1} \ \cdots \ u_{1, K_1}
⋮\vdots
KXK_X
uX,0 uX,1 ⋯ uX,KXu_{X,0} \ u_{X,1} \ \cdots \ u_{X, K_X}
L1L_1
v1,0 v1,1 ⋯ v1,L1v_{1,0} \ v_{1,1} \ \cdots \ v_{1, L_1}
⋮\vdots
LYL_Y
vY,0 vY,1 ⋯ vY,LYv_{Y,0} \ v_{Y,1} \ \cdots \ v_{Y, L_Y}
  • 入力される値はすべて整数
  • 1≤N≤1051 \le N \le 10^5
  • 1≤X,Y≤N1 \le X, Y \le N
  • 2≤Ki≤N+12 \le K_i \le N + 1
  • ui,0=0u_{i,0} = 0 かつ ui,Ki=N+1u_{i,K_i} = N + 1
  • 1≤j<Ki1 \le j < K_i に対して、1≤ui,j≤N1 \le u_{i,j} \le N
  • 1≤j<Ki,1≤j′<Ki′1 \le j < K_i, 1 \le j' < K_{i'} に対して、i≠i′i \neq i' または j≠j′j \neq j' ならば ui,j≠ui′,j′u_{i,j} \neq u_{i', j'}
  • 2≤Li≤N+12 \le L_i \le N + 1
  • vi,0=0v_{i,0} = 0 かつ vi,Li=N+1v_{i,L_i} = N + 1
  • 1≤j<Li1 \le j < L_i に対して、1≤vi,j≤N1 \le v_{i,j} \le N
  • 1≤j<Li,1≤j′<Li′1 \le j < L_i, 1 \le j' < L_{i'} に対して、i≠i′i \neq i' または j≠j′j \neq j' ならば vi,j≠vi′,j′v_{i,j} \neq v_{i', j'}

出力

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

条件を満たすパス集合としては R1={0→P3→P1→Q5,0→P2→P4→Q5},R2={0→P3→Q4→Q5,0→P2→Q1→Q5}\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\} があり、 ∣P∩R1∣=4,∣P∩R2∣=2|\mathcal{P} \cap \mathcal{R}_1| = 4, |\mathcal{P} \cap \mathcal{R}_2| = 2 なので答えは 44 となります。

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

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

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

条件を満たすパス集合には {0→P1→P2→P3→P4→Q5}\{0→_\mathcal{P}1→_\mathcal{P}2→_\mathcal{P}3→_\mathcal{P}4→_\mathcal{Q}5\} や {0→P1→P2→Q3→Q4→Q5}\{0→_\mathcal{P}1→_\mathcal{P}2→_\mathcal{Q}3→_\mathcal{Q}4→_\mathcal{Q}5\} などがあります。{0→P1→P2→P3→P4→P5}\{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もしくは右上の雲マークをクリックしてアカウントを作成してください。