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()))

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]
    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 = -float("inf")
        while i < nokori:
            nex = P[nex]-1
            nscore += C[nex]
            nax = max(nax, nscore)
            i += 1
        if nnnnn == 0 and nax < 0:
            score[start] += nax
        elif 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()))
list = []
for i in range(n):
  s = 0
  m = 0
  for j in range(k):
    i = p[i]-1
    s += c[i]
    m = max(m, s)
    list.append(m)
print(max(list))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

P = [p - 1 for p in P]
SB = defaultdict(int)

sumC = sum(C) 

if sumC > 0:
  d, k = divmod(k, n)
  if d > 0:
    pscore = (d - 1) * sumC
    k += n 
  else:
    pscore = 0
else:
  k = min(k, n * 2)
  pscore = 0

for p in P: 
  cnt = 0
  score = 0
  mv = - 10 ** 19
  s = p
  while cnt < k:
    score += C[s]
    s = P[s]
    cnt += 1
    mv = max(mv, score)
  
  SB[p] = mv

ans = max(SB.values()) + pscore
print(ans)

Submission status: Wrong Answer

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


def start_game(cursor_masu):
    print("-" * 10 + str(cursor_masu) + "-" * 10)
    # initialize
    visit_count = [0 for _ in range(N + 1)]
    point = 0
    points = list()

    # move
    for _ in range(K):
        cursor_masu = masues[cursor_masu]
        if visit_count[cursor_masu] >= 1 and point < 0:
            break

        point += masu_points[cursor_masu]
        points.append(point)

        visit_count[cursor_masu] += 1

    return points


result = list()
for i in range(1, N + 1):
    result += start_game(i)
print(max(result))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 63


def run():
    N, K = map(int, sysread().split())
    P = list(map(int, sysread().split()))
    C = list(map(int, sysread().split()))
    P = [p-1 for p in P]

    loops = []
    checked = [0] * N
    loop = [0]
    for i in range(N):
        current = i
        while True:
            if not checked[current]:
                checked[current] = 1
                loop.append(C[current])
                current = P[current]
            else:
                if len(loop) == 1:break
                loops.append(loop)
                loop = [0]
                break
    loopSums = []
    for loop in loops:
        val = 0
        tmp = []
        for l in loop:
            val += l
            tmp.append(val)
        loopSums.append(tmp)
    #print(loops)
    #print(loopSums)
    ans = -INF
    for loop, loopSum in zip(loops, loopSums):
        for i in range(1, len(loop)):
            val = 0
            if loopSum[-1] < 0 or K <= len(loop)-2:
                j = i
                max_val = -INF
                iter = 0
                done = False
                while iter <= K:
                    if j >= len(loop):j=0
                    if i != j and j:
                        val += loop[j]
                        max_val = max(val, max_val)
                    j += 1
                    iter += 1
                    if done : break
                    if i == j: done = True
                ans = max(ans, max_val)
                continue


            rest = K
            #if K <= len(loop) - i - 1:
            #    val += loopSum[i + K - 1] - loopSum[i]
            #    ans = max(ans, val)
            #    continue
            rest -= len(loop) - i - 1
            val += loopSum[-1] - loopSum[i]
            val += (rest // (len(loop)-1)) * loopSum[-1]
            rest = rest % (len(loop) - 1)
            val += max(loopSum[:rest+1])
            ans = max(ans, val)

    print(ans)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, P: "List[int]", C: "List[int]"):

    if K > N-1:
        temp_max = C[0]
        for i in range(N):
            score_i = [0]*N 
            score_i_max = [0]*N
            h = P[i]-1
            score_i[0] = C[h]
            score_i_max[0] = C[h]
            if h == i: break
            for j in range(1, N):
                h = P[h]-1
                score_i[j] = score_i[j-1] + C[h]
                score_i_max[j] = max(score_i[j-1], score_i[j])
                if h == i: break

            # print(score_i)
            mod_k = K % (j+1)
            rat_k = K //(j+1)
            if score_i[j] > 0:
                t = rat_k * score_i[j] + max(0,(score_i_max[mod_k-1]))
                temp_max = max(t, temp_max)
            else:
                temp_max = max(score_i_max[j], temp_max)

        print(temp_max)
    
    elif K <= N:
        score = [[0]*N for i in range(N)]
        temp_max = C[0]
        for i in range(N):
            h = i
            for j in range(1, K):
                h = P[h]-1
                score[i][j] = score[i][j-1] + C[h]
                temp_max = max(score[i][j], temp_max)
        print(temp_max)


    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, P, C)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
lst1 = [ int(i) for i in input().split()]
lst2 = [ int(i) for i in input().split()]
visited = [0]*n
count = 0
count_lst = []
x = 0
while True:
    count += lst2[x-1]
    visited[x-1] = 1
    if visited[x-1] != 0:
        for i, num in enumerate(visited):
            if num == 0:
                x = i
                count_lst.append(count)
        break
    else:
        x = lst1[x-1]
print(max(count_lst))

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 n in range(N):
    ans_pre = 0
    for _ in range(K):
        index = P[n] - 1
        ans_pre += C[index]
        n = index
        ans = max(ans, ans_pre)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
p_lis = list(map(int, input().split()))
score_lis = list(map(int, input().split()))

visited = [False]*n
# same_group = [False]*n

ans = -10**9


for start in range(n):
    visited = [False]*n
    point_tmp = 0
    visited[start] = True
    # same_group[start] = True
    tmp = start

    for i in range(k):
        tmp = p_lis[tmp-1]
        point_tmp += score_lis[tmp-1]
        visited[tmp-1] = True
        # same_group[tmp-1] = True
        
        if point_tmp > ans:
            ans = point_tmp

        # ループ
        if tmp == start:
            if point_tmp > 0:
                p_cycle = point_tmp
                l = visited.count(True)
                t = k//l
                amari = k%l
                point_tmp = 0
                tmp = start
                for j in range(l):
                    tmp = p_lis[tmp-1]
                    point_tmp += score_lis[tmp-1]

                    if j+1 <= amari:
                        ans = max(ans, point_tmp+p_cycle*(t))
                    else:
                        ans = max(ans, point_tmp+p_cycle*(t-1))
            break

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

ans = -float("inf")
for i in range(N):
    score_acc = [L[i]]
    cur = P[i] - 1
    while cur != i:
        score_acc.append(L[cur])
        cur = P[cur] - 1
    score_acc = list(accumulate(score_acc))
    M = len(score_acc)
    if M < K and score_acc[-1] > 0:
        res = K // M * score_acc[-1]
        if K % M:
            res += max(score_acc[: K % M])
        else:
            res += -score_acc[1] + max(score_acc)
        ans = max(ans, res)

    else:
        res = max(score_acc[:K])
        ans = max(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 21:20:49 2020

@author: NEC-PCuser
"""

N, K = map(int, input().split())

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

X = [0] * N
c_li = []
position = 0 
sum_li = []
for i in range(len(P)):
	if X[i] == 1:
		continue
	position = i
	li = []
	sum_l = 0
	for j in range(len(P)):
		X[position] = 1
		li.append(C[position])
		position = P[position] - 1
		sum_l += C[position]
		if position == i:
			c_li.append(li)
			sum_li.append(sum_l)
			break

Submission status: Wrong Answer

Solution code:
def main():
    n,k = map(int, input().split())
    p = [int(v)-1 for v in input().split()]
    c = [int(v) for v in input().split()]
    groups = []
    nums = set(list(range(n)))
    while len(nums)>0:
        num = nums.pop()
        s = set([num])
        nn = num
        while p[nn] != num:
            s.add(p[nn])
            nn = p[nn]
            nums.remove(nn)
        groups.append(s)
    # print(groups)
    
    ans = -(1<<63)
    for s in groups:
        cnt = len(s)
        mul = k // cnt
        cnt2 = k % cnt
        if mul>0:
            mul -= 1
            cnt2 += cnt
        for c2 in range(1,cnt2+1):
            if mul>0:
                add = sum([c[i] for i in s])*mul
                if add<0:
                    add = 0
            else:
                add = 0
            
            sl = list(s)
            # print(cnt, sl, [c[i] for i in sl], add, c2, ans)
            ss = [0] * cnt
            ss[0] = sum([c[i] for i in (sl+sl)[:c2]]) + add
            ans = max(ans, ss[0])
            for i in range(1,cnt):
                # print('n',ss[i-1],c[sl[i-1]],c[sl[(i-1+c2)%cnt]], i, (i-1+c2)%cnt)
                ss[i] = ss[i-1]-c[sl[i-1]]+c[sl[(i-1+c2)%cnt]]
                ans = max(ans, ss[i])
            # print(ss)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
def simulate(n, k, p, c):
    score = min(c) * n
    for start in range(n):
        cs = 0
        cm = 0
        m = start
        for i in range(k):
            m = p[m]
            cs += c[m]
            cm = max(cs, cm)
        score = max(cm, score)
    print(score)


def loop(n, k, p, c):
    scores = []
    seen = set()
    for start in range(n):
        m = start
        ls = []
        while m not in seen:
            ls.append(c[m])
            seen.add(m)
            m = p[m]
        seen.add(m)
        if ls:
            scores.append(ls)
    ans = min(c) * n
    for si in scores:
        pc = sum(sij for sij in si if sij > 0)
        nc = sum(sij for sij in si if sij < 0)
        if pc > 0:
            l = k // len(si)
            m = k % len(si)
            ls = (pc + nc) * l
            ms = sum(si[:m])
            msi = ms
            for i in range(len(si)):
                msi = msi - si[i % len(si)] + si[(i + m) % len(si)]
                ms = max(msi, ms)
            ans = max(ms + max(ls, 0), ans)
        else:
            ans = max(max(si), ans)
    print(ans)


def main():
    n, k = map(int, input().split())
    p = [int(i) - 1 for i in input().split()]
    c = [int(i) for i in input().split()]
    if n > k:
        simulate(n, k, p, c)
    else:
        loop(n, k, p, c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
r = []
visit = [0] * n
for i in range(n):
    if not visit[i]:
        x = []
        j = i
        while True:
            if visit[j]:
                break
            x.append(c[j])
            visit[j] = 1
            j = p[j] - 1
        r.append(x)
l = len(r)
ans = -1145141919810
for x in r:
    ll = len(x)
    y = [0] * (ll + 1)
    for i in range(ll):
        y[i + 1] = y[i] + x[i]
    sumx = y[ll]
    a = 0
    kk = k
    #print(kk, ll)
    if ll < kk:
        if sumx > 0:
            a = (kk // ll) * sumx
        kk -= ll * (kk // ll)
    #print(a, kk, ll, sumx)
    b = -1145141919810
    #print(y)
    for i in range(1, kk + 1):
        for j in range(ll + 1 - i):
            #print(i + j, j)
            b = max(y[i + j] - y[j], b)
    for i in range(kk - 1):
        for j in range(i + 1):
            #print(ll - 1 - (j - 1), 1 + (i - j))
            b = max(y[ll] - (y[ll - 2 - (j - 1)] - y[1 + (i - j)]), b)
    ans = max(a + b, 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()))

ans = max(C)
for i in range(N):
    s = P[i]-1
    l = [C[i]]
    while s != i:
        l.append(C[s])
        s = P[s]-1
    if sum(l) > 0:
        c = K//len(l)*sum(l)
        n = K%len(l)
        ans = max(ans,c)
        s = i
        x = 0
        for j in range(n):
            s = P[s]-1
            x += C[s]
            ans = max(ans,c+x)
    else:
        n = min(len(l),K)
        s = i
        x = 0
        for j in range(n):
            s = P[s]-1
            x += C[s]
            ans = max(ans,x)
            
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

class Doubling:
    def __init__(self, lst, max_step):
        self.lst = lst
        self.max_step = max_step
        self.k = int(log2(max_step * 2 - 1)) + 1
        # print(self.k)
        self.D = self.create()

    def create(self):
        len_ = len(self.lst)
        D = [[-1] * len_ for _ in range(self.k)]
        D[0] = self.lst
        d = 2
        for i in range(1, self.k):
            for j in range(len_):
                D[i][j] = D[i - 1][D[i - 1][j]]
            d *= 2
        # print(D)
        return D

    def step(self, start, step):
        v = start
        for i in range(self.k, -1, -1):
            l = 1 << i
            if l <= step:
                v = self.D[i][v]
                # print(i, l)
                step -= l
        return v

def solve():
    N, K = MI()
    P = LI1()
    C = LI()

    ans = -INF
    for i in range(N):
        S = [0] * (N+1)
        used = [0] * N
        used[i] = 1
        mxs = [-INF] * (N+1)
        step = 0
        while 1:
            next = P[i]
            step = step + 1
            score = S[step-1] + C[next]
            S[step] = score
            mxs[step] = max(mxs[step-1], score)
            # ans_l = max(ans_l, S[step])
            if step == K:
                # print(mxs, mxs[K])
                ans = max(ans, mxs[K])
                break
            if used[next]:
                left = K - step
                # print(next, S, step, S[step], left)
                p = left // step
                q = left % step
                # print(mxs, p, q)
                # 現在の最高得点で打ち切る
                ans = max(ans, mxs[step])

                # さらにスコアを伸ばす
                ans = max(ans, S[step] + max(0, mxs[step]))
                ans = max(ans, S[step] * (p+1) + max(0, mxs[q]))

                # plus = max(S[step] * p + max(0, mxs[q]), mxs[step])
                # ans = max(ans, max(mxs[step], S[step] + mxs[step] * p + mxs[q]))
                # ans = max(ans, max(mxs[step], S[step] + max(0, plus)))
                break
            used[next] = 1
            i = next
    print(ans)

    
if __name__ == '__main__':
    solve()

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,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 = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
x = 0
y = 1
ans = -10 ** 9
k = K


for i in range(N):
    x = P[i]
    while K > 0:
        y += C[x - 1]
        x = P[x - 1]
        
        K -= 1
        
        

        ans = max(ans, y)
    y = 0
    K = k

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# map(int, input().split())

def junkan_max_score(junkan, C, K):
    ruiseki = [0]
    for i in range(len(junkan)):
        if i < len(junkan)-1:
            j = junkan[i+1]
        else:
            j = junkan[0]
        ruiseki.append(ruiseki[-1]+C[j])

    n_junkan = int(K/len(junkan))
    if n_junkan == 0:
        return max(ruiseki[1:K+1])
    elif ruiseki[-1] <= 0:
        return max(ruiseki[1:])
    else:
        junkan_score = n_junkan*ruiseki[-1]
        nokori_K = K-(n_junkan*len(junkan))
        if nokori_K == 0:
            return junkan_score
        else:
            return junkan_score+max(ruiseki[1:nokori_K+1])
        

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

p_junkan = {i:[] for i in range(1,N+1)}

for i, lst in p_junkan.items():
    j = P[i-1]
    while j != i:
        lst.append(j-1)
        j = P[j-1]
    lst.append(i-1)

junkan_max = [junkan_max_score(lst, C, K) for i,lst in p_junkan.items()]
print(max(junkan_max))

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            #根を探す&つなぎかえる
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

        def size(self, x):
            return -self.parents[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    ################


    mod=10**9+7
    N,K=MI()
    P=LI()
    C=LI()
    
    for i in range(N):
        P[i]-=1
    
    uf =UnionFind(N)
    for i in range(N):
        uf.union(i,P[i])
        
    from collections import defaultdict
    dd = defaultdict(list)
        
    for i in range(N):
        root=uf.find(i)
        dd[root]+=[i]
        
    ansAll=-1*(10**10)
    for k,v in dd.items():
        N2=len(v)
        #rootから移動した時の点数の順番，2周分
        L=[0]*(2*N2+3)
        now=k
        for i in range(2*N2+3):
            nxt=P[now]
            L[i]=C[nxt]
            now=nxt
        S=[0]*(2*N2+3)
        for i in range(2*N2+2):
            S[i+1]=S[i]+L[i]
        
        ans=0
        
        ROOP=S[N2]-S[0] 
        if ROOP>0:#1週分
            roop=K//N2
            ans+=ROOP*roop
            rem=K%(N2)
        else:
            roop=0
            rem=min(K,N2)
            
        if roop==0:
            temp=-1*(10**10)
        else:
            #1回以上ループしていれば，追加で1こも取る必要はない
            temp=0
        for i in range(1,rem+1):#i個トル
            for j in range(N2+1):#jからスタート
                s=S[j+i]-S[j]
                temp=max(temp,s)
        ans=ans+temp
        
        # print(k,v,roop,rem)
        # print(L)
        # print(S)
        # print(temp,ans)
        # print("---")
        
        
        ansAll=max(ansAll,ans)
        
    print(ansAll)
        
            
    
 
        
    
            
    

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n,K=list(map(int,input().split()))
ps=list(map(int,input().split()))
cs=list(map(int,input().split()))


group=[-1]*n
cnt=0
for i in range(len(ps)):
    tmp=i
    check=0
    while True:
        if group[tmp]!=-1:
            break
        check=1
        group[tmp]=cnt
        tmp=ps[tmp]-1
    if check!=0:
        cnt+=1

anses=[]
for i in range(cnt):
    position=group.index(i)
    scores=[cs[position]]
    while ps[position]-1!=group.index(i):
        position=ps[position]-1
        scores.append(cs[position])
    vals=np.array(scores.copy())
    length=len(scores)
    scores=scores+scores

    ans=0
    if sum(vals)>0:
        ans+=K//length*sum(vals)
        remain=K%length
    else:
        if K>length:
            remain=K%length
        else:
            remain=K

    m=max(vals)
    for j in range(1,remain):
        vals+=scores[j:j+length]
        if m<max(vals):
            m=max(vals)
    ans+=m
    anses.append(ans)
print(max(anses))

Submission status: Wrong Answer

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

N,K=(int(x) for x in input().rstrip('\n').split())
Ps = [int(x)-1 for x in input().rstrip('\n').split()]
Cs = [int(x) for x in input().rstrip('\n').split()]
res = -10**9-1
for i in range(N):
  next = Ps[i]
  cycle = Cs[next]
  steps =[cycle]
  for a in range(K):
    next = Ps[next]
    cycle += Cs[next]
    steps.append(cycle)
    if next == i:
      if cycle>0:
        if K%len(steps)!=0:
          now = (K//(len(steps)))*cycle+max(steps[:K%(len(steps))])
          if now>res:
            res = now
          break
        else:
          now =(K//len(steps))*cycle
          if now>res:
            res = now
          break
      else:
        now = max(steps)
        if now>res:
            res = now
        break
    if a==K-1:
      now = max(steps)
      if now>res:
        res = now
print(res)

Submission status: Wrong Answer

Solution code:
def roop(i,K):
    isroop=False
    last=[-1]*N
    lastcnt=[-1]*N
    n=i
    last[n]=0
    lastcnt[n]=0
    roopp=-1#ループ1回のポイント
    cnt=0
    rs=-1#ループ開始
    maxp=-10**30
    point=0
    while(True):
        cnt+=1
        n=P[n]
        point+=C[n]
        maxp=max(maxp,point)
        if last[n]!=-1:
            roopp=point-last[n]
            syuki=cnt-last[n]#ループ周期
            isroop=True
            rs=n
            start=last[n]
            break
        last[n]=point
        lastcnt[n]=cnt
        if cnt==K:
            break
    if not isroop:
        return  maxp
    if roopp<0:
        return maxp
    K-=lastcnt[rs]
    roopcnt=K//syuki
    allpoint=(K//syuki)*roopp
    K%=syuki
    j=0
    n=rs
    point=0
    maxpp=0
    while(j<K):
        j+=1
        n=P[n]
        point+=C[n]
        maxpp=max(maxpp,point)
    if rs!=i:
        return max([start,start+allpoint,start+allpoint+maxpp,start+allpoint-roopp+maxpp])
    else:
        if roopcnt>1:
            return max([allpoint,allpoint+maxpp,maxp,allpoint-roopp+maxpp])
        else:
            return max([allpoint,allpoint+maxpp,maxp])
        
        
        

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

ans=-10**30
for i in range(N):
    r=roop(i,K)
    ans=max(ans,r)
print(ans)

Submission status: Wrong Answer

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


inf = float("inf")


ans = max(C)  # at least one move
for pos in range(N):
    i = pos
    score = 0
    cycleLen = None
    cycleGain = None
    bestInc = 0
    k = 0
    while k < K:
        i = P[i]
        score += C[i]
        ans = max(ans, score)

        if i == pos:
            cycleLen = k + 1
            numCycles = max(0, (K - k) // cycleLen)
            if k + numCycles * cycleLen < K:
                k += numCycles * cycleLen
                score += numCycles * score
        k += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 17:00:46 2020

@author: saito
"""

# %% import phase

# %% define phase    

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

# %% process phase
P.insert(0, -1)
C.insert(0, -1)

mscore = 0
for si in range(N):
    nscore = 0
    i = si+1
    for _ in range(K):
        i = P[i]
        nscore += C[i]
        mscore = max(mscore, nscore)

# %%output phase
print(mscore)