The Ultimate Game
All submissions for this problem are available.
Naresh and Neel got bored of playing all the usual games. They want to play something new. Chef introduced them to a new game called 'Ultimate'. The rule of the game are as follows:
This game is played on an undirected graph with all edges of equal value W.Graph is such that all the path from a vertex to itself are of even length. Naresh and Neel will play this game Q time. In each game they will be given U,V and W representing the source node, destination node and value of all the edges respectively. They will randomly select a path from U to V with equal probability. Both the players will play alternatively with Naresh playing first. In each turn, they will select an edge with positive value on this path and reduce it's value by some positive integer such that after reduction, value of edge is never negative.Player who won't be able to make a move lose. For different path selected between U and V , answer can change. Naresh want to know the probability of his winning the game for each query.
Note: There may not be path between U and V. In that case Naresh will lose.
The first line of the input contains N,M and Q denoting number of vertices in graph, number of edges in graph and number of queries
Next M line will contain U V representing there is an edge between vertex U and V.
Next Q line will contain queries of form U V W represing the start node of path , end node of path and value of all the edges.
For each query , output in single line the probability of Naresh winning the game.
Your answer will be considered correct if it has at most 10-6 absolute or relative error.
- 1 ≤ N ≤ 105
- 1 ≤ Q ≤ 105
- 1 ≤ U ≤ N
- 1 ≤ V ≤ N
- 0 ≤ W ≤ 109
Input: 4 4 2 1 2 2 3 1 4 4 3 1 3 2 2 3 5 Output: 0.000000 1.000000
Example case 1. In query 1, there are two path possible from 1 to 3 (1-2-3 and 1-4-3).Both are selected with equal probability 0.5. In both the cases Neel will imitates Naresh action and win the game.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions