시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 93 | 35 | 31 | 56.364% |
You are in charge of the security for a large building, with n rooms and m doors between the rooms. The rooms and doors are conveniently numbered from 1 to n, and from 1 to m, respectively.
Door i opens from room ai to room bi, but not the other way around. Additionally, each door has a security code that can be represented as a range of numbers [ci, di].
There are k employees working in the building, each carrying a security badge with a unique, integer-valued badge ID between 1 and k. An employee is cleared to go through door i only when the badge ID x satisfies ci ≤ x ≤ di.
Your boss wants a quick check of the security of the building. Given s and t, how many employees can go from room s to room t?
The first line of input contains three space-separated integers n, m, and k (2 ≤ n ≤ 1,000; 1 ≤ m ≤ 5,000; 1 ≤ k ≤ 109).
The second line of input contains two space-separated integers s and t (1 ≤ s, t ≤ n; s ≠ t).
Each of the next m lines contains four space-separated integers ai, bi, ci, and di (1 ≤ ai, bi ≤ n; 1 ≤ ci ≤ di ≤ k; ai ≠ bi), describing door i.
For any given pair of rooms a, b there will be at most one door from a to b (but there may be both a door from a to b and a door from b to a).
Print, on a single line, the number of employees who can reach room t starting from room s.
4 5 10 3 2 1 2 4 7 3 1 1 6 3 4 7 10 2 4 3 5 4 2 8 9
5
4 5 9 1 4 1 2 3 5 1 3 6 7 1 4 2 3 2 4 4 6 3 4 7 9
5
ICPC > Regionals > North America > Pacific Northwest Regional > 2017 Pacific Northwest Region Programming Contest > Division 1 G번
ICPC > Regionals > North America > Pacific Northwest Regional > 2017 Pacific Northwest Region Programming Contest > Division 2 T번
ICPC > Regionals > North America > Southeast USA Regional > 2017 Southeast USA Regional Programming Contest > Division 1 H번