問題一覧 > 通常問題

No.1745 Selfish Spies 2 (à la Princess' Perfectionism)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : 👑 ygussanyygussany / テスター : optopt
1 ProblemId : 6654 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-04 01:48:28

問題文

この問題は ICPC 2021 アジア地区横浜大会国内予選 F 問題(日本語英語ジャッジ)のオマージュです.

$N$ 人のスパイ達に $M$ 個の任務を割り当てようとしています. ただし,

  • 各スパイは高々 $1$ 個の任務を割り当てられ,
  • 各任務は高々 $1$ 人のスパイに割り当てられます.
また,スパイの能力によって各任務が遂行可能かどうかが決まっています.

スパイ達のボスである S.S. 君は,できる限り多くの任務をスパイに割り当てて遂行させたいと考えています. しかし,自身が遂行可能な任務のうち特定のものに固執する我儘なスパイが出てくるかもしれません.

スパイと遂行可能な任務の組は $L$ 個あり,そのすべてが与えられます. S.S. 君のために,全体の任務割り当て数を(我儘が出ない場合に達成可能な)最大にするという条件の下で,各組を選ぶことが可能かどうかを判定してあげてください.

入力

$N\ \ M\ \ L$
$S_1\ \ T_1$
$S_2\ \ T_2$
  $\vdots$
$S_L\ \ T_L$

  • $1 \le N, M \le 10^5$
  • $1 \le L \le 2 \times 10^5$
  • $1 \le S_i \le N \ \ (1 \le i \le L)$
  • $1 \le T_i \le M \ \ (1 \le i \le L)$
  • $S_i \neq S_j$ または $T_i \neq T_j \ \ (1 \le i < j \le L)$
  • スパイには $1, 2, \dots, N$ の番号が付いている.
  • 任務には $1, 2, \dots, M$ の番号が付いている.
  • 各組 $(S_i, T_i)$ は「スパイ $S_i$ が任務 $T_i$ を遂行可能である」ことを表す.
  • 入力は全て整数である.

出力

$L$ 行に渡って出力してください.

$i$ 行目には,遂行可能な最大数の任務割り当てであって,スパイ $S_i$ に任務 $T_i$ を割り当てるようなものが存在するなら Yes を,存在しないなら No を出力してください.

サンプル

サンプル 1
入力
2 2 3
1 1
1 2
2 2
出力
Yes
No
Yes

組 $1, 3$ を選ぶ,すなわち,スパイ $1$ に任務 $1$ を割り当て,スパイ $2$ に任務 $2$ を割り当てるのが最大で,これが唯一の方法です. したがって,組 $1, 3$ は選ぶことが可能なので $1, 3$ 行目には Yes を出力し,組 $2$ は選ぶことが不可能なので $2$ 行目には No を出力します.

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

組 $1, 4$ を選ぶか,組 $2, 3$ を選ぶかのいずれかによって最大の任務割り当てが達成できます. したがって,どの組についても選ぶことが可能なので,すべて Yes を出力します.

サンプル 3
入力
7 8 15
7 8
5 5
2 2
1 6
1 8
5 8
2 6
6 7
5 6
2 5
4 6
1 3
7 7
4 7
6 5
出力
Yes
Yes
Yes
No
No
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes

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