Mock CCC '18 Contest 1 S4 - A Graph Problem

Points: 12 (partial)

Time limit: 4.5s

Memory limit: 1G

Problem type

You are given four sequences $a$ ~a~, $b$ ~b~, $c$ ~c~, and $d$ ~d~, each consisting of exactly $M$ ~M~ positive integers.

Let graph $g(k)$ ~g(k)~ be the graph consisting of vertices labeled from $1$ ~1~ to $N$ ~N~ where there is a directed edge from vertex $u$ ~u~ to vertex $v$ ~v~ if and only if there exists some index $i$ ~i~ such that $a_i = u$ ~a_i = u~, $b_i = v$ ~b_i = v~, and $c_i \le k \le d_i$ ~c_i \le k \le d_i~.

Define $f(s, t, k)$ ~f(s, t, k)~ to be $1$ ~1~ if there is a path from vertex $s$ ~s~ to vertex $t$ ~t~ in $g(k)$ ~g(k)~, and $0$ ~0~ otherwise.

Given $S$ ~S~, $T$ ~T~, and $K$ ~K~, compute $\sum_{k=1}^K f(S, T, k)$ ~\sum_{k=1}^K f(S, T, k)~: the sum of $f(S, T, k)$ ~f(S, T, k)~ as $k$ ~k~ ranges over all positive integers from $1$ ~1~ to $K$ ~K~.

Constraints

$2 \le N \le 1\,000$ ~2 \le N \le 1\,000~

$1 \le M \le 5\,000$ ~1 \le M \le 5\,000~

$1 \le K \le 10^9$ ~1 \le K \le 10^9~

$1 \le S, T \le N, S \ne T$ ~1 \le S, T \le N, S \ne T~

$1 \le a_i, b_i \le N, a_i \ne b_i$ ~1 \le a_i, b_i \le N, a_i \ne b_i~

$1 \le c_i \le d_i \le K$ ~1 \le c_i \le d_i \le K~

For any pair $(x, y)$ ~(x, y)~ with $x \ne y$ ~x \ne y~, there is at most one index $j$ ~j~ such that $a_j = x$ ~a_j = x~ and $b_j = y$ ~b_j = y~.

Input Specification

The first line contains three space-separated integers $N$ ~N~, $M$ ~M~, and $K$ ~K~.

The second line contains two space-separated integers $S$ ~S~ and $T$ ~T~.

The next $M$ ~M~ lines each contain four space-separated integers. Specifically, line $i$ ~i~ of the input contains $a_{i-2}$ ~a_{i-2}~, $b_{i-2}$ ~b_{i-2}~, $c_{i-2}$ ~c_{i-2}~, and $d_{i-2}$ ~d_{i-2}~ in order for $3 \le i \le M+2$ ~3 \le i \le M+2~.

Output Specification

Print, on a single line,

$\displaystyle \sum_{k=1}^K f(S, T, k)$

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Comments

0

insect commented on Feb. 6, 2018, 2:21 a.m.

Can someone help find the bug in my program?

0

aeternalis1 commented on Feb. 6, 2018, 3:01 a.m.

Haven't exactly found the bug, but I changed the dfs to a bfs and got 14/15 instead. Still failed the last case, but it's something. I'll edit if I find something else.

1

insect commented on Feb. 6, 2018, 3:12 a.m.

That's weird. shouldn't dfs work just as well as bfs for testing connectivity?

3

aeternalis1 commented on Feb. 6, 2018, 3:32 a.m.

Ok, I should've noticed this earlier, but you need to reread the problem statement. Your code AC's upon removal of one line.

0

insect commented on Feb. 6, 2018, 3:37 a.m.

lol it's a directed graph. Thanks!