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()))
x=0
A=[]
B=[0]*n
for i in range(n):
  X=[]
  x=i
  while B[x]==0:
    X.append(C[P[x]-1])
    B[x]=1
    x=P[x]-1
  if X!=[]:
    A.append(X)
m=M=max(C)
for a in A:
  l=len(a)
  S=sum(a)
  a=a+a
  for i in range(l):
    s=0
    for j in range(min(k,l)):
      s+=a[i+j]
      if j<k%l:
        m=max(m,s)
      else:
        M=max(M,m,s)
  m=max(m,m+S*((k-1)//l),M,M+S*max(k//l-1,0))
print(m)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
toku=[0]*(n+1)
from collections import deque
for i in range(1,n+1):
  now=i
  aru=[0]*(n+1)
  ans=[0]
  d=deque()
  d.append(i)
  while d:
    now=d.pop()
    if aru[now]==0:
      aru[now]+=1
      ans.append(ans[-1]+c[p[now-1]-1])
    else:
      syuki=sum(aru)
      if syuki>=k:
        toku[i]=max(ans)
      else:
        if ans[-1]<=0:
          toku[i]=max(ans)
        else:
          a=k%syuki
          if a==0:
            a=syuki
          d=[(k//syuki-1)*ans[-1]]
          for i in range(a):
            d.append(d[0]+ans[i+1])
          toku[i]=max(d)
print(max(toku))          
print(toku)

Submission status: Wrong Answer

Solution code:
def main():
    INF = 10 ** 15
    N, K = list(map(int, input().split()))
    P = list(map(lambda x: int(x) - 1, input().split()))
    C = list(map(int, input().split()))
    # P のループの最初を検索しておく
    loop_list = list()
    visited = [0] * N
    for i in range(N):
        if visited[i] == 1:
            continue
        start = i
        size = 0
        sum_c = 0
        while visited[i] == 0:
            visited[i] = 1
            size += 1
            sum_c += C[i]
            i = P[i]
        loop_list.append((start, size, sum_c))
    # 各ループごとに考える
    ans = - INF
    for start, size, sum_c in loop_list:
        MAX_LEN = K % size
        if MAX_LEN == 0:
            MAX_LEN = K
        # 2順ループを作っておく
        CUMSUM_CC = [0] * (2 * size)
        cur_index = P[start]
        CUMSUM_CC[0] = C[P[start]]
        for i in range(1, 2 * size):
            cur_index = P[cur_index]
            CUMSUM_CC[i] += C[cur_index] + CUMSUM_CC[i - 1]
        # 最大MAX_LENの連続部分列での最大スコア
        max_score = - INF
        for left in range(2 * size):
            for right in range(left, min(2 * size, left + MAX_LEN)):
                s = CUMSUM_CC[right]
                if left > 0:
                    s -= CUMSUM_CC[left - 1]
                max_score = max(max_score, s)
        if sum_c > 0:
            if MAX_LEN != K:
                max_score += sum_c * (K // size)
            else:
                max_score += sum_c * (K // size - 1)
        ans = max(ans, max_score)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Doubling():
    def __init__(self, a0, M, C):
        """
        a0 is an array-like object which contains ai, 0 <= i < N.
        ai is the next value of i.
        """
        N = len(a0)
        self.N = N
        self.nt = [[None] * N for i in range(M.bit_length()+1)]
        self.s = [[0] * N for i in range(M.bit_length()+1)]
        for i, a in enumerate(a0):
            self.nt[0][i] = a
            self.s[0][i] = C[a]

        for i in range(1, len(self.nt)):
            for j in range(N):
                if self.nt[i-1][j] is None:
                    self.nt[i][j] = None
                else:
                    self.nt[i][j] = self.nt[i-1][self.nt[i-1][j]]
                    self.s[i][j] = self.s[i-1][self.nt[i-1][j]] * (1<<i)

    def apply(self, i, n):
        """
        Apply n times from i
        """
        j = i
        s = 0
        for k in range(n.bit_length()):
            m = 1 << k
            if m & n:
                j = self.nt[k][j]
                s += self.s[k][j]
            if j is None:
                break

        return j, s


@mt
def slv(N, K, P, C):
    P = [p-1 for p in P]
    S = [[0] * (N+1) for _ in range(N)]


    if K < 2*N:
    # if True:
        ans = -INF
        for i in range(N):
            c = i
            a = 0
            for j in range(K):
                n = P[c]
                a += C[n]
                ans = max(ans, a)
                c = n
        error_print('--')
        return ans

    ga = -INF
    for i in range(N):
        c = i
        done = {c: 0}
        S[i][0] = C[i]
        ans = -INF
        for j in range(1, N+1):
            n = P[c]
            S[i][j] = C[n] + S[i][j-1]
            c = n
            if n in done:
                break
            else:
                done[n] = j
        ans = max(ans, S[i][1])
        ans = max(ans, S[i][done[n]])
        if S[i][j] - S[i][done[n]] > 0:
            ans = S[i][done[n]]
            a = S[i][j] - S[i][done[n]]
            l = j - done[n]
            k = K - done[n]
            m = (k // l)
            if m > 0:
                m -= 1
            ans += a * m
            rem = K - m * l - done[n]
            c = n
            b = ans
            for _ in range(rem):
                n = P[c]
                b += C[n]
                ans = max(ans, b)
                c = n
            ans -= C[i]
        # print(i, ans)
        ga = max(ga, ans)

    return ga


    # from pprint import pprint
    # pprint(S)

    # for i in range(N):



def main():
    N, K = read_int_n()
    P = read_int_n()
    C = read_int_n()
    print(slv(N, K, P, C))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest

def resolve():

    # スペース区切りの整数の入力
    N, K = map(int, input().split())
    # 文字列の入力
    Ps = list(map(int, input().split()))
    Cs = list(map(int, input().split()))

    c = [0] * N
    for i in range(N):
        ni = Ps[i]-1
        c[ni]=Cs[i]

    max_all =-10000000000

    max_im_end=-1
    max_im_val = 0
    for i in range(0,N):
        # print("i {}".format(i))
        if i==0:
            tmp_i_val = 0
        else:
            tmp_i_val = max_im_val - c[i - 1]
        max_i_val = -10000000000
        for j in range(max_im_end+1, i+K):
            j=j%N
            tmp_i_val=tmp_i_val+c[j]
            # print("j {}  tmp_i_val {}".format(j, tmp_i_val))
            if max_i_val<=tmp_i_val:
                max_i_val=tmp_i_val
                max_im_end=j
                # print("max j {}  tmp_i_val {}".format(j, tmp_i_val))
        # print("i end max   max_i_val {}".format( max_i_val))
        max_im_val=max_i_val
        max_all=max(max_all,max_im_val)
    # 出力
    print("{}".format(max_all))





class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5 2
2 4 5 1 3
3 4 -10 -8 8"""
        output = """8"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 3
2 1
10 -7"""
        output = """13"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """3 3
3 1 2
-1000 -2000 -3000"""
        output = """-1000"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719"""
        output = """29507023469"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
N, K = [int(_) for _ in input().split()]
P = [int(_) - 1 for _ in input().split()]
C = [int(_) for _ in input().split()]


X = [False for _ in range(N)]

V = []
for i in range(N):
    if X[i]:
        continue
    t = i
    v = []
    while X[t] is False:
        X[t] = True
        v.append(C[t])
        t = P[t]
    V.append(tuple(v))

def f(v, K):
    if max(v) < 0:
        return max(v)
    n = len(v)
    dp = [[0 for _ in range(n)] for _ in range(K + 1)]

    for k in range(1, K + 1):
        dp[k][0] = max(v[0], 0)
        for i in range(1, n):
            dp[k][i]= max(dp[k-1][i-1] + v[i], 0)
    ans = max([ max(dp[k]) for k in range(K + 1)])
    return(ans)

ans = -100000000000
for v in V:
    n = len(v)
    if K > n:
        s = sum(v)
        if s > 0:
            a = s * (K // n) + f(v * 2, K % n) 
        else:
            a = f(v * 2, n)
    else:
        a = f(v * 2, K)
    ans = max(a, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))

tokuten = []
zan = p[:]
while len(zan) != 0:
    loop = []
    start = zan.pop()
    loop.append(c[start-1])
    next = p[start-1]
    zan.remove(next)
    while start != next:
        loop.append(c[next-1])
        next = p[next-1]
        if next in zan:
            zan.remove(next)
    tokuten.append(loop)

ans = -10e9
for loop in tokuten:
    tmp = 0
    le = len(loop)
    su = sum(loop)
    if le < k:
        if su > 0:
            tmp += (k//le)*su
            amari = k%le
            ma = -10e9
            lplp = loop + loop
            index = loop.index(max(loop))
            for i in range(1,amari+1):
                ma = max(ma,sum(lplp[index:i+index]))
            tmp += ma
            ans = max(ans,tmp)
        if su <= 0:
            ma = -10e9
            lplp = loop + loop
            index = loop.index(max(loop))
            for i in range(1,le+1):
                ma = max(ma,sum(lplp[index:i+index]))
            ans = max(ans,ma)
    else:
        ma = -10e9
        lplp = loop + loop
        index = loop.index(max(loop))
        for i in range(1,k+1):
            ma = max(ma,sum(lplp[index:i+index]))
        ans = max(ans,ma)
print(ans)

Submission status: Wrong Answer

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

for i in range(N):  # スタート位置
    now = i
    visited = []
    score_history = []
    first_loop_max = C[P[now]-1]
    while True:
        next_place = P[now]-1
        if next_place not in visited:
            visited.append(next_place)
            now = next_place
            score_history.append(C[now])  # score_history と visited を対応させる
            first_loop_max = max(first_loop_max, first_loop_max + C[now])
        else:  # ループした
            idx = visited.index(next_place)  # visited の idxから最後までがループ
            loop = visited[idx:]
            loop_score = score_history[idx:]
            tmp1 = loop_score[0]
            loop_score_ruiseki = [tmp1]
            for j in range(1, len(loop_score)):
                tmp1 += loop_score[j]
                loop_score_ruiseki.append(tmp1)
            loop_sum = sum(loop_score)
            if loop_sum <= 0:  # ループを経ても増えない場合
                ans = max(ans, first_loop_max)
                break
            else:  # ループを経るごとに増える場合
                moved = len(visited)
                rem_loops = (K - moved) // len(loop)
                rem_moves = (K - moved) - (rem_loops * len(loop))
                tmp = score_history[-1] + loop_sum * rem_loops + max(loop_score_ruiseki[:rem_moves+1])
                ans = max(ans, tmp)
                break

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,K = [int(i) for i in input().split()]
P = [int(i)-1 for i in input().split()]
C = [int(i) for i in input().split()]
places = []
n = 0
i = 0
T = list(range(N))
while n < N:
    L = [i]
    T.remove(i)
    n += 1
    for _ in range(N):
        if not P[i] in L:
            i = P[i]
            T.remove(i)
            L.append(i)
            n += 1
        else:
             break
    places.append(L)
    if T:
        i = T[0]
scores = []
for L in places:
    s = 0
    M = []
    for l in L:
        s += C[l]
        M.append(s)
    scores.append(M)
ans = -(10**9)
for L in scores:
    l = len(L)
    if K >= l:
        ans = max(ans,L[-1])
        if L[-1] > 0:
            ans = max(ans,L[-1] * (K//l))
    for i in range(l):
        ans = max(ans,L[i])
    for i,j in itertools.combinations(range(l),2):
        if j-i <= K:
            n = 0
            if L[-1] > 0:
                n = L[-1] * ((K-j+i)//l)
            ans = max(ans, L[j]-L[i]+n)
        if N-j+i <= K:
            n=0
            if L[-1]>0:
                n= L[-1] * ((K-l+j-i)//l)
            ans = max(ans,L[i] + L[-1] - L[j]+n)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=input().split()
N,K=int(N),int(K)
P=input().split()
for i in range(N): P[i]=int(P[i])-1
C=input().split()
for i in range(N): C[i]=int(C[i])
  
lpi=[False]*N
maxmain=None
start=0
if True:
  while start<N:#(False in lpi):
    
    #for i in range(len(lpi)):
      #if lpi[i]==False:
        #start=i
        #break
    
    vsd=[-1]*N #Visited
    vsd[start]=0
    pos=start
    lpi[pos]=True
    i=0
    points=[0]
    while True:
      i+=1
      if vsd[P[pos]]==-1:
        pos=P[pos]
        vsd[pos]=i
        lpi[pos]=True
        points.append(points[-1]+C[pos])
      else:
        pos=P[pos]
        lpstart,lpend=vsd[P[pos]],i
        lplen=lpend-lpstart
        points.append(points[-1]+C[pos])
        max_outsideloop=max(points[1:lpstart+1])
        maxr_inloop=max(points[lpstart:lpend+1])-points[lpstart]
        lpbnf=points[lpend]-points[lpstart]
        if K<=len(points)-1: maxsub=max(points[1:])
        else:
          if lpbnf>=0:
            loops=int((K-lpstart)/lplen)
            maxsub=max_outsideloop
            maxsub=max(maxsub, points[lpstart]+lpbnf*loops )
            maxsub=max(maxsub, points[lpstart]+lpbnf*(loops-1)+maxr_inloop )
            #print(lpstart,loops,lplen)#debug
            for j in range(lpstart+loops*lplen+1,K+1):
              maxsub=max(maxsub, points[lpstart+(j-lpstart)%loops]+loops*lpbnf )
              #print("done")
          else:
            maxsub=max(points[1:])
        if maxmain==None: maxmain=maxsub
        else: maxmain=max(maxmain,maxsub)
        #print(points,maxsub) #debug
        break
    start+=1

print(maxmain)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

score = [0 for _ in range(n)]
loopn = [0 for _ in range(n)]
done = {i: True for i in range(n)}
for start in range(n):
    if done[start]:
        nex = -1
        j = 0
        tuuka = []
        nax = -float("inf")
        while nex != start:
            if nex == -1:
                nex = P[start]-1
            else:
                nex = P[nex]-1
            tuuka.append(nex)
            score[start] += C[nex]
            nax = max(nax, score[start])
            j += 1
        loopn[start] = j
        for i in tuuka:
            done[i] = False
            loopn[i] = j
            score[i] = score[start]
            nokori = k-(k//loopn[start])*loopn[start]
    else:
        nax = 0
    if score[start] < 0:
        score[start] = nax
    else:
        score[start] = (k//loopn[start])*score[start]
        nokori = k-(k//loopn[start])*loopn[start]
        i = 0
        nnnnn = (k//loopn[start])
        nscore = 0
        nax = 0
        while i < nokori:
            nex = P[nex]-1
            nscore += C[nex]
            if C[nex] < 0:
                break
            nax = max(nax, nscore)
            i += 1
        if nax > 0:
            score[start] += nax


ans = max(score)
if ans <= 0:
    ans = max(C)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
Loop = [1] * N
Score = [0] * N
Ans = [0] * N
Y = [0] * N
for i in range(N):
  x = P[i] - 1
  y = C[i]
  X = [0] * N
  for j in range(N):
    x = P[x] - 1
    y += C[x]
    if X[x] != 0:
      Loop[i] = j + 1 - X[x]
      Y[i] = X[x]
      break
    else:
      X[x] = j + 1
  
    
  Score[i] = y

for i in range(N):
  a = K // Loop[i]
  b = K % Loop[i]
  x = i
  y = 0
  M = 0
  if a > 0 and b < Y[i] + Loop[i]:
    b = Loop[i]
    a = a - 1
  c = max(0, Score[i]) * a
  for j in range(b):
    x = P[x] - 1
    y += C[x]
    if j == 0 or y > M:
      M = y
  Ans[i] = c + M
print(max(Ans))

Submission status: Wrong Answer

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

P = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = 0
for p in P:
    tmp = 0
    for i in range(K):
        tmp += C[p-1]
        p = P[p-1]
        if ans < tmp:
            ans = tmp

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-


def solve():
    N, K = list(map(int, input().split()))
    Ps = list(map(int, input().split()))
    Cs = list(map(int, input().split()))

    # 最低一回は移動させないといけないの忘れてた
    ans = -float("inf")
    for i in range(N):
        ans = max(ans, Cs[i])

    if K == 1:
        print(ans)
        return

    loop_list = []
    for now in range(N):
        visited = set()
        visited.add(now)
        move = 0
        total_score = 0
        max_score = ans

        while True:  # たかだかN回
            nx = Ps[now]-1
            total_score += Cs[nx]
            max_score = max(max_score, total_score)
            move += 1
            if nx in visited:
                # 一周した
                if total_score > 0:
                    # 一周する価値あるので、loop_listに追加
                    loop_list.append((now, total_score, move))
                break

            # 一周してない
            if move == K:
                # もう移動できないので終わり
                break
            visited.add(nx)
            now = nx
        ans = max(ans, max_score)


    # 一周した方が得かつ、移動回数が余っているなら、ぐるぐる回る
    for s, score, move in loop_list:
        total_score = score*(K//move)
        restK = K % move
        max_score = total_score

        now = s
        while restK != 0:
            restK -= 1
            nx = Ps[now]-1
            total_score += Cs[nx]
            max_score = max(max_score, total_score)
            now = nx
        ans = max(ans, max_score)

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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


def read():
    N, K = map(int, input().strip().split())
    P = [0] + list(map(int, input().strip().split()))
    C = [0] + list(map(int, input().strip().split()))
    return N, K, P, C


def solve(N, K, P, C):
    max_score = -10**9
    for i in range(1, N+1):
        # 途中までのスコアの最大値をとるための移動距離
        d = 0
        # 途中までのスコアの最大値
        inter_score = -10**7
        # 1周の長さ
        size = 0
        # 1周のスコアの最大値
        round_score = -10**7
        j = i
        score = 0
        while True:
            size += 1
            score += C[P[j]]
            j = P[j]
            if score > inter_score:
                inter_score = score
                d = size
            if i == j:
                break
        round_score = score
        if K < d:
            continue
        else:
            max_score = max(max_score, inter_score)
        if K < size:
            continue
        else:
            max_score = max(max_score, round_score)
        # 周回してみる
        if i == 5:
            print(round_score, K / size, inter_score, d)
        if round_score > 0 and K >= size:
            if K % size <= d:
                base_score = round_score * (K // size)
                k = K % size
                j = i
                while k >= 0:
                    max_score = max(max_score, base_score)
                    base_score += C[P[j]]
                    j = P[j]
                    k -= 1
            else:
                max_score = max(max_score, round_score * (K // size))
    return max_score


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
def f(x):
  D=[-1]*(N+1)
  D[x]=0
  S=[None]*(N+1)
  S[x]=0
  ima=x+0
  for count in range(1, 5001):
    if D[P[ima]]<0:
      D[P[ima]]=D[ima]+1
      S[P[ima]]=S[ima]+C[P[ima]]
      ima=P[ima]+0
    else:
      if S[ima]+C[P[ima]]>S[P[ima]]:
        isshu=count-D[P[ima]]
        atonanshu=(K-count)//isshu
        atonanho=(K-count)%isshu
        agatta=S[ima]+C[P[ima]]-S[P[ima]]
        S[P[ima]]=S[ima]+C[P[ima]]+agatta*atonanshu
        D[P[ima]]=D[ima]+1
        
        ima=P[ima]+0
        for _ in range(atonanho):
          S[P[ima]]=S[ima]+C[P[ima]]
          D[P[ima]]=D[ima]+1
          ima=P[ima]+0
      break
      
  if D[x]==0:
    S[x]=None
  return max([s for s in S if s is not None])

N, K=map(int, input().split())
P=[None]+list(map(int, input().split()))
C=[None]+list(map(int, input().split()))

print(max([f(x) for x in range(1, N+1)]))

Submission status: Wrong Answer

Solution code:
import copy

datas = [int(i) for i in input().split(" ")]
N = datas[0]
K = datas[1]

P = [int(i) for i in input().split(" ")]
C = [int(i) for i in input().split(" ")]

sumData = []
nextData = copy.deepcopy(P)
tempData = []
total = [0] * N
cnt = 0
maxData = -1000000000

while cnt < K:
    cnt += 1
    for i in range(N):
        sumData.append(C[nextData[i] - 1])
        tempData.append(nextData[nextData[i] - 1])
        total[i] += sumData[i]

    nextData = copy.deepcopy(tempData)
    sumData = []
    tempData = []
    if maxData < max(total):
        maxData = max(total)

print(maxData)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
input = sys.stdin.readline
INF = float("inf")


# 処理内容
def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))

    ans = max(C)

    if K <= N:
        for i in range(N):
            score = 0
            v = P[i] - 1
            for _ in range(K):
                score += C[v]
                ans = max(score, ans)
                v = P[v] - 1
    else:
        for i in range(N):
            score = 0
            S = 0
            v = P[i] - 1
            for _ in range(N):
                S += C[v]
                ans = max(S, ans)
                v = P[v] - 1

            m = K // N
            q = K % N
            score += m * S
            ans = max(score, ans)

            for _ in range(q):
                score += C[v]
                ans = max(score, ans)
                v = P[v] - 1   
        
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

ans=-1*(10**10)
for i in range(N):
    tmp=0
    pos=i
    gpos=i
    count=0
    while count<K:    
        #print(pos,P[pos])
        tmp+=C[P[pos]-1]
        if tmp>ans:
            ans=tmp
        
        
        pos=P[pos]-1
        count+=1
        if pos==gpos and count!=K:
            divide=K//count
            tmp=tmp*divide
            count=count*divide
            gpos=10**10
        

print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    pd = {i: x for i, x in enumerate(p, 1)}
    cd = {i: x for i, x in enumerate(c, 1)}
    ans = -10 ** 10
    for i in range(1, n + 1):
        res = 0
        x = i
        for j in range(1, min(5001,k + 1)):
            res += cd[x]
            x = pd[x]
            ans = max(res, ans)
    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
INF = 10**18

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

ans = -INF
for start in range(N):
    T = K
    S = {start: 0}
    seq = {start: 0}
    t = start
    while T > 0 and not P[t]-1 in S:
        seq[P[t]-1] = seq[t] + 1
        S[P[t]-1] = S[t] + C[P[t]-1]
        ans = max(ans, S[P[t]-1])
        t = P[t] - 1
        T -= 1
    if T > 0:
        scoredelta = S[t] + C[P[t]-1] - S[P[t]-1]
        cycle = seq[t] + 1 - seq[P[t] - 1]
        score = S[P[t]-1]
        T += cycle - 1
        count = T // cycle - 1
        T -= count * cycle
        score += count * scoredelta
        ans = max(ans, score)
        t = P[t]-1
        while T > 0:
            score += C[t]
            ans = max(ans, score)
            t = P[t]-1
            T -= 1
print(ans)

Submission status: Wrong Answer

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

F=[0]*N
I=[0]*N
CN=[0]*N

for i in range(N):
  around=0
  cnt=0
  A=[]
  if F[i]==0:
    F[i]=1
    around+=1
    cnt+=C[i]
    nex=P[i]-1
    A.append(i)
    while F[nex]==0:
      A.append(nex)
      F[nex]=1
      around+=1
      cnt+=C[nex]
      nex=P[nex]-1
    for j in A:
      I[j]=around
      CN[j]=cnt
#print(F)
#print(I)
#print(CN)
ans=-(10**9)*2
for i in range(N):
  cnt=C[i]
  #動かす回数が一周に満たない時
  if (K+1)<=I[i]:
    d=0
    nex=i
    for j in range(K+1):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  #動かす回数が一周を超えるとき
  elif CN[i]<=0:
    d=0
    nex=i
    for j in range(I[i]):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  else:
    d=0
    nex=i
    for j in range(I[i]):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
    acnt=cnt
    bcnt=C[i]
    syuukai=(K+1)//I[i]
    nokori=(K+1)%I[i]
    syuukai-=1
    nokori+=I[i]
    d=0
    nex=i
    for j in range(nokori-1):
      d+=C[nex]
      nex=P[nex]-1
      bcnt=max(d,bcnt)
    bcnt+=syuukai*CN[i]
    cnt=max(acnt,bcnt,(syuukai+1)*CN[i])
  ans=max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
p.insert(0,0)
c=list(map(int,input().split()))
c.insert(0,0)
a=[]
ans=-100000000
for i in range(1,n+1):
  flg=0
  for aa in a:
    if p[i] in aa:
      flg=1
  if flg==0:
    t=[p[i]]
    while p[t[-1]] not in t:
      t.append(p[t[-1]])
    a.append(t)
for i in range(len(a)):
  for j in range(len(a[i])):
    a[i][j]=c[a[i][j]]
for i in range(len(a)):
  if k<=len(a[i]):
    tmp=list(a[i])
    tmp.extend(a[i])
    for j in range(len(a[i])):
      for l in range(j+1,k+1):
        ans=max(ans,sum(tmp[j:l]))
  else:
    tmp=list(a[i])
    tmp.extend(a[i])
    for j in range(len(a[i])):
      for l in range(j+1,k+1):
        ans=max(ans,sum(tmp[j:l]))
        ans=max(ans,sum(tmp[j:l])+((k-l+j)//len(a[i]))*sum(a[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
#hoge2
N, K = [int(_) for _ in input().split()]
P = [int(_) - 1 for _ in input().split()]
C = [int(_) for _ in input().split()]
child_parent = [0] * N
ans = -float('inf')
for p, c in enumerate(P):
    child_parent[c] = p
for i in range(N):
    f = i
    i_cnt = [None] * N
    i_cnt[i] = 0
    cnt_score = [0]
    score = 0
    cnt = 0
    loop = 0
    while True:
        cnt += 1
        if cnt > K:
            break
        i = P[i]
        score += C[i]
        if i_cnt[i] is not None:
            loop = 1
            break
        cnt_score += [score]
        i_cnt[i] = cnt
    if loop:
        cnt1 = i_cnt[i]
        score1 = cnt_score[cnt1]
        ans = max(ans, max(cnt_score[1:]))
        if score > score1:
            q, r = divmod((K - cnt1), cnt - cnt1)
            ans1 = (score - score1) * q + max(cnt_score[cnt1:cnt1 + r + 1])
            ans = max(ans, ans1)
    else:
        ans = max([ans] + cnt_score[1:])
print(ans)