Mock CCC '18 Contest 1 S4 - A Graph Problem

View as PDF

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

Problem type

You are given four sequences , , , and , each consisting of exactly positive integers.

Let graph be the graph consisting of vertices labeled from to where there is a directed edge from vertex to vertex if and only if there exists some index such that , , and .

Define to be if there is a path from vertex to vertex in , and otherwise.

Given , , and , compute : the sum of as ranges over all positive integers from to .

Constraints

For any pair with , there is at most one index such that and .

Input Specification

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

The second line contains two space-separated integers and .

The next lines each contain four space-separated integers. Specifically, line of the input contains , , , and in order for .

Output Specification

Print, on a single line,

Sample Input 1

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 1

5

Sample Input 2

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 2

5

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

Can someone help find the bug in my program?

• 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.

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

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

• 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.

• commented on Feb. 5, 2018, 10:37 p.m.

lol it's a directed graph. Thanks!