Submission #1330532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1330532		akshar_7	Senior Postmen (BOI14_postmen)	Pypy 3	55 / 100	1049 ms	236768 KiB

postmen

from sys import stdin
input = stdin.readline

def main():
  def euler(x):
    ans = []
    vis = [False]*m
    s = [x]
    while s:
      u = s[-1]
      while g[u] and vis[g[u][-1][1]]: g[u].pop()
      if g[u]:
        v,j = g[u].pop()
        vis[j] = True
        s.append(v)
      else:
        y = s.pop()
        ans.append(y)
        #idx.append(k)
    return ans
  
  #n = int(input())
  n,m = map(int, input().split())
  #a = [int(i) for i in input().split()]
  #b = [int(i) for i in input().split()]
  #c = [int(i) for i in input().split()]
  #c = [list(i) for i in input().split()]
  #b = [int(i) for i in input().split()]
  #s = input().strip()
  g = [[] for i in range(n+1)]
  for i in range(m):
    u,v = map(int, input().split())
    g[u].append((v,i))
    g[v].append((u,i))
  ans = euler(1)
  #print(ans)
  res = []
  onstk = [False]*(n+1)
  s = []
  for x in ans:
    if onstk[x]:
      b = [x]
      while s[-1] !=x:
        y = s.pop()
        onstk[y] = False
        b.append(y)
      res.append(b)
    else:
      onstk[x] = True
      s.append(x)
  for cyc in res: print(*cyc)

t = 1#int(input())
for __ in range(t):
  (main())

Compilation message (stdout)

Compiling 'postmen.py'...

=======
  adding: __main__.pyc (deflated 37%)

=======

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45