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} \leq k \leq 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 \leq N \leq 1 000$

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

$1 \le K \le 10^9$ $1 \leq K \leq 10^{9}$

$1 \le S, T \le N, S \ne T$ $1 \leq S, T \leq N, S \neq T$

$1 \le a_i, b_i \le N, a_i \ne b_i$ $1 \leq a_{i}, b_{i} \leq N, a_{i} \neq b_{i}$

$1 \le c_i \le d_i \le K$ $1 \leq c_{i} \leq d_{i} \leq K$

For any pair $(x, y)$ $(x, y)$ with $x \ne y$ $x \neq 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 \leq i \leq M + 2$ .

Output Specification

Print, on a single line,

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

Sample Input 1

Copy

Sample Output 1

Copy

Sample Input 2

Copy

Sample Output 2

Copy

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!