Problem p02585 (python)

Fixed submission:
n, k = map(int, input().split())
positions = [int(i) for i in input().split()]
scores = [int(i) for i in input().split()]
if max(scores) <= 0:
  print(max(scores))
else:
  positions = [0] + positions
  scores = [0] + scores
  max_point = -pow(10, 9)
  #print(max_point)
  for i in range(1, n + 1):
    s = []
    f_pos = positions[i]
    score = scores[f_pos]
    s.append(score)
    while f_pos != i:
      f_pos = positions[f_pos]
      score += scores[f_pos]
      s.append(score)
    loop = len(s)
    if loop >= k:
      point = max(s[:k])
    elif s[-1] <= 0:
      point = max(s)
    else:
      loop_c = k // loop
      r = k % loop
      point1 = s[-1] * loop_c
      if r != 0:
        point1 += max(s[:r])
      point2 = s[-1] * (loop_c - 1)
      point2 += max(0, max(s))
      point = max(point1, point2)
    max_point = max(max_point, point)
  print(max_point)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
positions = [int(i) for i in input().split()]
scores = [int(i) for i in input().split()]
if max(scores) <= 0:
  print(max(scores))
else:
  positions = [0] + positions
  scores = [0] + scores
  max_point = -pow(10, 9)
  #print(max_point)
  dic = {}
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    if f_pos not in dic:
      point_loop = 0
      loop = 0
      pos_set = set([f_pos])
      while True:
        f_pos = positions[f_pos]
        point_loop += scores[f_pos]
        #print('pos', f_pos)
        #print(point)
        loop += 1
        if f_pos in pos_set:
          for j in pos_set:
            dic[j] = [loop, point_loop]
          break
        pos_set.add(f_pos)
    else:
      loop, point_loop = dic[f_pos]
    #print(loop, point)
    loop_c = k // loop
    r = k % loop
    if loop_c ==　0 or point_loop <= 0:
      if point_loop <= 0:
        if loop_c > 0:
          r = loop
      point = 0
      for _ in range(r):
        f_pos = positions[f_pos]
        point += scores[f_pos]
        max_point = max(max_point, point)
    else:
      point1, point2 = 0, 0
      point1 = loop_c * point_loop
      max_point1 = point1
      for _ in range(r):
        f_pos = positions[f_pos]
        point1 += scores[f_pos]
        max_point1 = max(point1, max_point1)
      point2 = (loop_c - 1) * point_loop
      max_point2 = point2
      for _ in range(loop):
        f_pos = positions[f_pos]
        point2 += scores[f_pos]
        max_point2 = max(point2, max_point2)
      max_point = max(max_point, max(max_point1, max_point2))
  print(max_point)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
positions = [int(i) for i in input().split()]
scores = [int(i) for i in input().split()]
if max(scores) <= 0:
  print(max(scores))
else:
  positions = [0] + positions
  scores = [0] + scores
  max_point = -pow(10, 9)
  #print(max_point)
  dic = {}
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    if f_pos not in dic:
      point_loop = 0
      loop = 0
      pos_set = set([f_pos])
      while True:
        f_pos = positions[f_pos]
        point_loop += scores[f_pos]
        #print('pos', f_pos)
        #print(point)
        loop += 1
        if f_pos in pos_set:
          for j in pos_set:
            dic[j] = [loop, point_loop]
          break
        pos_set.add(f_pos)
    else:
      loop, point_loop = dic[f_pos]
    #print(loop, point)
    loop_c = k // loop
    r = k % loop
    if loop_c ==　0 or point_loop <= 0:
      if point_loop <= 0:
        if point_c > 0:
          r = loop
      point = 0
      for _ in range(r):
        f_pos = positions[f_pos]
        point += scores[f_pos]
        max_point = max(max_point, point)
    else:
      point1, point2 = 0, 0
      point1 = loop_c * point_loop
      max_point1 = point1
      for _ in range(r):
        f_pos = positions[f_pos]
        point1 += scores[f_pos]
        max_point1 = max(point1, max_point1)
      point2 = (loop_c - 1) * point_loop
      max_point2 = point2
      for _ in range(loop_c):
        f_pos = positions[f_pos]
        point2 += scores[f_pos]
        max_point2 = max(point2, max_point2)
      max_point = max(max_point, max(max_point1, max_point2))
  print(max_point)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(3000)
n, k = map(int, input().split())
pos = [int(i) for i in input().split()]
score = [int(i) for i in input().split()]
if max(score) <= 0:
  print(max(score))
else:
  pos = [0] + pos
  score = [0] + score
  max_point = -10 ** 11
  s_l = [[0]]
  nei = {}
  dic = {}
  loop = 0
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    if f_pos not in nei:
      points = [0]
      count = 0
      loop += 1
      while True:
        n_pos = pos[f_pos]
        points.append(points[-1] + score[n_pos])
        count += 1
        nei[f_pos] = [count, loop]
        if n_pos in nei:
          dic[loop] = count
          break
        f_pos = n_pos
      #print(nei)
      s_l.append(points)
      count = 1
    else:
      loop = nei[f_pos][1]
      count = nei[f_pos][0]
      points = s_l[loop]
    #print(points)
    #print(count)
    loop_num = dic[loop]
    s = points[count - 1]
    m = points[loop_num] - s
    a = k // loop_num
    b = k % loop_num
    if points[loop_num] > 0:
      point = points[loop_num] * a
      if point > max_point and a != 0:
        max_point = point
    else:
      point = 0
      if a > 0:
        b = loop_num
    #print(point)
    if b > 0:
      t_max = -10 ** 11
      if loop_num - count + 1 >= b:
        for j in range(b):
          t = points[j + count] - s
          #print(t)
          if t > t_max:
            t_max = t
      else:
        for j in range(count, loop_num + 1):
          t = points[j] - s
          #print(t)
          if t > t_max:
            t_max = t
        for j in range(1, b - loop_num + count):
          t = points[j] + m
          #print(t)
          if t > t_max:
            t_max = t
      point += t_max
    #print(point)
    if point > max_point:
      max_point = point
  print(max_point)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
pos = [int(i) for i in input().split()]
score = [int(i) for i in input().split()]
if max(score) <= 0:
  print(max(score))
else:
  pos = [0] + pos
  score = [0] + score
  max_point = -10 ** 11
  s_dic = {}
  dic = {}
  loop = 0
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    if f_pos not in dic:
      points = [0]
      index = 0
      loop += 1
      while True:
        n_pos = pos[f_pos]
        points.append(points[-1] + score[n_pos])
        index += 1
        dic[f_pos] = [index, loop]
        if n_pos in dic:
          break
        f_pos = n_pos
      #print(nei)
      s_dic[loop] = points
      index = 1
    else:
      index, loop = dic[f_pos]
      points = s_dic[loop]
    #print(points)
    #print(count)
    loop_num = len(points) - 1
    s = points[index - 1]
    m = points[loop_num] - s
    a = k // loop_num
    b = k % loop_num
    if points[loop_num] > 0:
      point = points[loop_num] * a
      if point > max_point and a != 0:
        max_point = point
    else:
      point = 0
      if a > 0:
        b = loop_num
    #print(point)
    if b > 0:
      t_max = -10 ** 11
      if loop_num - index + 1 >= b:
        for j in range(b):
          t = points[j + index] - s
          #print(t)
          if t > t_max:
            t_max = t
      else:
        for j in range(index, loop_num + 1):
          t = points[j] - s
          #print(t)
          if t > t_max:
            t_max = t
        for j in range(1, b - loop_num + index):
          t = points[j] + m
          #print(t)
          if t > t_max:
            t_max = t
      point += t_max
    #print(point)
    if point > max_point:
      max_point = point
  print(max_point)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(3000)
n, k = map(int, input().split())
pos = [int(i) for i in input().split()]
score = [int(i) for i in input().split()]
if max(score) <= 0:
  print(max(score))
else:
  pos = [0] + pos
  score = [0] + score
  max_point = -10 ** 11
  s_l = [[0]]
  nei = {}
  dic = {}
  loop = 0
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    if f_pos not in nei:
      points = [0]
      count = 0
      loop += 1
      while True:
        n_pos = pos[f_pos]
        points.append(points[-1] + score[n_pos])
        count += 1
        nei[f_pos] = [count, loop]
        if n_pos in nei:
          dic[loop] = count
          break
        f_pos = n_pos
      #print(nei)
      s_l.append(points)
      count = 1
    else:
      loop = nei[f_pos][1]
      count = nei[f_pos][0]
      points = s_l[loop]
    #print(points)
    #print(count)
    loop_num = dic[loop]
    s = points[count - 1]
    m = points[loop_num] - s
    a = k // loop_num
    b = k % loop_num
    if points[loop_num] > 0:
      point = points[loop_num] * a
      if point > max_point and a != 0:
        max_point = point
    else:
      point = 0
      if a > 0:
        b = loop_num
    #print(point)
    if b > 0:
      t_max = -10 ** 11
      if loop_num - count + 1 >= b:
        for j in range(b):
          t = points[j + count] - s
          #print(t)
          if t > t_max:
            t_max = t
      else:
        for j in range(count, loop_num + 1):
          t = points[j] - s
          #print(t)
          if t > t_max:
            t_max = t
        for j in range(1, b - loop_num + count):
          t = points[j] + m
          #print(t)
          if t > t_max:
            t_max = t
      point += t_max
    #print(point)
    if point > max_point:
      max_point = point
  print(max_point)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
pos = [int(i) for i in input().split()]
score = [int(i) for i in input().split()]
if max(score) <= 0:
  print(max(score))
else:
  pos = [0] + pos
  score = [0] + score
  max_point = -10 ** 10
  s_l = [[0]]
  nei = {}
  dic = {}
  loop = 0
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    if f_pos not in nei:
      points = [0]
      count = 0
      loop += 1
      while True:
        n_pos = pos[f_pos]
        points.append(points[-1] + score[n_pos])
        count += 1
        nei[f_pos] = [count, loop]
        if n_pos in nei:
          dic[loop] = count
          break
        f_pos = n_pos
      #print(points)
      #print(nei)
      s_l.append(points)
      count = 1
    else:
      loop = nei[f_pos][1]
      count = nei[f_pos][0]
      points = s_l[loop]
    loop_num = dic[loop]
    s = points[count - 1]
    m = points[loop_num] - s
    a = k // loop_num
    b = k % loop_num
    if points[loop_num] > 0:
      point = points[loop_num] * a
      if point > max_point:
        max_point = point
    else:
      point = 0
      if a > 0:
        b = loop_num
    if b > 0:
      t_max = -10 ** 10
      if loop_num - count + 1 >= b:
        for j in range(b):
          t = points[j + count] - s
          if t > t_max:
            t_max = t
      else:
        for j in range(count, loop_num + 1):
          t = points[j] - s
          if t > t_max:
            t_max = t
        if b != loop_num and count != 1:
          for j in range(1, b - loop_num + count):
            t = points[j] + m
            if t > t_max:
              t_max = t
      point += t_max
    #print(point)
    if point > max_point:
      max_point = point
  print(max_point)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
pos = [int(i) for i in input().split()]
score = [int(i) for i in input().split()]
if max(score) <= 0:
  print(max(score))
else:
  pos = [0] + pos
  score = [0] + score
  max_point = -10 ** 10
  s_l = [[0]]
  nei = {}
  dic = {}
  loop = 0
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    points = [0]
    count = 0
    if f_pos not in nei:
      loop += 1
      while True:
        n_pos = pos[f_pos]
        points.append(points[-1] + score[n_pos])
        count += 1
        nei[f_pos] = [count, loop]
        if n_pos in nei:
          dic[loop] = count
          break
        f_pos = n_pos
      #print(points)
      #print(nei)
      s_l.append(points)
      loop_num = count
      count = 1
    else:
      loop = nei[f_pos][1]
      count = nei[f_pos][0]
      loop_num = dic[loop]
      points = s_l[loop]
    s = points[count - 1]
    m = points[loop_num] - s
    a = k // loop_num
    b = k % loop_num
    if points[loop_num] > 0:
      point = points[loop_num] * a
    else:
      point = 0
      b = loop_num
    if b > 0:
      if loop_num - count + 1 >= b:
        t_max = -10 ** 10
        for j in range(b):
          t = points[j + count] - s
          if t > t_max:
            t_max = t
      else:
        t_max = -10 ** 10
        for j in range(count, loop_num + 1):
          t = points[j] - s
          if t > t_max:
            t_max = t
        for j in range(1, b - loop_num + count):
          t = points[j] + m
          if t > t_max:
            t_max = t
      point += t_max
    #print(point)
    if point > max_point:
      max_point = point
  print(max_point)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
pos = [int(i) for i in input().split()]
score = [int(i) for i in input().split()]
if max(score) <= 0:
  print(max(score))
else:
  pos = [0] + pos
  score = [0] + score
  max_point = -10 ** 10
  s_l = [[0]]
  nei = {}
  dic = {}
  loop = 0
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    points = [0]
    count = 0
    if f_pos not in nei:
      loop += 1
      while True:
        n_pos = pos[f_pos]
        points.append(points[-1] + score[n_pos])
        count += 1
        nei[f_pos] = [count, loop]
        if n_pos in nei:
          dic[loop] = count
          break
        f_pos = n_pos
      #print(points)
      #print(nei)
      s_l.append(points)
      loop_num = count
      count = 1
    else:
      loop = nei[f_pos][1]
      count = nei[f_pos][0]
      loop_num = dic[loop]
      points = s_l[loop]
    s = points[count - 1]
    m = points[loop_num] - s
    a = k // loop_num
    b = k % loop_num
    if points[loop_num] > 0:
      point = points[loop_num] * a
      if b > 0:
        if loop_num - count + 1 >= b:
          t_max = -10 ** 10
          for j in range(b):
            t = points[j + count] - s
            if t > t_max:
              t_max = t
        else:
          t_max = -10 ** 10
          for j in range(count, loop_num + 1):
            t = points[j] - s
            if t > t_max:
              t_max = t
          for j in range(1, b - loop_num + count):
            t = points[j] + m
            if t > t_max:
              t_max = t
        point += t_max
    else:
      point = max(points)
    #print(point)
    if point > max_point:
      max_point = point
  print(max_point)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
pos = [int(i) for i in input().split()]
score = [int(i) for i in input().split()]
if max(score) <= 0:
  print(max(score))
else:
  pos = [0] + pos
  score = [0] + score
  max_point = -10 ** 10
  s_l = [[0]]
  nei = {}
  dic = {}
  loop = 0
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    points = [0]
    count = 0
    if f_pos not in nei:
      loop += 1
      while True:
        n_pos = pos[f_pos]
        points.append(points[-1] + score[n_pos])
        count += 1
        nei[f_pos] = [count, loop]
        if n_pos in nei:
          dic[loop] = count
          break
        f_pos = n_pos
      #print(points)
      #print(nei)
      s_l.append(points)
      loop_num = count
    else:
      loop = nei[f_pos][1]
      count = nei[f_pos][0]
      loop_num = dic[loop]
      s = s_l[loop][count - 1]
      for j in range(count, loop_num + 1):
        points.append(s_l[loop][j] - s)
      s = s_l[loop][loop_num] - s
      for j in range(1, count):
        points.append(s_l[loop][j] + s)
      #print(points)
    a = k // loop_num
    b = k % loop_num
    if points[loop_num] > 0:
      point = points[loop_num] * a
      if b > 0:
        point += max(points[1:b + 1])
    else:
      point = max(points)
    #print(point)
    if point > max_point:
      max_point = point
  print(max_point)