No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
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.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
opt