Mock CCC '18 Contest 1 S4 - A Graph Problem

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 4.5s
Memory limit: 1G

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

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

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

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


2 \le N \le 1000

1 \le M \le 5000

1 \le K \le 10^9

1 \le S, T \le N, S \neq T

1 \le a_i, b_i \le N, a_i \neq b_i

1 \le c_i \le d_i \le K

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

Input Specification

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

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

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

Output Specification

Print, on a single line, \displaystyle\sum_{k=1}^K f(S, T, k).

Sample Input

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

Sample Output


Sample Input

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

Sample Output



  • 0
    insect  commented on Feb. 5, 2018, 9:21 p.m.

    Can someone help find the bug in my program?

    • 0
      aeternalis1  commented on Feb. 5, 2018, 10:01 p.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.

      • 0
        insect  commented on Feb. 5, 2018, 10:12 p.m.

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

        • 3
          aeternalis1  commented on Feb. 5, 2018, 10:32 p.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. 5, 2018, 10:37 p.m.

            lol it's a directed graph. Thanks!