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
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
used = [-1]*N 
renketu = []
index = 0
def dfs(fr,cur,parent,index,li):
    Next = fr[cur]
    Next -= 1
    for chi in [Next]:
        if chi == parent or used[chi] != -1:
            continue
        used[chi] = index
        li.append(chi)
        dfs(fr,chi,cur,index,li)
for i in range(N):
    if used[i] != -1:
        continue
    li = [i]
    used[i] = index
    dfs(P,i,-1,index,li)
    index += 1
    renketu.append(li)
ren = renketu
n = len(ren)
ans = -1*10**20
for i in range(n):
    li = ren[i]
    nn = len(li)
    val = 0
    nnow = li[0]
    for jj in range(nn):
        val += C[P[nnow]-1]
        nnow = P[nnow]-1
    if val <= 0:
        for k in range(nn):
            now = li[k]
            v = 0
            for j in range(nn):
                v += C[P[now]-1]
                ans = max(ans,v)
                now = P[now]-1
    else:
        vvv = val*(K//nn)
        nnn = K % nn
        vmax = -1*10**20
        for k in range(nn):
            now = li[k]
            v = 0
            for j in range(nnn):
                v += C[P[now]-1]
                now = P[now]-1
            vmax = max(vmax,v)
        ans = max(ans,vvv+vmax)


print(ans)

Submission status: Wrong Answer

Solution code:
class Union_Find():
    def __init__(self,N):
        """0,1,...,n-1を要素として初期化する.

        n:要素数
        """
        self.n=N
        self.parents=[-1]*N
        self.rank=[0]*N

    def find(self, x):
        """要素xの属している族を調べる.

        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,yを同一視する.

        x,y:要素
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x]>self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def size(self, x):
        """要素xの属している要素の数.

        x:要素
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """要素x,yは同一視されているか?

        x,y:要素
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """要素xが属している族の要素.
        ※族の要素の個数が欲しいときはsizeを使うこと!!

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

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

U=Union_Find(N+1)

for i in range(1,N+1):
    U.union(i,P[i])

Cycle_Point={}
for a in U.roots():
    if a==0:
        continue

    b=P[a]
    S=C[a]
    while a!=b:
        S+=C[b]
        b=P[b]
    Cycle_Point[a]=S

Ans=-float("inf")
for i in range(1,N+1):
    group=U.find(i)
    length=U.size(i)

    rap,remain=divmod(K,length)

    if Cycle_Point[group]>0 and rap>0:
        Base_Score=Cycle_Point[group]*rap

        Temp_Score=Base_Score
        Score=Temp_Score

        p=i
        for _ in range(remain):
            p=P[p]
            Temp_Score+=C[p]
            Score=max(Score,Temp_Score)

        Ans=max(Ans,Score)
    else:
        Temp_Score=0
        Score=C[P[i]]

        p=i
        for _ in range(min(length,K)):
            p=P[p]
            Temp_Score+=C[p]
            Score=max(Score,Temp_Score)

        Ans=max(Ans,Score)

print(Ans)

Submission status: Wrong Answer

Solution code:
R = lambda: map(int, raw_input().split())
n, k = R()
p, c = R(), R()
p = [x - 1 for x in p]
vis = [False] * n
ans = min(c)

for i in xrange(n):
    if vis[i]:
        continue
    t = [c[i]]
    j = p[i]
    while j != i:
        vis[j] = True
        t.append(c[j])
        j = p[j]

    m = len(t)
    s = sum(t)

    ta = 0
    tk = k
    if s > 0:
        ta += s * (tk / m)
        tk %= m
    else:
        tk = m

    t = t + t
    j = -1
    v = 0
    mv = 0
    for i in xrange(len(t)):
        if v < 0:
            j = i - 1
            v = 0
        v += t[i]
        if i - j > tk:
            j += 1
            v -= t[j]
        mv = max(mv, v)
    ans = max(ans, ta + mv)
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 i in range(n):
    p[i] -= 1
def score(a, k):
    now = p[a]
    s = c[now]
    cnt = 1
    l = [s]
    while now != a and cnt < k:
        now = p[now]
        s += c[now]
        l.append(s)
        cnt += 1
    if cnt == k:
        return max(l)
    s = (k // cnt) * s
    k %= cnt
    cnt=0
    while cnt < k:
        now = p[now]
        s += c[now]
        l.append(s)
        cnt += 1
    return max(l)
print(max(score(i, k) for i in range(n)))

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
pl = [0] + list(map(int, input().split()))
cl = [0] + list(map(int, input().split()))

ans = (10**9)*(-1)
for start in range(1,n+1):
    val = 0
    vals = []
    already_set = set()
    curr_mass = start
    while True:
        next_mass = pl[curr_mass]
        point = cl[next_mass]
        if next_mass in already_set:
            break
        else:
            vals.append(point)
            already_set.add(next_mass)
            curr_mass = next_mass
    if k <= len(vals):
        c_max = vals[0]
        c_val = vals[0]
        if len(vals) > 1:
            for v in vals[1:]:
                c_val += v
                c_max = max(c_max, c_val)
        # print(c_max)
        ans = max(c_max,ans)
    else:
        v_sum = sum(vals)
        if v_sum <= 0:
            c_max = vals[0]
            c_val = vals[0]
            if len(vals) > 1:
                for v in vals[1:]:
                    c_val += v
                    c_max = max(c_max, c_val)
            # print(c_max)
            ans = max(c_max,ans)
        else:
            loop_cnt = k//len(vals)
            rem = k - loop_cnt*len(vals)
            c_max = v_sum*loop_cnt
            c_val = c_max
            if rem > 0:
                for v in vals[:rem]:
                    c_val += v
                    c_max = max(c_max, c_val)
            # print(c_max)
            ans = max(c_max,ans)
print(ans)
# 2939275739

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 ** 100
for i in range(n):
    d = [-1] * n
    d[i] = 0
    res = 0
    t = i
    cnt = 1
    while d[p[t] - 1] == -1:
        cnt += 1
        d[p[t] - 1] = d[t] + 1
        t = p[t] - 1
        res += c[t]
        ans = max(ans, res)
    t = p[t] - 1
    res += c[t]
    K = k - d[t]
    rt = 0
    q = i
    for i in range(d[t]):
        q = p[q] - 1
        rt += c[q]
    re = 0
    r = 0
    for i in range(K % cnt):
        t = p[t] - 1
        r += c[t]
        re = max(r, re)
    ans = max(ans, res * (K // cnt) + rt + re)
print(ans)

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
INF = 10**10
def main(N, K, P, C):
    ans = max(C)
    for i in range(N):
        used = [False] * N
        now = 0
        mx = -INF
        cnt = 0
        while True:
            if used[i]:
                break
            used[i] = True
            now += C[i]
            mx = max(mx, now)
            i = P[i] - 1
            cnt += 1
        tmp = max(mx, now)
        if now > 0:
            cycle, mod = divmod(K, cnt)
            tmp = max(tmp, now * (cycle - 1) + mx)
            t = now * cycle
            tmp = max(tmp, t)
            for j in range(mod):
                t += C[i]
                tmp = max(tmp, t)
                i = P[i] - 1
        ans = max(ans, tmp)
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *P, = map(int, input().split())
    *C, = map(int, input().split())
    main(N, K, P, C)

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

ans = max(c)
if(ans <= 0):
    print(ans)
    exit()

for i in range(n):
    now = i
    score = [0]
    while(p[now] != i ):
        now = p[now]
        score.append(score[-1] + c[now])
    cyc_score = score[-1] + c[i]
    cyc = len(score)

    tmp = max(score[:(k%cyc) + 1])
    tmp += max(0,cyc_score) * (k//cyc)
    if( k >= cyc):
        tmp = max(tmp, max(score))
    ans = max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    P = tuple(map(int, input().split())) #1行ベクトル
    C = tuple(map(int, input().split()))
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    
    tans=-float('inf')
    for i in range(N):
        start=i
        cur=P[i]-1
        score=C[cur]
        time=1
        ans=-float('inf')
        f=0
        while True:
            ans=max(ans,score)
            if cur==start:
                if score>0:
                    d=(K//time)
                    time=d*time
                    score=d*score
                else:
                    f=1
            if f:
                break

            cur=P[cur]-1
            score=score+C[cur]
            time=time+1
            if time>K:
                break
        tans=max(ans,tans)
    print(tans)





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:


from sys import stdin

N,K = map(int,stdin.readline().split())

P = list(map(int,stdin.readline().split()))
C = list(map(int,stdin.readline().split()))
end = [-1] * N
sc = [0] * N
for i in range(N):
    P[i] -= 1



ans = max(C)
for i in range(N):

    now = i
    nsum = 0
    lis = [0]

    for j in range(min(N,K)):
        now = P[now]
        nsum += C[now]
        ans = max(ans , nsum)
        lis.append(nsum)

        if i == now and nsum > 0:
            ans = max(ans , nsum*(K//(len(lis)-1)) + max(lis[:K%(len(lis)-1)+1]))
            break

print (ans)

Submission status: Wrong Answer

Solution code:
class Union_Find():
    def __init__(self,N):
        """0,1,...,n-1を要素として初期化する.

        n:要素数
        """
        self.n=N
        self.parents=[-1]*N
        self.rank=[0]*N

    def find(self, x):
        """要素xの属している族を調べる.

        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,yを同一視する.

        x,y:要素
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x]>self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def size(self, x):
        """要素xの属している要素の数.

        x:要素
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """要素x,yは同一視されているか?

        x,y:要素
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """要素xが属している族の要素.
        ※族の要素の個数が欲しいときはsizeを使うこと!!

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

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

U=Union_Find(N+1)

for i in range(1,N+1):
    U.union(i,P[i])

Cycle_Point={}
for a in U.roots():
    if a==0:
        continue

    b=P[a]
    S=C[a]
    while a!=b:
        S+=C[b]
        b=P[b]
    Cycle_Point[a]=S

Ans=-float("inf")
for i in range(1,N+1):
    group=U.find(i)
    length=U.size(i)

    rap,remain=divmod(K,length)

    if Cycle_Point[group]>0:
        Base_Score=Cycle_Point[group]*rap

        Temp_Score=Base_Score
        Score=Temp_Score

        p=i
        for _ in range(remain):
            p=P[p]
            Temp_Score+=C[p]
            Score=max(Score,Temp_Score)

        Ans=max(Ans,Score)
    else:
        Temp_Score=0
        Score=C[P[i]]

        p=i
        for _ in range(min(length,K)):
            p=P[p]
            Temp_Score+=C[p]
            Score=max(Score,Temp_Score)

        Ans=max(Ans,Score)

print(Ans)

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]*N
    flag = [False]*N
    locate = [i for i in range(N)]
    ans = max(C)
    if ans<0:
        print(ans)
        return

    for k in range(31)[::-1]:
        if K&(1<<k)>0:
            for i in range(N):
                if score_doubling[k+1][locate[i]]>0:
                    score[i] += score_doubling[k+1][locate[i]]
                    locate[i] = locat_doubling[k+1][locate[i]]
                else:
                    flag[i] = True
        else:
            for i in range(N):
                if flag[i] and score_doubling[k + 1][locate[i]]>0:
                    score[i] += score_doubling[k + 1][locate[i]]
                    locate[i] = locat_doubling[k + 1][locate[i]]
    for s in score:
        ans = max(ans,s)
    print(ans)
    return

def examE():
    R, C, K = LI()

    ans = 0
    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 = [int(i)-1 for i in input().split()]
c = [int(i) for i in input().split()]


def merge(p_a, c_a, p_b, c_b):
    p_c = []
    c_c = []
    for i, j in zip(p_a, c_a):
        p_c.append(p_b[i])
        c_c.append(j + c_b[i])
    return p_c, c_c


ans = -10**18
for i in range(n):
    co = 0
    for _ in range(n):
        i = p[i]
        co += c[i]
        ans = max(ans, co)

if k > n:
    pp = p[:]
    cc = c[:]
    k -= n
    a = list(range(n))
    b = [0] * n
    while k > 0:
        if k % 2 == 1:
            a, b = merge(a, b, p, c)
        p, c = merge(p, c, p, c)
        k //= 2

    ans = max(b)
    for i in range(n):
        co = b[i]
        i = a[i]
        for _ in range(n):
            i = pp[i]
            co += cc[i]
            ans = max(ans, co)

print(ans)

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()))
ans=-10**20
for i in range(n):
  x=[c[i]]
  j=p[i]
  while i!=j:
    x.append(c[j])
    j=p[j]
  d=(k-1)//len(x)
  dd=max(d*sum(x),0)
  kk=k-d*len(x)
  s=x[0]
  ans=max(ans,s+dd)
  for i in x[1:kk]:
    s+=i
    ans=max(ans,s+dd)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


def solve(n, k, ppp, ccc):
    NINF = -(10 ** 18)
    ans = NINF

    checked = [False] * n
    for s in range(n):
        if checked[s] == True:
            continue
        checked[s] = True
        scores = [ccc[ppp[s]]]
        v = ppp[s]
        while v != s:
            scores.append(ccc[ppp[v]])
            checked[v] = True
            v = ppp[v]

        l = len(scores)
        d, m = divmod(k, l)
        loop = sum(scores)

        if m == 0:
            d -= 1
            m = l

        scores += scores[:m]
        scores.insert(0, 0)
        acc = list(accumulate(scores))
        tmp = NINF
        for i in range(l):
            tmp = max(tmp, max(acc[i + 1:i + m + 1]) - acc[i])
        ans = max(ans, tmp, loop * d + tmp)

    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
ppp = [p - 1 for p in ppp]
ccc = list(map(int, input().split()))

print(solve(n, k, ppp, ccc))

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

class doubling(object):
	def __init__(self, N, P, C, bitlen):
		self.bitlen = bitlen
		self.nex = [[None] * N for i in range(bitlen)]
		for i in range(N):
			self.nex[0][i] = P[i]
		self.score = [[None] * N for i in range(bitlen)]
		for i in range(N):
			self.score[0][i] = C[i]

		#ダブリングテーブル構築
		for i in range(1, self.bitlen):
			for j in range(N):
				self.nex[i][j] = self.nex[i - 1][self.nex[i - 1][j]]

		for i in range(1, self.bitlen):
			for j in range(N):
				self.score[i][j] = self.score[i - 1][self.nex[i - 1][j]] + self.score[i - 1][j]


	#startからK回移動後の点を求める
	def query1(self, start, K):
		self.loc = start
		self.ans = 0
		for i in range(self.bitlen):
			if K % 2 == 1:
				self.ans += self.score[i][self.loc]
				self.loc = self.nex[i][self.loc]
			K = int(K // 2)

		return self.ans

#処理内容
def main():
	N, K = getlist()
	P = getlist()
	for i in range(N):
		P[i] -= 1
	C = getlist()
	DDD = doubling(N, P, C, 40)

	ans = -INF
	for i in range(N):
		val = 0
		itr = i
		for j in range(N):
			val += C[itr]
			ans = max(ans, val)
			itr = P[itr]

	for i in range(N):
		ans = max(ans, DDD.query1(i, K))

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
INF = 10**10
def main(N, K, P, C):
    ans = max(C)
    for i in range(N):
        used = [False] * N
        now = 0
        mx = -INF
        cnt = 0
        while True:
            if used[i]:
                break
            used[i] = True
            now += C[i]
            mx = max(mx, now)
            i = P[i] - 1
            cnt += 1
        tmp = max(mx, now)
        if now > 0:
            cycle, mod = divmod(K, cnt)
            t = now * cycle
            tmp = max(tmp, t)
            for j in range(mod):
                t += C[i]
                tmp = max(tmp, t)
                i = P[i] - 1
            t = now * (cycle - 1)
            tmp = max(tmp, t)
            for j in range(cnt):
                t += C[i]
                tmp = max(tmp, t)
                i = P[i] - 1
        ans = max(ans, tmp)
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *P, = map(int, input().split())
    *C, = map(int, input().split())
    main(N, K, P, C)

Submission status: Wrong Answer

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

group = [-1] * N
grouped_Ps = []
next_num = 0
for i in range(N):
    if group[i] == -1:
        g = []
        while group[i] == -1:
            group[i] = next_num
            g.append(Cs[i])
            i = Ps[i]
        grouped_Ps.append(g)
        next_num += 1

max_score = -1001001001
for g in grouped_Ps:
    l = len(g)
    q, r = divmod(K-1, l)
    r += 1
    score = max(0, sum(g) * q)
    max_s = -1001001001
    for k in range(1, r+1):
        s = sum(g[:k])
        max_s = max(max_s, s)
        for i in range(l):
            s -= g[i]
            s += g[(i+k)%l]
            max_s = max(max_s, s)
    
    max_score = max(max_s + score, max_score)

print(max_score)

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


def merge(p_a, c_a, p_b, c_b):
    p_c = []
    c_c = []
    for i, j in zip(p_a, c_a):
        p_c.append(p_b[i])
        c_c.append(j + c_b[i])
    return p_c, c_c


ans = -10**18
for i in range(n):
    co = 0
    for _ in range(n):
        i = p[i]
        co += c[i]
        ans = max(ans, co)

if k > n:
    pp = p[:]
    cc = c[:]
    k -= n
    a = list(range(n))
    b = [0] * n
    while k > 0:
        if k % 2 == 1:
            a, b = merge(a, b, p, c)
        p, c = merge(p, c, p, c)
        k //= 2

    for i in range(n):
        ans = max(ans, b[a[i]])
    for i in range(n):
        i = a[i]
        co = b[i]
        for _ in range(n):
            i = pp[i]
            co += cc[i]
            ans = max(ans, co)

print(ans)

Submission status: Wrong Answer

Solution code:


from sys import stdin

N,K = map(int,stdin.readline().split())

P = list(map(int,stdin.readline().split()))
C = list(map(int,stdin.readline().split()))
end = [-1] * N
sc = [0] * N
for i in range(N):
    P[i] -= 1



ans = max(C)
for i in range(N):

    now = i
    nsum = 0
    lis = [0]

    for j in range(min(N,K)):
        now = P[now]
        nsum += C[now]
        ans = max(ans , nsum)
        lis.append(nsum)

        if i == now and nsum > 0:
            ans = max(ans , nsum*(K//(len(lis)-1)) + lis[K%(len(lis)-1)])
            break

print (ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, k = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
for i in range(n):
    P[i] -= 1

V = [0] * n
ans = -float("inf")
an = 0
for i in range(n):
    if V[i] == 0:
        A = []
        V[i] = 1
        ii = P[i]
        V[ii] = 1
        A.append(C[ii])
        while ii != i:
            ii = P[ii]
            V[ii] = 1
            A.append(C[ii])
        # print(A)
        an = 0
        anb=0
        kb=k
        if sum(A) > 0:
            anb += sum(A) * (k//len(A))
            k %= len(A)
        A += A
        S = [A[0]]
        # print(an,k)
        for i in range(1,len(A)):
            S.append(S[-1]+A[i])
        # print(S)
        anc = 0
        for i in range(len(S)):
            for j in range(i+1, min(i+kb+1,len(S))):
                anc = max(anc,S[j]-S[i])

        for i in range(len(S)):
            for j in range(i+1, min(i+k+1,len(S))):
                an = max(an,S[j]-S[i])

        ans = max(an+anb,anc,ans)
            
if ans == 0 and max(C) < 0:
    print(max(C))
else:
    print(ans)