Problem:


Score : 400 points

Problem Statement

Takahashi will play a game using a piece on an array of squares numbered 1, 2, \cdots, N. Square i has an integer C_i written on it. Also, he is given a permutation of 1, 2, \cdots, N: P_1, P_2, \cdots, P_N.

Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between 1 and K (inclusive):

In one move, if the piece is now on Square i (1 \leq i \leq N), move it to Square P_i. Here, his score increases by C_{P_i}.

Help him by finding the maximum possible score at the end of the game. (The score is 0 at the beginning of the game.)

Constraints

2 \leq N \leq 5000

1 \leq K \leq 10^9

1 \leq P_i \leq N

P_i \neq i

P_1, P_2, \cdots, P_N are all different.

-10^9 \leq C_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_1 P_2 \cdots P_N
C_1 C_2 \cdots C_N

Output

Print the maximum possible score at the end of the game.

Sample Input 1

5 2
2 4 5 1 3
3 4 -10 -8 8

Sample Output 1

8

When we start at some square of our choice and make at most two moves, we have the following options:

If we start at Square 1, making one move sends the piece to Square 2, after which the score is 4. Making another move sends the piece to Square 4, after which the score is 4 + (-8) = -4.

If we start at Square 2, making one move sends the piece to Square 4, after which the score is -8. Making another move sends the piece to Square 1, after which the score is -8 + 3 = -5.

If we start at Square 3, making one move sends the piece to Square 5, after which the score is 8. Making another move sends the piece to Square 3, after which the score is 8 + (-10) = -2.

If we start at Square 4, making one move sends the piece to Square 1, after which the score is 3. Making another move sends the piece to Square 2, after which the score is 3 + 4 = 7.

If we start at Square 5, making one move sends the piece to Square 3, after which the score is -10. Making another move sends the piece to Square 5, after which the score is -10 + 8 = -2.

The maximum score achieved is 8.

Sample Input 2

2 3
2 1
10 -7

Sample Output 2

13

Sample Input 3

3 3
3 1 2
-1000 -2000 -3000

Sample Output 3

-1000

We have to make at least one move.

Sample Input 4

10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719

Sample Output 4

29507023469

The absolute value of the answer may be enormous.



Sample input:
5 2
2 4 5 1 3
3 4 -10 -8 8


Sample output:
8

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

for c in C:
    if c >= 0:
        flg = False
        break
    flg = True
if flg:
    print(max(C))
    exit()
    
passed = []
loop_list = []
for now in range(1, N+1):
    if now in passed:
        continue
    passed.append(now)
    loop = [now]
    start_c = C[now-1]
    sum_list = []
    while P[now-1] not in passed:
        passed.append(P[now-1])
        now = P[now-1]
        loop.append(now)
        sum_list.append(C[now-1])
    sum_list.append(start_c)
    loop_list.append((loop, sum_list))
    
ans = -1e30
for loop, sum_list in loop_list:
    if sum(sum_list) > 0 and K > len(loop):
        mx = 0
        rest = K % len(loop)
        for l in range(1, rest+1):
            for i in range(len(loop)):
                tmp_loop = sum_list + sum_list
                mx = max(mx, sum(tmp_loop[i:i+l]))
        tmp = sum(sum_list) * (K//len(loop)) + mx
    else:
        if K > len(loop):
            rest = K % len(loop)
        else:
            rest = K
        mx = 0
        for l in range(1, rest+1):
            for i in range(len(loop)):
                tmp_loop = loop + loop
                mx = max(mx, sum(tmp_loop[i:i+l]))
        tmp = mx
        
    ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
c = tuple(map(int,input().split()))
for i in range(n):
  p[i] -= 1

ans = -float('inf')
v = [False for _ in range(n)]
for i in range(n):
  j = i
  if v[j]:
    continue
  r = []
  while(v[j] == False):
    r.append(j)
    v[j] = True
    j = p[j]
  cr = []
  for ri in r:
    cr.append(c[ri])
  k1 = k%len(cr)
  k2 = k//len(cr)
  k1 += len(cr)
  k2 = max(k2-1,0)
  cr2 = cr+cr+cr
  #print(k1,k2,cr)
  now = -float('inf')
  csum = [0 for _ in range(len(cr2)+1)]
  for i0 in range(len(cr2)):
    csum[i0+1] = csum[i0]+cr2[i0]
  for i0 in range(len(cr)):
    for i1 in range(k1):
      now = max(csum[i0+i1+1]-csum[i0],now)
  if sum(cr) > 0:
    now += sum(cr)*k2
  ans = max(ans,now)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split(" "))
Ps = list(map(int, input().split(" ")))
Cs = list(map(int, input().split(" ")))

def create_cycle(start):
    next_idx = start
    scores = []
    indexes = set()

    while not next_idx in indexes:
        scores.append(Cs[next_idx])
        indexes.add(next_idx)
        next_idx = Ps[next_idx] - 1
    return (scores, sum(scores))

cycles = []

for i in range(N):
    cycles.append(create_cycle(i))


max_score = -9999999999
for cycle, score in cycles:
    length = len(cycle)
    score_sum = 0
    steps = K
    if score > 0:
        times = K // length
        score_sum += times * score
        mod = K % length
        steps = mod
    max_idx = 0
    for i, s in enumerate(cycle):
        if i > steps - 1:
            break            
        score_sum += s
        if score_sum > max_score:
            max_score = score_sum

print(max_score)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))

answer = -float('inf')
for start_p in range(1, N+1):

    cycle_total_score = 0
    cycle_in_score = -float('inf')
    cycle_count = 0
    next_p = P[start_p]
    while True:
        cycle_total_score += C[next_p]
        cycle_in_score = max(cycle_in_score, cycle_total_score)
        cycle_count += 1

        if next_p == start_p:
            # print('start_p:', start_p, ' cycle_total_score:', cycle_total_score, 'cycle_in_score:', cycle_in_score, 'cycle_count:', cycle_count)
            break
        next_p = P[next_p]
    
    max_score = 0
    if K <= cycle_count:
        #最大の試行回数がcycle_countよりも小さい場合はcycleの中で最大のスコアcycle_in_scoreを使用する
        max_score = cycle_in_score
    else:
        if cycle_total_score >= 0:
            #1サイクルでプラスの場合はできるだけサイクルを回してサイクルの中で一番良いところでbeak
            max_score = (K // cycle_count) * cycle_total_score
            #あふれたK % cycle_count回数分だけスコアを足すためにmaxを探さす
            add_max_count = K % cycle_count
            add_total_score = 0
            add_score = -float('inf')
            add_count = 0
            add_next_p = P[start_p]
            while True:
                add_total_score += C[add_next_p]
                add_score = max(add_score, add_total_score)
                add_count += 1

                if add_count == add_max_count:
                    break
                add_next_p = P[add_next_p]
            max_score += add_total_score
        else:
            #1サイクルでマイナスの場合はサイクルを回さないで、サイクルの中で一番良いところでbreak
            max_score = cycle_in_score
    # print('max_score', max_score)
    answer = max(answer, max_score)

print(answer)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))

answer = -float('inf')
for start_p in range(1, N+1):

    cycle_total_score = 0
    cycle_in_score = -float('inf')
    cycle_count = 0
    next_p = P[start_p]
    while True:
        cycle_total_score += C[next_p]
        cycle_in_score = max(cycle_in_score, cycle_total_score)
        cycle_count += 1

        if next_p == start_p:
            # print('start_p:', start_p, ' cycle_total_score:', cycle_total_score, 'cycle_in_score:', cycle_in_score, 'cycle_count:', cycle_count)
            break
        next_p = P[next_p]
    
    max_score = 0
    if K <= cycle_count:
        #最大の試行回数がcycle_countよりも小さい場合はcycleの中で最大のスコアcycle_in_scoreを使用する
        max_score = cycle_in_score
    else:
        if cycle_total_score >= 0:
            #1サイクルでプラスの場合はできるだけサイクルを回してサイクルの中で一番良いところでbeak
            max_score = (K // cycle_count) * cycle_total_score
            #あふれたK % cycle_count回数分だけスコアを足すためにmaxを探さす
            add_max_count = K % cycle_count
            add_total_score = 0
            add_score = -float('inf')
            add_count = 0
            add_next_p = P[start_p]
            while True:
                add_total_score += C[add_next_p]
                add_score = max(add_score, add_total_score)
                add_count += 1

                if add_count == add_max_count:
                    break
                add_next_p = P[add_next_p]
            max_score += add_total_score
        else:
            #1サイクルでマイナスの場合はサイクルを回さないで、サイクルの中で一番良いところでbreak
            max_score = cycle_in_score
    # print('max_score', max_score)
    answer = max(answer, max_score)

print(answer)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


def main():
    cells, moves = [int(x) for x in input().split()]
    nexts = [int(x) - 1 for x in input().split()]
    scores = [int(x) for x in input().split()]

    ans = - 10**10
    for start in range(cells):
        route = []
        route_append = route.append
        position = start
        while True:
            route_append(scores[position])
            position = nexts[position]
            if position == start:  # Looped
                break

        length = len(route)
        total = sum(route)
        if total > 0:
            q, mod = divmod(moves, length)
            if mod == 0:
                candidate = total * q
            else:
                candidate = max(list(accumulate(route))[:mod]) + total * q
        else:
            candidate = max(list(accumulate(route))[:min(moves, length)])
        ans = max(ans, candidate)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#D
class UnionFind():
    # https://www.slideshare.net/chokudai/union-find-49066733
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        # root[x]>=0の場合は、特に直接的な意味を持たない気がする。計算に寄与するので意味はあるのだろうが。
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        # 無結合の時はRank=0,結合して1つ木が深くなると根がRank+=1
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    #
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        # (1)xのランクの方が大きい(位置が深い)場合
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        # (2)yのランクの方が大きい(位置が深い)場合 or 等しい場合
        # また等しい場合、引数の2つめのyの方のランクを1つ増やす
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    # Return: True or False
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
###################################################################    
N,K=map(int,input().split())
UN=UnionFind(N)
P=list(map(int,input().split()))
C=list(map(int,input().split()))
for i,num in enumerate(P):
    UN.Unite(i+1,num)
root=set()
loop_score=dict()
loop_len=dict()

#print(UN.root)
for i,node in enumerate(UN.root):
    if i==0:
        pass
    else:
        if node<0:
            #print(i,"is root")
            root.add(i)
            score=0
            ini=i
            leng=0
            while True:
                ret=P[ini-1]
                score += C[ret-1]
                leng +=1
                if ret==i:
                    break
                else:
                    ini=ret
            loop_score[i]=score
            loop_len[i] = leng
            
#print(loop_score)
#print(loop_len)

ans_list=[]
ans=float("-inf")

for i in range(1,N+1):
    t=K
    p=UN.Find_Root(i)
    
    
    #ループした方がいいかの確認
    if loop_score[p]>0:
        tmp=0
        pos=i
        tmp += (t//loop_len[p])*loop_score[p]
        if tmp>0:
            ans=max(tmp,ans)
        t %= loop_len[p]
        for j in range(t):
            pos = P[pos-1]
            tmp += C[pos-1]
            ans=max(tmp,ans)

    else:
        tmp=0
        pos=i
        
        for j in range(min(t,loop_len[p]-1)):
            pos = P[pos-1]
            tmp += C[pos-1]
            ans=max(tmp,ans)
    
print(ans)

Submission status: Wrong Answer

Solution code:
#D
class UnionFind():
    # https://www.slideshare.net/chokudai/union-find-49066733
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        # root[x]>=0の場合は、特に直接的な意味を持たない気がする。計算に寄与するので意味はあるのだろうが。
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        # 無結合の時はRank=0,結合して1つ木が深くなると根がRank+=1
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    #
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        # (1)xのランクの方が大きい(位置が深い)場合
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        # (2)yのランクの方が大きい(位置が深い)場合 or 等しい場合
        # また等しい場合、引数の2つめのyの方のランクを1つ増やす
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    # Return: True or False
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
###################################################################    
N,K=map(int,input().split())
UN=UnionFind(N)
P=list(map(int,input().split()))
C=list(map(int,input().split()))
for i,num in enumerate(P):
    UN.Unite(i+1,num)
root=set()
loop_score=dict()
loop_len=dict()

#print(UN.root)
for i,node in enumerate(UN.root):
    if i==0:
        pass
    else:
        if node<0:
            #print(i,"is root")
            root.add(i)
            score=0
            ini=i
            leng=0
            while True:
                ret=P[ini-1]
                score += C[ret-1]
                leng +=1
                if ret==i:
                    break
                else:
                    ini=ret
            loop_score[i]=score
            loop_len[i] = leng
            
#print(loop_score)
#print(loop_len)

ans_list=[]
ans=float("-inf")

for i in range(1,N+1):
    t=K
    p=UN.Find_Root(i)
    
    
    #ループした方がいいかの確認
    if loop_score[p]>0:
        tmp=0
        pos=i
        tmp += (t//loop_len[p])*loop_score[p]
        ans=max(tmp,ans)
        t %= loop_len[p]
        for j in range(t):
            pos = P[pos-1]
            tmp += C[pos-1]
            ans=max(tmp,ans)

    else:
        tmp=0
        pos=i
        ans=max(tmp,ans)
        
        for j in range(min(t,loop_len[p]-1)):
            pos = P[pos-1]
            tmp += C[pos-1]
            ans=max(tmp,ans)
    
print(ans)

Submission status: Wrong Answer

Solution code:
#D
class UnionFind():
    # https://www.slideshare.net/chokudai/union-find-49066733
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        # root[x]>=0の場合は、特に直接的な意味を持たない気がする。計算に寄与するので意味はあるのだろうが。
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        # 無結合の時はRank=0,結合して1つ木が深くなると根がRank+=1
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    #
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        # (1)xのランクの方が大きい(位置が深い)場合
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        # (2)yのランクの方が大きい(位置が深い)場合 or 等しい場合
        # また等しい場合、引数の2つめのyの方のランクを1つ増やす
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    # Return: True or False
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
###################################################################    
N,K=map(int,input().split())
UN=UnionFind(N)
P=list(map(int,input().split()))
C=list(map(int,input().split()))
for i,num in enumerate(P):
    UN.Unite(i+1,num)
root=set()
loop_score=dict()
loop_len=dict()

#print(UN.root)
for i,node in enumerate(UN.root):
    if i==0:
        pass
    else:
        if node<0:
            #print(i,"is root")
            root.add(i)
            score=0
            ini=i
            leng=0
            while True:
                ret=P[ini-1]
                score += C[ret-1]
                leng +=1
                if ret==i:
                    break
                else:
                    ini=ret
            loop_score[i]=score
            loop_len[i] = leng
            
#print(loop_score)
#print(loop_len)

ans_list=[]
ans=float("-inf")

for i in range(1,N+1):
    t=K
    p=UN.Find_Root(i)
    
    
    #ループした方がいいかの確認
    if loop_score[p]>0:
        tmp=0
        tmp += (t//loop_len[p])*loop_score[p]
        t %= loop_len[p]
        pos=i
        for j in range(t):
            pos = P[pos-1]
            tmp += C[pos-1]
            ans=max(tmp,ans)

    else:
        tmp=0
        pos=i
        
        for j in range(min(t,loop_len[p]-1)):
            pos = P[pos-1]
            tmp += C[pos-1]
            ans=max(ans,tmp)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
P = list(map(lambda x:x - 1, map(int,readline().split())))
C = list(map(int,readline().split()))

# 全ての頂点からスタートして、ループを探す
# ループを一周したときの得点が正であれば、
# ・[可能な限り - 1]回ループを回して、あとは得点が最大になるところまで歩く
# (-1回は、最後のループは回し切らないほうが良いパターンがあるため)

ans = - (10 ** 10)
for start in range(N):
  cur = start
  point_sum = 0
  cnt = 0
  best = []
  while True:
    cur = P[cur] # 次に進む
    cnt += 1 # ステップ数を記録
    point_sum += C[cur] # 得点を加算
    if len(best) == 0:
      best.append(point_sum)
    else:
      best.append(max(best[-1], point_sum))
    if cur == start:
      break # 始点に戻っていたらそこで終了
  #print("start",start,"best",best,"point_sum",point_sum)
  # ここから場合分け
  # 1.ループの得点が正のとき
  # 1.1. 可能な限りループを回して、そのあと最も得点が高いところまで行く
  # 1.2. [可能な限り - 1]回ループを回して、そのあと最も得点が高いところまで行く
  # 2.ループの得点が正でないとき
  # 2.1. Kがループ一周以上の回数のときは好きな得点を選べる
  # 2.2. Kがループ一周未満の回数のときは、そこまでの最高得点を選ぶ
  
  # 1.
  if point_sum > 0:
    # 1.1.
    loop_count = K // cnt # 可能な限り回したときのループ数
    case1_point = loop_count * point_sum
    rest = K % cnt
    case1_point += best[rest - 1]
    
    point = case1_point
    # 1.2.
    if loop_count > 0: # ループが一回以上あるときのみ検討可能
      loop_count -= 1
      case2_point = loop_count * point_sum
      # ループを一回省略しているので、好きな数を選べる
      case2_point += best[-1]
      if point < case2_point:
        point = case2_point
    if ans < point:
      ans = point
  else:
    # ループの得点が正でないとき
    point = 0
    if cnt <= K: # 好きな得点を選べる
      point = best[-1]
    else:
      point = best[cnt - 1]
    if ans < point:
      ans = point
  
print(ans)

Submission status: Wrong Answer

Solution code:
def calc_circle(P,C,K):
  N = len(P)
  m = 0
  M = -10**9
  if K > N:
    if sum(C) > 0:
      m = (K // N) * sum(C)
      M = 0
    K = K % N
  for i in range(0,N):  
    for j in range(1,K+1):
      s = 0
      index = i
      for k in range(0,j):
        index = P[index]
        s = s + C[index]
      if M < s:
        M = s
  return (M + m)

N,K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
for n in range(0,N):
  P[n] = P[n] - 1
M = -10 ** 9
circleCheck = [0] * N
for n in range(0,N):
  if circleCheck[n] == 0:
    circleP = []
    circleC = []
    index = n
    count = 0
    while circleCheck[index] == 0:
      count = count + 1
      circleP.append(count)
      circleC.append(C[index])
      circleCheck[index] = 1
      index = P[index]
    circleP[count-1] = 0
    s = calc_circle(circleP,circleC,K)
    if s > M:
      M = s
print(M)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


def main():
    cells, moves = [int(x) for x in input().split()]
    nexts = [int(x) - 1 for x in input().split()]
    scores = [int(x) for x in input().split()]

    ans = - 10**10
    for start in range(cells):
        route = []
        route_append = route.append
        now = start
        for _step in range(cells):
            nex = nexts[now]
            route_append(scores[nex])
            if nex == start:  # Looped
                break
            now = nex

        length = len(route)
        total = sum(route)
        if total > 0:
            q, mod = divmod(moves, length)
            if mod == 0:
                candidate = total * q
            else:
                candidate = max(list(accumulate(route))[:mod]) + total * q
        else:
            candidate = max(list(accumulate(route))[:min(moves, length)])
        ans = max(ans, candidate)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


def main():
    cells, moves = [int(x) for x in input().split()]
    nexts = [int(x) - 1 for x in input().split()]
    scores = [int(x) for x in input().split()]

    ans = - 10**20
    for start in range(cells):
        route = []
        route_append = route.append
        now = start
        for _step in range(cells):
            nex = nexts[now]
            route_append(scores[nex])
            if nex == start:
                break
            now = nex

        length = len(route)
        total = sum(route)
        if total >= 0:
            q, mod = divmod(moves, length)
            if mod == 0:
                candidate = total * q
            else:
                candidate = max(list(accumulate(route))[:mod]) + total * q
        else:
            candidate = max(list(accumulate(route))[:min(moves, length)])
        ans = max(ans, candidate)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#D
class UnionFind():
    # https://www.slideshare.net/chokudai/union-find-49066733
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        # root[x]>=0の場合は、特に直接的な意味を持たない気がする。計算に寄与するので意味はあるのだろうが。
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        # 無結合の時はRank=0,結合して1つ木が深くなると根がRank+=1
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    #
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        # (1)xのランクの方が大きい(位置が深い)場合
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        # (2)yのランクの方が大きい(位置が深い)場合 or 等しい場合
        # また等しい場合、引数の2つめのyの方のランクを1つ増やす
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    # Return: True or False
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
###################################################################    
N,K=map(int,input().split())
UN=UnionFind(N)
P=list(map(int,input().split()))
C=list(map(int,input().split()))
for i,num in enumerate(P):
    UN.Unite(i+1,num)
root=set()
loop_score=dict()
loop_len=dict()

#print(UN.root)
for i,node in enumerate(UN.root):
    if i==0:
        pass
    else:
        if node<0:
            #print(i,"is root")
            root.add(i)
            score=0
            ini=i
            leng=0
            while True:
                ret=P[ini-1]
                score += C[ret-1]
                leng +=1
                if ret==i:
                    break
                else:
                    ini=ret
            loop_score[i]=score
            loop_len[i] = leng
            
#print(loop_score)
#print(loop_len)

ans_list=[]
ans=float("-inf")

for i in range(1,N+1):
    t=K
    p=UN.Find_Root(i)
    
    
    #ループした方がいいかの確認
    if loop_score[p]>0:
        tmp=0
        tmp += (K//loop_len[p])*loop_score[p]
        t %= loop_len[p]
        pos=i
        for j in range(t):
            pos = P[pos-1]
            tmp += C[pos-1]
            ans=max(tmp,ans)

    else:
        tmp=0
        pos=i
        
        for j in range(min(t,loop_len[p])):
            pos = P[pos-1]
            tmp += C[pos-1]
            ans=max(ans,tmp)
    
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


def main():
    cells, moves = [int(x) for x in input().split()]
    nexts = [int(x) - 1 for x in input().split()]
    scores = [int(x) for x in input().split()]

    ans = - 10**20
    for start in range(cells):
        route = []
        route_append = route.append
        now = start
        for _step in range(cells):
            nex = nexts[now]
            route_append(scores[nex])
            if nex == start:
                break
            now = nex

        length = len(route)
        total = sum(route)
        if total > 0:
            q, mod = divmod(moves, length)
            if mod == 0:
                candidate = total * q
            else:
                candidate = max(list(accumulate(route))[:mod]) + total * q
        else:
            candidate = max(list(accumulate(route))[:min(moves, length)])
        ans = max(ans, candidate)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#D
class UnionFind():
    # https://www.slideshare.net/chokudai/union-find-49066733
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        # root[x]>=0の場合は、特に直接的な意味を持たない気がする。計算に寄与するので意味はあるのだろうが。
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        # 無結合の時はRank=0,結合して1つ木が深くなると根がRank+=1
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    #
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        # (1)xのランクの方が大きい(位置が深い)場合
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        # (2)yのランクの方が大きい(位置が深い)場合 or 等しい場合
        # また等しい場合、引数の2つめのyの方のランクを1つ増やす
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    # Return: True or False
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
###################################################################    
N,K=map(int,input().split())
UN=UnionFind(N)
P=list(map(int,input().split()))
C=list(map(int,input().split()))
for i,num in enumerate(P):
    UN.Unite(i+1,num)
root=set()
loop_score=dict()
loop_len=dict()

#print(UN.root)
for i,node in enumerate(UN.root):
    if i==0:
        pass
    else:
        if node<0:
            #print(i,"is root")
            root.add(i)
            score=0
            ini=i
            leng=0
            while True:
                ret=P[ini-1]
                score += C[ret-1]
                leng +=1
                if ret==i:
                    break
                else:
                    ini=ret
            loop_score[i]=score
            loop_len[i] = leng
            
#print(loop_score)
#print(loop_len)

ans_list=[]
ans=float("-inf")

for i in range(1,N+1):
    t=K
    p=UN.Find_Root(i)
    
    
    #ループした方がいいかの確認
    if loop_score[p]>0:
        tmp=0
        tmp += (K//loop_len[p])*loop_score[p]
        t %= loop_len[p]
        pos=i
        for j in range(t):
            pos = P[pos-1]
            tmp += C[pos-1]
            ans=max(tmp,ans)

    else:
        tmp=0
        pos=i
        
        for j in range(min(t,loop_len[p])):
            pos = P[pos-1]
            tmp += C[pos-1]
            ans=max(ans,tmp)
    
print(ans)