|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||256 MB||22||11||11||50.000%|
The Fair Inc. administration decided to promote the best employees and limited the number of promotions to a fixed interval [A, B]. The directors compared the employees’ performance and their evaluations resulted in a consistent precedence relation among employees, which has to be respected by promotions. This means that, for every pair of employees x and y, if x outperformed y, then y may be promoted only if x is promoted.
In order to understand whether the data collected so far is enough for ensuring fairness, the executive chairman wants to know:
Consider the example depicted in the figure. There are seven employees and eight precedence rules. An arrow from an employee x to an employee y means that x outperformed y. The number of promotions is limited to the interval [3, 4]. Therefore:
In this case, two employees (Anne and Greg) will certainly be promoted. Notice that, with the current information, Bob and Eve may or may not win a promotion.
So, with four promotions, four employees (Anne, Bob, Eve and Greg) will certainly be promoted and three employees (Cora, Dan and Fred) have no possibility of being promoted.
Write a program that, given the interval of the number of promotions, the set of employees and the precedence relation among them, computes, for each of the interval endpoints, the number of employees that will certainly be promoted, and the number of employees that have no possibility of being promoted.
The precedence relation is consistent in the sense that, if an employee x outperformed an employee y, y did not outperform (directly or indirectly) x.
The first line of the input has four space separated integers: A, B, E, and P. A and B are the interval endpoints, E is the number of employees and P is the number of precedence rules. Employees are identified by integers, ranging from 0 to E − 1. Each of the following P lines contains two distinct space separated integers, x and y, which indicate that employee x outperformed employee y.
The output consists of three lines. The first line contains the number of employees that will certainly be promoted if there are A promotions. The second line contains the number of employees that will certainly be promoted if there are B promotions. The third line contains the number of employees that have no possibility of being promoted (even if there are B promotions).
3 4 7 8 0 4 1 2 1 5 5 2 6 4 0 1 2 3 4 5
2 4 3