All Tracks Math Problem

Chip on Graph
Tag(s):

Basic Probability, Bipartite Graph, Disjoint Set, Math, Medium-Hard, Probablity

Problem
Editorial
Analytics

Given an undirected-weighted graph of \(N\) vertices, numbered from \(1\) to \(N\). Initially, there is no edge in the graph. There is a chip places on some vertex. At each second, the chip randomly moves to one of its neighbors with probability relative with the weight of that edges, if it has no neighbor, the chip won't move. For example, assume that the chip is on vertex \(1\) and there are three edges \((1, 2)\) weight \(1\)\((1, 3)\) weight \(2\) and \((1, 4)\) weight \(3\). Then the chip moves to vertex \(2\) with probability \(\frac{1}{1 + 2 + 3}\), vertex \(3\) with probability \(\frac{2}{1 + 2 + 3}\), vertex \(4\) with probability \(\frac{3}{1 + 2 + 3}\); at the next second. You are asked to process \(Q\) queries:

  • \(1\ u\ v\ w\): add an edge \((u, v)\) with weight \(w\), there is no multiple edge or self-loop in the graph at any moment.
  • \(2\ u\ v\): find the probability the chip is on vertex \(u\) after \(10^{10^{10^{10}}}\) seconds if at the beginning, we place the chip on vertex \(v\).

Input Format

The first line contains two integers \(N, Q\) denoting the number of vertices of the graph and the number of queries.

Each of \(Q\) following lines contains a query of two kinds as described above.

Output Format

For each query of the second type, assume \(x\) is the answer, you should print \(floor(x\times 10^9 + \frac{1}{2})\) (the largest integer doesn't exceed \(x\times 10^9 + \frac{1}{2}\)) in a line. (It is guaranteed that the output doesn't change if we change \(x\) by \(x + 10^{-18}\) or \(x - 10^{-18}\))

Constraints

  • \(1 \le N, Q \le 10^6\)
  • \(1 \le u, v \le n\)
  • \(1 \le w \le 10^4\)
SAMPLE INPUT
3 5
1 1 2 1
2 1 3
1 2 3 1
1 3 1 1
2 1 2

SAMPLE OUTPUT
0
333333333
Explanation

The actual answer for \(2\)nd query is \(0\).

The actual answer for \(5\)-th query is \(\frac{1}{3} + \epsilon\), where \(|\epsilon| < 10^{-100}\).

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

January Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?