Fox Rocks

View as PDF

Submit solution

Points: 40 (partial)
Time limit: 25.0s
Memory limit: 1G

Author:
Problem types
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
Facebook Hacker Cup 2015 Round 3

Mr. Fox sure loves his rocks! In fact, when he's not in a hurry, he often looks at the rocks lying around near him to decide where to wander in his forest.

Mr. Fox lives in a forest with N clearings, numbered from 0 to N-1, with P one-way trails initially running amongst them. The ith trail runs from clearing A_i to a different clearing B_i, and is littered with R_i rocks. No two clearings are connected by multiple trails running in the same direction, though they could be connected by 2 trails running in opposite directions. Additionally, an interesting property of this forest is that a trail from clearing a to clearing b may only exist if 0 \le \text{floor}(b/4) - \text{floor}(a/4) \le 1.

To entertain himself over a period of D days, Mr. Fox will cause one event to occur on each day. The ith event may be one of 3 types, determined by the value of E_i:

  1. Given 3 integers X_i, Y_i, and Z_i, Mr. Fox will create a new trail from clearing X_i to a different clearing Y_i, and drop Z_i rocks onto it. It's guaranteed that no trail from X_i to Y_i will exist at the start of the ith day, and that 0 \le \text{floor}(Y_i/4) - \text{floor}(X_i/4) \le 1 will hold.

  2. Given 2 distinct integers X_i and Y_i, Mr. Fox will completely destroy the trail from clearing X_i to clearing Y_i (which is guaranteed to exist at the start of the ith day). Note that, once such a trail is destroyed, a new trail from X_i to Y_i may be created in the future.

  3. Given 2 distinct integers X_i and Y_i, Mr. Fox will take a "random stroll" starting at clearing X_i, and would like to determine the probability that he'll visit clearing Y_i at least once during it.

    A "random stroll" consists of repeating the following process potentially infinitely: If Mr. Fox is currently in some clearing c, and there are no outgoing trails from c, then the stroll ends immediately. Otherwise, he'll consider all of the rocks on all of the outgoing trails from c, choose one of these rocks uniformly at random, follow the trail on which that rock lies to its destination clearing (without removing any rocks), and repeat the process from his new clearing.

For each event of type 3, output the requested probability.

Input

Input begins with an integer T, the number of test cases. For each test case, there is first a line containing the space-separated integers N, P, and D.

Then, P lines follow, the ith of which contains the space-separated integers A_i, B_i, and R_i.

Then, D lines follow, the ith of which contains the space-separated integers E_i, X_i, and Y_i. If E_i = 1, this line additionally contains the integer Z_i.

Output

For the ith test case, print a line containing Case #i: followed by the computed probabilities for each stroll that Mr. Fox takes. These probabilities should be space-separated, and rounded to 6 decimal places.

Absolute errors of up to 10^{-5} will be ignored.

Constraints

1 \le T \le 42
1 \le N \le 50\,000
0 \le P \le 100\,000
1 \le D \le 20\,000
0 \le A_i, B_i, X_i, Y_i < N
1 \le E_i \le 3
1 \le R_i, Z_i \le 5

Explanation of Sample

In the first test case, Mr. Fox does multiple strolls from clearing 0 while looking out for clearing 3.
His first stroll has probability 1 as he must always end up at clearing 3.
His second stroll has probability 1/2 as there's a 50% chance he gets stuck in clearing 4.
His third stroll has probability 2/3 as he now only goes to clearing 4 1/3 of the time.
His fourth stroll has probability 1/3 as he gets stuck in clearing 4 1/3 of the time, and in clearing 1 1/3 of the time.

Sample Input

5
8 0 10
1 0 1 1
1 1 2 1
1 2 3 1
3 0 3
1 0 4 1
3 0 3
1 0 3 1
3 0 3
2 1 2
3 0 3
4 4 10
0 1 1
1 0 1
1 2 1
0 3 1
3 0 2
2 0 1
1 0 1 2
3 0 2
2 0 1
1 0 1 3
3 0 2
2 0 1
1 0 1 4
3 0 2
8 7 5
0 1 1
1 2 1
2 3 1
0 4 1
1 5 1
2 6 1
3 7 1
3 0 5
3 0 7
1 3 0 1
3 0 5
3 0 7
8 4 10
4 5 1
5 6 1
6 7 1
7 4 1
1 0 4 1
1 0 1 4
3 0 7
1 1 6 1
3 0 7
1 1 2 1
1 2 3 1
3 0 7
1 2 0 1
3 0 7
12 5 7
0 4 1
4 8 1
0 1 1
1 2 1
2 3 1
3 0 8
1 1 4 1
3 0 8
1 2 4 1
3 0 8
1 3 4 1
3 0 8

Sample Output

Case #1: 1.000000 0.500000 0.666667 0.333333
Case #2: 0.333333 0.500000 0.600000 0.666667
Case #3: 0.250000 0.125000 0.266667 0.066667
Case #4: 0.200000 1.000000 0.600000 0.750000
Case #5: 0.500000 0.750000 0.875000 1.000000

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 3.0 Unported License.


Comments

There are no comments at the moment.