fork(1) download
copy 
  1. import random
  2.  
  3. def AllPairsNonDecreasingPaths(E, n):
  4.     p = 1234567891                            #large prime ${\color{commentcolour} p > n^3 \log n}$
  5.     r = random.randint(0,p)                   #random number ${\color{commentcolour} r}$ in [0,p)
  6.     powr = [1]                                #Precompute powers of ${\color{commentcolour} r }$
  7.     for i in range(n):                        #powr[i] ${\color{commentcolour} \triangleq }$ ${\color{commentcolour} r^i }$ (mod p)
  8.         powr.append((powr[-1] * r) % p)
  9.  
  10.     N = 1<<(n-1).bit_length()                 #round n to next power of 2
  11.     tree = [ [0]*(2*N) for _ in range(n) ]
  12.     def update(v,node,val):
  13.         while node > 0:
  14.             tree[v][node] += val
  15.             node >>= 1
  16.  
  17.     #Functions for finding new paths and adding them
  18.     def FindNewPaths(a,b,node):
  19.         if tree[a][node] == tree[b][node]: return []
  20.         if node >= N:                         
  21.             u = node - N                      #leaf node
  22.             if path[u][a] is None: 
  23.                 return [(u,a,b)]
  24.             return [(u,b,a)]
  25.         return FindNewPaths(a,b,2*node) + FindNewPaths(a,b,2*node+1)
  26.     def AddNewPath(u, v, par):
  27.         path[u][v] = par
  28.         update(v,u+N,powr[u])
  29.  
  30.     #Main routine for finding all pairs non-decreasing paths
  31.     path = [ [None] * n for _ in range(n) ]
  32.     for i in range(n):
  33.         AddNewPath(i,i,i)
  34.     for (a,b) in E:
  35.         for (u,v,par) in FindNewPaths(a,b,1):
  36.             AddNewPath(u,v,par)
  37.  
  38.     return path
  39.  
  40. print(AllPairsNonDecreasingPaths([(1,2),(0,1)], 3))
  41.             #Returns [[0, 0, None], [1, 1, 1], [1, 2, 2]]
  42.  
  43. def RecoverPath(path,u,v):
  44.     if path[u][v] is None: return None
  45.     if u == v: return [u]
  46.     return RecoverPath(path, u, path[u][v]) + [ v ]
  47.  
  48. path = AllPairsNonDecreasingPaths([(1,2),(0,1)], 3)
  49. print(RecoverPath(path, 2, 0))  #Returns [2,1,0]
  50. print(RecoverPath(path, 0, 2))  #Returns None
Success #stdin #stdout 0.03s 65480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[[0, 0, None], [1, 1, 1], [1, 2, 2]]
[2, 1, 0]
None
https://ideone.com/S9RAhX
language:
Python (PyPy 2.7.13)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!