問題一覧 > 通常問題

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

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 21
作問者 : ygussany / テスター : opt
お気に入りにしたユーザー ProblemId : 6654 / 自分の提出
問題文最終更新日: 2021-12-04 01:48:28
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 Qualifier (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 be selfish spies who insist on a particular mission among those they can carry out.

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

Input

$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$ 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 assigns 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
Yes
No
Yes

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$ can be chosen, so print Yes on lines $1, 3$, and pair $2$ cannot be chosen, so print No on line $2$.

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

The maximum mission assignment can be achieved by choosing either pairs $1, 4$ or pairs $2, 3$. Therefore, every pair can be chosen, 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
Yes
No
No
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes

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