fork(1) download
copy 
  1. def parse(inFile):
  2.     [P, W] = inFile.getInts()
  3.     wormholes = [[int(num) for num in word.split(",")] for word in inFile.getWords()]
  4.     return (P,wormholes)
  5.  
  6. class Queue:
  7.     def __init__(self, x):
  8.         self.q = x
  9.         self.qat = 0
  10.         self.qlen = len(x)
  11.  
  12.     def pop(self):
  13.         self.qat += 1
  14.         return self.q[self.qat - 1]
  15.  
  16.     def elements(self):
  17.         while (not self.empty()):
  18.             yield self.pop()
  19.  
  20.     def push(self, x):
  21.         self.q.append(x)
  22.         self.qlen += 1
  23.  
  24.     def empty(self):
  25.         return self.qat == self.qlen
  26.  
  27. def solve((numPlanets, wormholes)):
  28.     print "There are %d planets." % numPlanets
  29.     nbs = [[] for i in xrange(numPlanets)]
  30.     adj = [[False for i in xrange(numPlanets)] for j in xrange(numPlanets)]
  31.     for i in xrange(len(wormholes)):
  32.         [p0,p1] = wormholes[i]
  33.         adj[p0][p1] = True
  34.         adj[p1][p0] = True
  35.         nbs[p0].append([p1,i])
  36.         nbs[p1].append([p0,i])
  37.     d0 = [numPlanets+1] * numPlanets
  38.     d0[0] = 0
  39.     q = Queue([0])
  40.     while (not (q.empty())):
  41.         qi = q.pop()
  42.         for nb in [z[0] for z in nbs[qi]]:
  43.             if (d0[nb] > d0[qi] + 1):
  44.                 d0[nb] = d0[qi] + 1
  45.                 q.push(nb)
  46.     d1 = [numPlanets+1] * numPlanets
  47.     d1[1] = 0
  48.     q = Queue([1])
  49.     while (not (q.empty())):
  50.         qi = q.pop()
  51.         for nb in [z[0] for z in nbs[qi]]:
  52.             if (d1[nb] > d1[qi] + 1):
  53.                 d1[nb] = d1[qi] + 1
  54.                 q.push(nb)
  55.  
  56.     threats = [[-1,-1,-1] for w in wormholes]
  57.     n0 = len(nbs[0])
  58.     q = Queue([])
  59.     for i in nbs[0]:
  60.         [j,w] = i
  61.         if d1[j] == d1[0] - 1:
  62.             threats[w] = [j,0,n0+len([k for k in nbs[j] if not adj[0][k[0]]])]
  63.             q.push(w)
  64.     rec = 0
  65.     if d0[1] == 1:
  66.         rec = n0 + 1
  67.     for qi in q.elements():
  68.         [j,i,t] = threats[qi]
  69.         for p in nbs[j]:
  70.             [dest,num] = p
  71.             if (dest == 1):
  72.                 rec = max(rec, t)
  73.             if (d0[dest] == d0[j] + 1) and (d1[dest] == d1[j] - 1):
  74.                 if threats[num][0] == -1:
  75.                     q.push(num)
  76.                 threats[num] = max(threats[num], [dest,j,t+len([k for k in nbs[dest] if not (adj[i][k[0]] or adj[j][k[0]])])])
  77.     return " ".join([str(d0[1] - 1),str(rec-d0[1])])
  78.  
  79. if __name__ == "__main__":
  80.     from GCJ import GCJ
  81.     GCJ(parse, solve, "/Users/lpebody/gcj/2011_round2/", "d").run()
  82.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:1: error: ‘def’ does not name a type
stdout
copy 
Standard output is empty
https://ideone.com/pGSXO
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
secret

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!