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

frag, loop, lcnt = set(), [], []
for i in range(n):
    if i in frag:
        continue
    now, tmp, tmpc = i, [], 0
    while True:
        frag.add(now), tmp.append(now)
        now = p[now] - 1
        tmpc += c[now]
        if now in frag:
            loop.append(tmp * 2)
            lcnt.append(tmpc)
            break

lacc = []
for l in loop:
    tmp = [0]
    for li in l[1:]: 
        tmp.append(tmp[-1] + c[li])
    lacc.append(tmp)

ans = min(c)
for l, la, lc in zip(loop, lacc, lcnt):
    num = k % len(l) // 2
    for cnt in range(1, min(len(l) // 2 + 1, k + 1)):
        for i in range(len(l) - cnt - 1):
            tmp = la[i + cnt] - la[i]
            tmp2 = tmp + lc * (k // (len(l) // 2) - (cnt > num))
            ans = max(ans, tmp, tmp2)
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()))
c = [1] * N
s = [C[P[i]-1] for i in range(N)]
m = [[0] * (N+1) for i in range(N)]
for i in range(N):
    m[i][1] = (C[P[i]-1])
for i in range(N):
    j = i
    while P[j]-1 != i:
        j = P[j]-1
        c[i] += 1
        s[i] += C[P[j]-1]
        if  c[i] <= K:
            if s[i] > m[i][c[i]-1]:
                m[i][c[i]] = s[i]
            else:
                m[i][c[i]] = m[i][c[i]-1]
ans = max(C)
for i in range(N):
    if s[i] > 0:
        if  s[i] * (K//c[i]) + m[i][K%c[i]] > ans:
            ans = s[i] * (K//c[i]) + m[i][K%c[i]]
    else:
        if max(m[i][1:min(c[i]+1,K+1)]) > ans:
            ans = max(m[i][1:min(c[i]+1,K+1)])
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()))

ps = [p-1 for p in ps]

visited = []
coarses = []
scores = []
while True:
    if len(visited) == n:
        break

    now = list(set(ps) - set(visited))[0]
    coarse = []
    score = []
    s, pre_s = 0, 0
    lp_cnt = 0
    visited_ = []

    while True:
        nxt = ps[now]
        if nxt in visited_:
            if lp_cnt != 0:
                break
            lp_cnt += 1
            visited_ = []

        s += cs[now]
        if cs[now] > 0:
            score.append(dict(bgn=pre_s, now=s, max=s))

        for sc in score:
            sc["now"] = s
            if sc["now"] > sc["max"]:
                sc["max"] = sc["now"]

        coarse.append(nxt)
        visited_.append(nxt)
        now = nxt
        pre_s = s
    
    scores += score
    coarses.append(coarse)
    visited += visited_

s_cands = []
for score in scores:
    s_cands.append(score["max"] - score["bgn"])

for coarse in coarses:
    sm = 0
    for i in coarse:
        sm += cs[i]
    s_cands.append(sm * (k // len(coarse)))

print(max(s_cands))

Submission status: Wrong Answer

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

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)

class UnionFind:
	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())


def main():
	log = Logger(0)
	n, k = map(int, sys.stdin.readline().split())
	p = list(map(int, sys.stdin.readline().split()))
	c = list(map(int, sys.stdin.readline().split()))
	uf = UnionFind(n)
	max_score = -float("inf")
	for i in range(n):
		uf.union(p[i] - 1, i)
	log.print(uf.all_group_members())
	for i in range(n):
		cnt = k
		score = 0
		loop = uf.members(p[i]-1)
		log.print(loop)
		if k > len(loop):
			here = i
			loopsum = 0
			for j in range(len(loop)):
				here = p[here] - 1
				loopsum += c[here]
			assert i == here
			if loopsum > 0:
				score += loopsum * (k // len(loop))
				cnt %= len(loop)
		tmp_max_score = -float("inf")
		here = i
		for j in range(len(loop)):
			if j >= cnt:
				break
			here = p[here] - 1
			score += c[here]
			log.print(here, score)
			tmp_max_score = max(tmp_max_score, score)
		tmp_max_score = max(tmp_max_score, score)
		log.print(tmp_max_score)
		max_score = max(tmp_max_score, max_score)
	print(max_score)




	


main()

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)-1:
                j = i
                max_val = -INF
                iter = 0
                done = False
                while iter <= K:
                    if j >= len(loop):j=0
                    if (i != j and j) or done:
                        val += loop[j]
                        max_val = max(val, max_val)
                    j += 1
                    if not 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[0:rest+1])
            ans = max(ans, val)

    print(ans)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
n, k = [int(e) for e in input().split()]
p =  [int(e) for e in input().split()]
c =  [int(e) for e in input().split()]
 
 
t = k // n
k %= n
 
if k == 0:
    t -= 1
    k = n
 
w = sum(c)
if w > 0:
    s = w * t
else:
    s = 0
 
u = - 10 ** 9
for i in range(n):
    m = p[i] - 1
    l = [c[m]]
    for j in range(1, k):
        m = p[m] - 1
        l.append(l[-1] + c[m])
    l.sort()
    if l[-1] > u:
        u = l[-1]
 
print(s + u)

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

ans = -1000000000
for i in range(n):
    now = i
    j = 0
    visited = deque()
    score = deque([0])
    isLoop = True
    while now not in visited:
        visited.append(now)
        score.append(score[j] +c[p[now]-1])
        now = p[now]-1
        j += 1
        if j >= k:
            isLoop = False
            break
    ans = max(ans, max(list(score)[1:]))
    if isLoop and score[-1] > 0:
        loop_num = k//len(score)
        rest = k%len(score)
        ans = max(ans, max(list(score)[:rest+2])+loop_num*score[-1] )
        ans = max(ans, max(list(score))+(loop_num-1)*score[-1] )
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 start in range(N):
        now = start
        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
            now = nx
            if now in visited:
                # 一周した
                if total_score > 0:
                    # 一周する価値あるので、loop_listに追加
                    loop_list.append((start, total_score, move))
                break

            # 一周してない
            if move == K:
                # もう移動できないので終わり
                break
            visited.add(now)
        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:

n, k = map(int, input().split())
k = k
p = [0] * n
c = [0] * n
a = [0] * (n+1)
ans = [0] * n

p = list(map(int, input().split()))
c = list(map(int, input().split()))
for i in range(n):
    s = 0
    x = i
    roop = 0
    for j in range(n):
        s += c[x]
        a[j+1] = s
        x = p[x] - 1
        if x == i:
            roop = j + 1
            break
    if s <= 0:
        ans[i] = max(a[1:min(roop+1, k+1)])
        #print(a,roop)
    else:
        if k%roop  == 0:
            ans[i] = max(s * (k // roop) , s * (k // roop - 1) + max(a))
        else:
            ans[i] = max(s * (k // roop) + max(a[:k % roop+1]), s * (k // roop - 1) + max(a))
            #print(a[:k % roop+1])
print(max(ans))

Submission status: Wrong Answer

Solution code:
import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict as dd

def maxSumSubSizek(arr, k): 
    n = len(arr)
    res = 0
    for i in range(k): 
        res += arr[i] 

    curr_sum = res 
    for i in range(k, n): 
        curr_sum += arr[i] - arr[i-k] 
        res = max(res, curr_sum) 
    return res 

def main():
    n,k = map(int, input().split())
    perm = [0] + list(map(int, input().split()))
    sqscore = [0] + list(map(int, input().split()))


    ans = -10**10
    visited = [False]*(n + 1)
    for i in range(1, n + 1):
        if not visited[i]:
            cycleScores = []
            j = i
            cycsum = 0
            maxsum = -10**10
            while not visited[j]:
                visited[j] = True
                score = sqscore[j]
                cycsum += score
                maxsum = max(maxsum, score)
                cycleScores.append(sqscore[j])
                j = perm[j]
            
            if maxsum <= 0:
                # All numbers are negative/0; take one step.
                ans = max(ans, maxsum)
            else:
                # positive numbers exist in cycle
                if k > len(cycleScores):
                    if cycsum <= 0:
                        temp = cycleScores + cycleScores
                        msf = cycleScores[0]
                        for i in temp[1:]:
                            msf = max(msf + i, i)
                            ans = max(ans, msf)
                    else:
                        # finish k/len(cycScores) cycles. Whatever is left, find subarray with max sum of that length
                        ogk = k
                        mult = k // len(cycleScores)

                        tempans = mult * cycsum
                        k -= mult * len(cycleScores)
                        
                        # find subarray of size k with in cycleScore with max Sum.
                        temp = cycleScores + cycleScores
                        for step in range(1, k + 1):
                            ans = max(ans, tempans + maxSumSubSizek(temp, step))

                        k = ogk
                        k -= (mult - 1) * len(cycleScores)
                        tempans = (mult - 1) * cycsum
                        temp = cycleScores + cycleScores
                        for step in range(1, k + 1):
                            ans = max(ans, tempans + maxSumSubSizek(temp, step))
                        
                else:
                    temp = cycleScores + cycleScores
                    for step in range(1, k + 1):
                        ans = max(ans, maxSumSubSizek(temp, step))
    print(ans)


        




































# region fastio
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# endregion
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#import numpy as np
#import collections
#import math
import copy

#f = open('./input_D.txt')
#
#N,K=map(int, f.readline().split())
#P=list(map(int, f.readline().split()))
#C=list(map(int, f.readline().split()))


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

def BestScore(p_cyc,k):
    score = -10**10
    len_p_cyc = len(p_cyc)
    p_cyc2 = copy.deepcopy(p_cyc)
    p_cyc2.extend(p_cyc[:k])
    for k_use in range(1,k+1):
        for i in range(len_p_cyc):
            p_use = p_cyc2[i:i+k_use]
            kouho=0
            for p in p_use:
                kouho += C[p-1]
            if kouho > score:
                score = kouho
    return score

Pcopy = copy.deepcopy(P)
P_cyc = []
Pcount=0
while Pcount < N:
    P_cyc.append([])
    startP = Pcopy[0]
    appendP = Pcopy[0]
    conti=True
    while conti:
        appendP = P[appendP-1]
        P_cyc[-1].append(appendP)
        Pcopy.pop(Pcopy.index(appendP))
        Pcount+=1
        if appendP == startP:
            conti=False

C_cyc = []
for cycle in P_cyc:
    score=0
    for p in cycle:
        score+=C[p-1]
    C_cyc.append(score)
    
ans= -10**10
for m,c_cyc in enumerate(C_cyc):
    Km = K
    ans_kouho = 0
    p_cyc = P_cyc[m]
    len_p_cyc = len(p_cyc)
#    print(len_p_cyc)
    if C_cyc[m] > 0:
        num_cyc = Km//len_p_cyc
#        print(num_cyc)
        ans_kouho += num_cyc * c_cyc
        Km -= num_cyc*len_p_cyc
    else:
        Km = len_p_cyc
    ans_kouho += BestScore(p_cyc,Km)
    
    if ans_kouho > ans:
        ans = ans_kouho

print(ans)

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 for i in range(N+1)]
        # 1周の長さ
        size = 0
        # 1周のスコアの最大値: D[size]
        j = i
        score = 0
        while True:
            size += 1
            j = P[j]
            D[size] = D[size-1] + C[P[j]]
            if i == j:
                break
        round_score = D[size]
        for i in range(1, min(K, size)+1):
            max_score = max(max_score, D[i])
        # 周回してみる
        if D[size] > 0 and K > size:
            base_score = round_score * (K // size)
            max_score = max(max_score, base_score)
            for i in range(1, min(K%size, size)+1):
                max_score = max(max_score, base_score + D[i])
    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:
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 = -10e10
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 = -10e10
            lplp = loop + loop
            for i in range(1,amari+1):
                for j in range(le):
                    ma = max(ma,sum(lplp[j:j+i]))
            tmp += ma
            ans = max(ans,tmp)
        if su <= 0:
            ma = -10e10
            lplp = loop + loop
            for i in range(1,le+1):
                for j in range(le):
                    ma = max(ma,sum(lplp[j:j+i]))
            ans = max(ans,ma)
    else:
        ma = -10e10
        lplp = loop + loop
        for i in range(1,k+1):
                for j in range(le):
                    ma = max(ma,sum(lplp[j:j+i]))
        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()))

s = -10**10
l = k % 5000
m = k // 5000
tc = sum(c)
if tc < 0:
    tc = 0

for i in range(n):
    e = 0
    f = -10**10
    d = p[i]
    for j in range(l):
        e = e + c[d-1]
        d = p[d-1]
        if f < e:
            f = e
    if s < f:
        s = f

ans = m * tc + s

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 = []
count2 = []
for i in range(n):
    ans2 = []
    syote = i
    count = 0
    for j in range(min(k, n)):
        count += c[p[syote]-1]
        ans2.append(count)
        syote = p[syote]-1
    count2.append(count)
    ans.append(max(ans2))
aaa = max(ans)
if k <= n:
    print(aaa)
# else:
#     kaisuu = k//n
#     amari = k % n

#     ans4 = []
#     count2 = []
#     for i in range(n):
#         ans2 = []
#         syote = i
#         count = 0
#         for j in range(amari):
#             count += c[p[syote]-1]
#             ans2.append(count)
#             syote = p[syote]-1
#         count2.append(count)
#         ans4.append(max(ans2))
#         print(ans4)
#     print(ans)
#     for i in range(len(ans)):
#         ans[i] *= kaisuu
#         ans[i] += ans4[i]
#     print(max(ans))

Submission status: Wrong Answer

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

def big(m,l,init=-10**9):
    ret = -10**9
    ll = l + l + l
    """
    for i in range(1,m+1):
        ret_ = sum(ll[:i])
        su = ret_
        for j in range(len(l)):
            su += ll[i+j] - ll[j]
            ret_ = max(ret_,su)
        ret = max(ret,ret_)
    """
    return max(ret,init)

visited = [False]*n

def dfs(l,v):
    if visited[v]:
        return l
    visited[v] = True
    return dfs(l + [c[v]],p[v])

ret = -10**9
for i in range(n):
    #l = dfs([],i)
    l = c
    #print(l)
    if len(l) == 0:
        continue
    if k//len(l) > 0:
        ret = max(ret,sum(l)*(k//len(l))+big(k%len(l),l,init=0))
        ret = max(ret,big(len(l),l))
        ret = max(ret,sum(l)*(k//len(l)-1)+big(len(l),l))
    else:
        ret = max(ret,big(k,l))

print(ret)

Submission status: Wrong Answer

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

r=[[0]*n for ii in range(k)]

for ii in range(n):
  ct=[0]*n
  tempr=0
  tempx=ii
  for jj in range(k):
    tempx=p[tempx]-1
    ct[tempx]+=1
    tempr+=c[tempx]
    if jj==0:
      tempp=tempr
    else:
      tempp=max(tempp,tempr)
    if ct[tempx]>2:
      # ToDo
      # tempp+=diff_tempp*(k-jj)//jj+r_tempp[(k-jj)%jj]
      break
    
  if ii==0:
    rr=tempp
  else:
    rr=max(rr,tempp)
print(rr)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))
INF = 10**18
ans = -INF
for i in range(N):
    ans2 = -INF
    tot = 0
    rest = K
    visited = {}
    visited[i] = rest
    point = {}
    point[i] = 0
    nex = i
    while rest:
        nex = P[nex]
        tot += C[nex]
        ans2 = max(ans2, tot)
        rest -= 1
        if nex in visited:
            loop = visited[nex]-rest
            loop_point = tot-point[nex]
            rest2 = min(rest, loop)
            nex2 = nex
            tot2 = tot
            while rest2:
                nex2 = P[nex2]
                tot2 += C[nex2]
                ans2 = max(ans2, tot2)
                rest2 -= 1
            if loop_point > 0:
                tot += (rest//loop)*loop_point
                ans2 = max(ans2, tot)
                rest = rest%loop
                while rest:
                    nex = P[nex]
                    tot += C[nex]
                    ans2 = max(ans2, tot)
                    rest -= 1
            break
        else:
            visited[nex] = rest
            point[nex] = tot
    ans = max(ans, ans2)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
C=list(map(int,input().split()))
class UnionFind():
    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())

Q=[]
uf=UnionFind(N)
for i in range(N):
    uf.union(i,P[i]-1)
D1=list(uf.all_group_members().values())
D2=[]
for i in D1:
    ans=0
    for j in i:
        ans+=C[j]
    D2.append(ans)
L=[len(i) for i in D1]
S=min(2*max(L),K)

for i in range(N):
    ans=-float('inf')
    ans1=0
    now=P[i]-1
    for j in range(S):
        ans1+=C[now]
        now=P[now]-1
        ans=max(ans1,ans)
    Q.append(ans)
    
if K>=min(L):
    for i,value in enumerate(D2):
        if value>0:
            ans3=value*(K//L[i])
            for j in D1[i]:
                ans=0
                ans1=0
                now=P[j]-1
                for k in range(K%L[i]):
                    ans1+=C[now]
                    now=P[now]-1
                    ans=max(ans1,ans)
                Q.append(ans3+ans)
print(max(Q))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
p = [int(x)-1 for x in input().split()]
c = list(map(int, input().split()))
realans = -1001001001
for i in range(n):
    count = 0
    now = i
    score = 0
    for _ in range(n):
        if now == i and count != 0:
            break
        now = p[now]
        count += 1
        score += c[now]
    ans = 0
    ans += score * (k // count-1)
    nk = k % count+ count
    if ans < 0:
        if nk == 0:
            nk = 2*count
        ans = 0

    maxim = -1001001001
    now = i
    tmp = 0
    for j in range(nk):
        now = p[now]
        tmp += c[now]
        maxim = max(maxim, tmp)
    ans += maxim
    realans = max(realans, ans)
print(realans)

Submission status: Wrong Answer

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

minusOnly = True
for i in range(n):
    if c[i] > 0:
        minusOnly = False
        break

if minusOnly:
    # print(max(c))
    exit()

ans = 0
used = [False]*n

for st in range(n):
    if not used[st]:
        gr = []
        now = st
        gr.append(st)
        used[st] = True
        while True:
            now = p[now]
            gr.append(now)
            used[now] = True
            if now == st:
                break
        gr.pop()

        cs = [c[i] for i in gr]
        s = sum(cs)
        point = 0
        r = k
        if k > len(gr):
            if s > 0:
                point += s*(k//len(gr))
                r -= len(gr)*(k//len(gr))
            else:
                r = len(gr)
        

        cs = cs + cs
        plus = 0
        for i in range(len(gr)):
            nowSum = 0
            for g in range(r):
                nowSum += cs[i+g]
                plus = max(plus, nowSum)
        
        point += plus
        ans = max(ans, point)

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) :
    log = [i+1]
    t = 0
    b = 0
    a = i+1
    while len(log) == len(set(log)) and t < K :
        b += C[P[a-1]-1]
        ans = max(ans,b)
        t += 1
        log.append(P[a-1])
        a = P[a-1]

    if b >= 1 and t < K :
       d = (K-t)%t
       e = (K-t)//t
       f = b*e
       ans = max(ans,f)
       for _ in range(d) :
           f += C[P[a-1]-1]
           a = P[a-1]
           ans = max(ans,f)

print(ans)