問題一覧 > 通常問題

No.1744 Selfish Spies 1 (à la Princess' Perfectionism)

レベル : / AI推定難易度 : 2050 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 34
作問者 : ygussany / テスター : opt
お気に入りにしたユーザー ProblemId : 6681 / 自分の提出
問題文最終更新日: 2021-12-04 01:46:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Y.Y. さんの単発問題コンテスト 2 (順位表) の他の問題:

Problem Statement

This problem is an homage to Problem F of the ICPC 2021 Asia Yokohama Regional Domestic Contest (Japanese, English, Judge).

We are going to assign $M$ missions to $N$ spies. Here,

  • each spy is assigned at most $1$ mission, and
  • each mission is assigned to at most $1$ spy.
Also, whether each mission can be carried out is determined by the abilities of the spies.

S.S., the boss of the spies, wants to assign as many missions as possible to the spies and have them carried out. However, there may appear selfish spies who refuse a particular mission among those they are able to carry out.

There are $L$ pairs of a spy and a mission that spy can carry out, and all of them are given. For S.S., determine, for each pair, whether it is possible not to choose it under the condition that the total number of assigned missions is the maximum (achievable when no one is selfish).

Input

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

  • $1 \le N, M \le 500$
  • $1 \le L \le 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$ or $T_i \neq T_j \ \ (1 \le i < j \le L)$
  • The spies are numbered $1, 2, \dots, N$.
  • The missions are numbered $1, 2, \dots, M$.
  • Each pair $(S_i, T_i)$ means that spy $S_i$ can carry out mission $T_i$.
  • All input values are integers.

Output

Output $L$ lines.

On the $i$-th line, print Yes if there exists an assignment with the maximum achievable number of missions that does not assign mission $T_i$ to spy $S_i$, and print No otherwise.

Sample

Sample 1
Input
2 2 3
1 1
1 2
2 2
Output
No
Yes
No

Choosing pairs $1, 3$, that is, assigning mission $1$ to spy $1$ and mission $2$ to spy $2$, gives the maximum, and this is the only way to do so. Therefore, pairs $1, 3$ must be chosen, so print No on lines $1, 3$; pair $2$ need not be chosen, so print Yes on line $2$.

Sample 2
Input
2 2 4
1 1
1 2
2 1
2 2
Output
Yes
Yes
Yes
Yes

The maximum assignment can be achieved by choosing either pairs $1, 4$ or pairs $2, 3$. Therefore, every pair can be left unchosen, so print Yes for all of them.

Sample 3
Input
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
Output
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes

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