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