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:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

# https://note.nkmk.me/python-union-find/

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():
    n, k = ns()
    p = na1()
    c = na()

    uf = UnionFind(n)
    for i, pi in enumerate(p):
        uf.union(i, pi)

    cycledist = [[-INF for _ in range(2)] for __ in range(n)]
    for lis in uf.all_group_members().values():
        if cycledist[lis[0]][0] != -INF:
            continue
        tmp = 0
        l = len(lis)
        for idx in lis:
            tmp += c[idx]
            cycledist[idx][1] = l

        for idx in lis:
            cycledist[idx][0] = tmp

    ans = -INF

    for i in range(n):
        tmp_ans = cycledist[i][0] * (k // cycledist[i][1])

        tmp = 0
        idx = i
        for _ in range(k % cycledist[i][1]):
            tmp += c[p[idx]]
            idx = p[idx]
            # if _ < k % cycledist[i][1]:
            ans = max(ans, tmp, tmp + tmp_ans)
            # else:
            #     ans = max(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
l = []
check = [True]*n
for i in range(1,n+1):
    if (check[i-1]==True):
        s = i
        sl = []
        tnp = i
        for j in range(n):
            tnp = p[tnp-1]
            check[tnp-1] = False
            sl.append(c[tnp-1])
            if (tnp==s):
                break
        l.append(sl)
#print(l)
ans = -float("inf")
for i in range(len(l)):
    if (len(l[i])<=k):
        if (sum(l[i])>0):
            x = k%len(l[i])
            if (x==0):
                tnp = 0
            else:
                tnp = -float("inf")
            for p in range(1,x+1):
                wa = sum(l[i][:p])
                tnp = max(tnp,wa)
                for j in range(len(l[i])):
                    wa -= l[i][j]
                    wa += l[i][(j+p)%len(l[i])]
                    tnp = max(tnp,wa)
            ans = max(ans, tnp + sum(l[i])*(k//len(l[i])) )
        else:
            tnp = -float("inf")
            for p in range(1,len(l[i])):
                wa = sum(l[i][:p])
                tnp = max(tnp,wa)
                for j in range(len(l[i])):
                    wa -= l[i][j]
                    wa += l[i][(j+p)%len(l[i])]
                    tnp = max(tnp,wa)
            ans = max(ans, tnp)
    tnp = -float("inf")
    for p in range(1,min(k,len(l[i]))+1):
        wa = sum(l[i][:p])
        tnp = max(tnp,wa)
        for j in range(len(l[i])):
            wa -= l[i][j]
            wa += l[i][(j+p)%len(l[i])]
            tnp = max(tnp,wa)
    ans = max(ans, tnp)
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 = -1000000000
for i in range(N):
  cost = 0
  S = []
  x = P[i] - 1
  l = 1
  while 1:
    cost += C[x]
    S.append(cost)
    if x == i:
      break
    l += 1
    x = P[x] - 1
  if cost > 0:
    if K % l != 0:
      ans = max(ans, cost * (K // l) + max(S[:K % l]), cost * ((K // l) - 1) + max(S))
    else:
      ans = max(ans, cost * (K // l))
  else:
    ans = max(ans, max(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=-10**10
for i in range(n):
	K=k
	score=0
	pre_score=0
	visit=[0]*n
	now=i
	cnt=0
	while visit[now]==0:
		cnt+=1
		visit[now]=1
		now=p[now]-1
		pre_score+=c[now]
		if cnt!=1:
			score=max(score,pre_score)
		else:
			score=pre_score
		K-=1
		if K==0:
			break
	ans=max(score,ans)
	if K==0:
		continue
	loop=[0]
	NOW=now
	#NOWはループ元
	for j in range(n):
		now=p[now]-1
		loop.append(loop[-1]+c[now])
		if NOW==now:
			break
	pre_score2=pre_score
	pre_score2+=max(loop[:min(K+1,len(loop))])
	score=max(score,pre_score2)
	pre_score+=max(loop[-1],0)*(K//(len(loop)-1))
	K%=(len(loop)-1)
	pre_score+=max(loop[:K+1])
	score=max(score,pre_score)
	ans=max(ans,score)
print(ans)

Submission status: Wrong Answer

Solution code:
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=scores.copy()
    length=len(scores)
    scores=scores+scores

    ans=0
    if sum(vals)>0:
        ans+=K//length*sum(vals)
        remain=K-K//length*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+=max(vals)
    anses.append(ans)
print(max(anses))

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    ans = 0
    if "R" in S:
        ans = 1
    if "RR" in S:
        ans = 2
    if "RRR" in S:
        ans = 3
    print(ans)
    return

def examB():
    N = I()
    L = LI()
    L.sort()
    cnt = 0
    for i in range(N):
        for j in range(i+1,N):
            for k in range(j+1,N):
                if L[i]==L[j]:
                    continue
                if L[j]==L[k]:
                    continue
                if L[i]+L[j]>L[k]:
                    cnt += 1
    ans = cnt
    print(ans)
    return

def examC():
    X, K, D = LI()
    if X<0:
        X = -X
    ans = inf
    if X>K*D:
        ans = X-K*D
        print(ans)
        return

    K -= X//D
    X -= D * (X//D)

    ans = X
    if K>0:
        if K%2==1:
            ans = abs(X-D)
    print(ans)
    return

def examD():
    N, K = LI()
    P = LI()
    C = LI()

    B = [i for i in range(N)]
    for i,p in enumerate(P):
        p -= 1
        B[i] = p

    locat_doubling = [[0]*N for _ in range(31)]
    score_doubling = [[0]*N for _ in range(31)]

    for i in range(N):
        locat_doubling[0][i] = i
        locat_doubling[1][B[i]] = i
        score_doubling[0][i] = 0
        score_doubling[1][B[i]] = C[i]
    for k in range(2,31):
        for i in range(N):
            locat_doubling[k][i] = locat_doubling[k-1][locat_doubling[k-1][i]]
            score_doubling[k][i] = score_doubling[k-1][i] + score_doubling[k - 1][locat_doubling[k - 1][i]]

    score = [[0,-inf] for i in range(N)]
    locate = [[i,i] for i in range(N)]
    ans = max(C)

    if ans<0:
        print(ans)
        return

    for k in range(30)[::-1]:
        for i in range(N):
            if score[i][1]<0:
                continue
            #print(score[i],locate[i])
            score[i][1] += score_doubling[k + 1][locate[i][1]]
            if score[i][1] < score[i][0]:
                locate[i][1] = locat_doubling[k + 1][locate[i][1]]
        if K&(1<<k)>0:
            for i in range(N):
                score[i][0] += score_doubling[k+1][locate[i][0]]
                locate[i][0] = locat_doubling[k+1][locate[i][0]]
    for s in score:
        ans = max(ans,s[0],s[1])
    print(ans)
    return

def examE():
    R, C, K = LI()
    V = [[-inf]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = LI()
        V[r-1][c-1] = v
    dp0 = [[0]*(C+1) for _ in range(R+1)]
    dp1 = [[0]*(C+1) for _ in range(R+1)]
    dp2 = [[0]*(C+1) for _ in range(R+1)]
    dp3 = [[0]*(C+1) for _ in range(R+1)]

    for r in range(R):
        for c in range(C):
            v = V[r][c]
            if 0<v:
                dp0[r+1][c+1] = max(dp0[r+1][c],dp0[r][c+1],dp1[r][c+1],dp2[r][c+1],dp3[r][c+1])
                dp1[r+1][c+1] = max(dp1[r+1][c],dp0[r+1][c]+v,dp0[r][c+1]+v,dp1[r][c+1]+v,dp2[r][c+1]+v,dp3[r][c+1]+v)
                dp2[r+1][c+1] = max(dp2[r+1][c],dp1[r+1][c]+v)
                dp3[r+1][c+1] = max(dp3[r+1][c],dp2[r+1][c]+v)
            else:
                dp0[r+1][c+1] = max(dp0[r+1][c],dp0[r][c+1],dp1[r][c+1],dp2[r][c+1],dp3[r][c+1])
                dp1[r+1][c+1] = dp1[r+1][c]
                dp2[r+1][c+1] = dp2[r+1][c]
                dp3[r+1][c+1] = dp3[r+1][c]

    ans = max(dp0[R][C],dp1[R][C],dp2[R][C],dp3[R][C])
    print(ans)
    return

def examF():

    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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

S = []
for i in range(N):
    p, si = i, [0]
    ps = set()
    while P[p] not in ps:
        p = P[p]
        ps.add(p)
        si.append(si[-1] + C[p])
    si = si[1:]
    S.append(si)


ans = -float('inf')
for i in range(N):
    if K >= len(S[i]):
        ans = max(ans, max(S[i]), S[i][-1] * (K // len(S[i])) + max(S[i][:(K % len(S[i]))] + [0]))
    else:
        ans = max(ans, max(S[i][:K]))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, K = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))
# print()
# print(*P)
# print(*C)
x = 0
used = [0] * N
path = defaultdict(list)
score = defaultdict(list)
for i in range(N):
    if used[i]:
        continue
    x = i
    while used[x] == 0:
        used[x] = 1
        path[i].append(x)
        score[i].append(C[x])
        x = P[x]
ans = -float('inf')
for r in path:
    pa, sc, le = path[r], score[r], len(path[r])
    # print(pa, sc, le)
    for i in range(le-1):
        sc[i+1] += sc[i]
    if sc[-1] <= 0 or K < le:
        m = -float('inf')
        for i in range(len(pa)):
            for j in range(i+1, len(pa)):
                if j - i <= K:
                    m = max(m, sc[j] - sc[i])
                if le - j + i <= K:
                    m = max(m, sc[-1] - sc[j] + sc[i])
        ans = max(ans, m)
    else:
        k = K % le
        m = -float('inf')
        for i in range(le):
            for j in range(i+1, le):
                if j - i <= k:
                    m = max(m, sc[j] - sc[i])
                if le - j + i <= k:
                    m = max(m, sc[-1] - sc[j] + sc[i])
        ans = max(ans, m + sc[-1] * (K // le))

        m = -float('inf')
        for i in range(le):
            for j in range(i+1, le):
                if j - i <= le:
                    m = max(m, sc[j] - sc[i])
                if le - j + i <= le:
                    m = max(m, sc[-1] - sc[j] + sc[i])
        ans = max(ans, m + sc[-1] * ((K // le) - 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()))
for k in range(N):
  P[k] -= 1
scorelist = []
roop = []
now = 0
visited = [-1 for _ in range(N)]
for k in range(N):
  now = k
  if visited[now] == -1:
    roop.append([])
    scorelist.append([])
    start = 0 + now
    while visited[start] == -1:
      roop[-1].append(start)
      visited[start] = 1 
      start = P[start]
      scorelist[-1].append(C[start])
    scorelist[-1] = scorelist[-1] + scorelist[-1]
    
#print(roop)
#print(scorelist)

ans = - float('inf')
for l in range(len(roop)):
  #print(scorelist[l][:len(roop[l])])
  Q = K // len(roop[l])
  R = K % len(roop[l])
  if Q > 0 and R == 0:
    Q -= 1
    R = len(roop[l]) 
  #print(Q, R)
  if sum(scorelist[l][:len(roop[l])]) > 0:
    basis = sum(scorelist[l][:len(roop[l])])*Q
  else:
    basis = 0
  #print(basis)
  advlist = -float('inf')
  for k in range(len(roop[l])):
    adv = 0
    for j in range(k, k + R):
      adv += scorelist[l][j]
      advlist  = max(advlist, adv) 
  ans = max(ans, basis + advlist)

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 = [False] * n
from collections import deque
ds = []
sums = []
for i in range(n):
    if visited[i]: continue
    q = deque([])
    q.append(i)
    s = cs[i]
    d = [i]
    while len(q) > 0:
        u = q.popleft()
        visited[u] = True
        nx = ps[u]
        if visited[nx]: continue
        d.append(nx)
        q.append(nx)
        s += cs[nx]
    sums.append(s)
    ds.append(d)

# print(ds,sums)
from itertools import accumulate
def calcmax(d,s,k,cs):
    cnt = 0
    l = len(d)
    div, rest_ = divmod(k-1, l)
    rest_ += 1
    if s > 0:
        cnt += div*s
    d2 = d*2
    mx = - 1<<50
    c_ = [cs[j] for j in d2]
    acc = list(accumulate(c_))
    for rest in range(1,rest_+1):
        for i in range(rest,l*2):
            c = acc[i] - acc[i-rest]
            mx = max(mx, c)
    # print(d,cnt,mx)
    return cnt + mx

ans = -1 << 50
for d,s in zip(ds,sums):
    # print("aaa",d,s)
    c = calcmax(d,s,k,cs)
    ans = max(ans,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()))

csum = sum(c)
if(k < n):
    ans = max(c)
    tab = [0 for i in range(n)]
    for i in range(k):
        ntab = [0 for i in range(n)]
        for j in range(n):
            ntab[p[j]-1] = tab[j] + c[p[j]-1]
        tab = ntab[:]
        mtab = max(tab)
        if(ans < mtab):
            ans = mtab
    print(ans)
else:
    ans = [0]
    tab = [0 for i in range(n)]
    for i in range(n):
        ntab = [0 for i in range(n)]
        for j in range(n):
            ntab[p[j]-1] = tab[j] + c[p[j]-1]
        tab = ntab[:]
        mtab = max(tab)
        ans.append(mtab)
        print(tab)
    if(csum <= 0):
        print(max(ans[1:]))
    else:
        nans = max(c)
        for i in range(n):
            ki = k-i
            nans2 = (ki // n)*csum + ans[i]
            if(nans2 > nans):
                nans = nans2
        print(nans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))

N, K = mi()
P = li()
C = li()
ans = -float('inf')

for i in range(N):
    ind = i
    his = []
    while True:
        ind = P[ind] - 1
        his.append(C[ind])
        if ind == i:
            his = list(accumulate(his))
            L = len(his)
            if K > L:
                if his[-1] > 0:
                    if not K%L:
                        ans = max(ans, his[-1] * (K//L))
                    else:
                        ans = max(ans, max(his[:K%L]) + his[-1] * (K//L))
                else:
                    ans = max(ans, max(his))
            else:
                ans = max(ans, max(his[:K]))
            break

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
class UnionFind:
    def __init__(self, N=None):
        if N is None or N < 1:
            self.parent = defaultdict(lambda: -1)
        else:
            self.parent = [-1]*int(N)

    def root_rec(self, n):
        if self.parent[n] < 0:
            return n
        else:
            m = self.root(self.parent[n])
            self.parent[n] = m
            return m

    def root(self, n):
        stack = []
        while n >= 0:
            stack.append(n)
            n = self.parent[n]
        m = stack.pop()
        while stack:
            self.parent[stack.pop()] = m
        return m

    def merge(self, m, n):
        rm = self.root(m)
        rn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def connected(self, m, n):
        return self.root(m) == self.root(n)

    def groups(self):
        if isinstance(self.parent,list):
            return list(filter(lambda i: self.parent[i]<0, range(len(self.parent))))
        else: # self.parent: defaultdict
            return list(filter(lambda i: self.parent[i]<0, self.parent.keys()))
 
    def groups_num(self):
        return len(self.groups())

    def elements(self):
        if isinstance(self.parent,list):
            return range(len(self.parent))
        else:
            return self.parent.keys()

N, K = inpl()
P = list(map(lambda x: x-1,inpl()))
C = inpl()

uf = UnionFind(N)
for i in range(N):
    uf.merge(i, P[i])

ans = C[0]
for g in uf.groups():
    L = uf.size(g)
    cycle = C[g]
    p = P[g]
    while p != g:
        cycle += C[p]
        p = P[p]
    q, r = K//L, K % L
    if cycle > 0:
        score = q * cycle
    else:
        score = 0

    s = g
    v = C[g]
    for _ in range(L):
        u = score
        t = s
        for i in range(1,N+1):
            u += C[t]
            t = P[t]
            if i > r:
                if q > 0 and cycle > 0:
                    u -= cycle
                elif q > 0 and cycle <= 0:
                    pass
                elif q == 0:
                    continue
            if u > v:
                v = u
        s = P[s]

    if v > ans:
        ans = v

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n,k = l_in()
P = l_in()
C = l_in()

s = min(k,n)

res = -(10**10)
for start in range(n):
    j = start
    current = 0
    tmp = -(10**10)
    for i in range(1, k+1):
        j = P[j]-1
        current += C[j]
        tmp = max(tmp, current)
        if j == start:
 #           print(i)
#            print(current)
            
            if current > 0:
                s = k%i
                add = current*(k//i)

                j = start
                current = 0

                for i2 in range(1, s+1):
                    j = P[j]-1
                    current += C[j]
                    tmp = max(tmp, current+add)


                if k//i > 1:
                    add = current*(k//i - 1)
                    j = start
                    current = 0

                    for _ in range(i):
                        j = P[j]-1
                        current += C[j]
                        tmp = max(tmp, current+add)
            break
                
    res = max(tmp, res)
    
print(res)

Submission status: Wrong Answer

Solution code:
def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    c = list(map(int,input().split()))
    vis = [0 for i in range(n)]
    grps = []
    g = 1
    for i in range(n):
        if vis[i] == 0:
            que = [i]
            vis[i] = g
            cnt = [i]
            while len(que)>0:
                st = que.pop(0)
                if vis[p[st]-1]!=0:
                    g += 1
                    grps.append(cnt)
                    break
                vis[p[st]-1] = g
                cnt.append(p[st]-1)
                que.append(p[st]-1)

    loop_sum = [0 for i in range(n)]
    for i in range(len(grps)):
        s = 0
        for j in range(len(grps[i])):
            s += c[grps[i][j]]
        for j in range(len(grps[i])):
            loop_sum[grps[i][j]] = s

    ans = -1 * float('inf')
    for i in range(n):
        g_sum = -1 * float('inf')
        l_len = len(grps[vis[i]-1])
        loop = k//l_len
        lost = k - loop*l_len
        if lost == 0:
            lost = l_len
            loop -= 1
        s = 0
        point = i
        for _ in range(lost):
            point = p[point]-1
            s += c[point]
            if s > g_sum:
                g_sum = s
        s += loop * loop_sum[i]
        if ans < max(s,g_sum):
            ans = max(s,g_sum)
    print(ans)

if __name__ == "__main__":
    main()

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:
# O(EV)
def bellman_ford(s):
    d = [0]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    x=s
    for tt in range(k):
        update = False # 更新が行われたか
        aa,bb,cc=g[x][0],g[x][1],g[x][2]
        if d[bb] < d[aa] + cc:
                d[bb] = d[aa] + cc
                update = True
            
        if not update:
            break

        x=bb
    return d

n,k=map(int,input().split())

g=[]
p=list(map(int,input().split()))
c=list(map(int,input().split()))

for i in range(n):
    g.append((i,p[i]-1,c[p[i]-1]))

ans=0

for i in range(n):
  for j in bellman_ford(i):
      if j==float('inf'):
          continue
      else:
        ans=max(ans,j)

print(ans)

Submission status: Wrong Answer

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

ret = -float('inf')
done = set()
for n in range(N) :
  if n in done : continue
    
  cur = n
  s = C[cur]
  done.add(cur)
  loop = [n]
  while not P[cur] in done :
    cur = P[cur]
    done.add(cur)
    loop.append(cur)
    s += C[cur]
  
  if s <= 0:
    for i in loop :
      cur = i
      x = 0
      for _ in range(min(len(loop), K)) :
        cur = P[cur]
        x += C[cur]
        ret = max(ret, x)
  else :
    d = 0
    if K > len(loop) :
      d = s * (K // len(loop) - 1)
      K = K % len(loop) + len(loop)
      
    for i in loop :
      cur = i
      x = 0
      for _ in range(K) :
        cur = P[cur]
        x += C[cur]
        ret = max(ret, x + d)
      
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()))

ans = -float('inf')
for i in range(N):
    s = 0
    j = i
    for k in range(K):
        j = P[j]-1
        s += C[j]
        ans = max(ans, s)
        if j==i: break
    rem = K - (k+1)
    d,m = divmod(rem, k+1)
    s *= (d+1)
    ans = max(ans, s)
    for k in range(m):
        j = P[j]-1
        s += C[j]
        ans = max(ans, s)

print(ans)

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  N,K=LI()
  P=LI()
  P=[0]+P
  C=LI()
  C=[0]+C

  l=[[0] for _ in range(N)]
  check=[[False]*(N+1) for _ in range(N)]
  roop=[]
  for i in range(N):
    zahyo=i+1
    check[i][zahyo]=True
    f=False
    for j in range(N+1):
      zahyo=P[zahyo]
      if check[i][zahyo] and not f:
        roop.append(j+1)
        f=True
      score=C[zahyo]
      l[i].append(l[i][-1]+score)
  # print(l)
  # print(roop)

  ans=-inf
  for i in range(N):
    roop_count=roop[i]
    if K<=roop_count:
      ans=max(ans,max(l[i][1:K+1]))
    else:
      ans=max(ans,max(l[i][1:K+1]))
      if l[i][roop_count]>0:
        c=K//roop_count
        _ans=c*l[i][roop_count]
        k=K%roop_count
        _ans+=max(l[i][1:k+1]+l[1])
        ans=max(ans,_ans)

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7


n,k=mdata()
p=mdata()
c=mdata()
l=[]
vis=[0]*n
ans=0
for i in range(n):
    vis=[0]*n
    q=[i]
    c1=[c[i]]
    t=0
    while True:
        a=q[-1]
        vis[a]=1
        if vis[p[a]-1]==1:
            t=p[a]-1
            break
        else:
            q.append(p[a]-1)
            c1.append(c[p[a]-1])
    m=0
    m1=-c1[0]
    for j in range(len(q)):
        if q[j]==t or j>k:
            break
        m1+=c1[j]
        m=max(m1,m)
    t1=m1
    if j<=k:
        for j1 in range(j,min(len(q),k)):
            m1 += c1[j1]
            m = max(m1, m)
        s=sum(c1[j:])
        t1+=((k+1-j)//(len(q)-j))*s
        m1=0
        m2=0
        for j1 in range(j,j+(k+1-j)%(len(q)-j)):
            m1+=c1[j1]
            m2=max(m1,m2)
        t1+=m2
        m=max(m,t1)
    ans=max(ans,m)
if ans==0 and 0 not in c:
    ans=max(c)
out(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()))
min = 0
for i in range(N):
    if C[i] >0:
        min+=1
else:
    if min == 0:
        print(max(C))