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: Accepted

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

def circle_grouping(P):
  P_in=[]
  P_group=[]
  for i in range(N):
    if i in P_in:
      pass
    else:
      start=i
      j=P[i]
      ls=[i]
      P_in.append(i)
      while j!=start:
        ls.append(j)
        P_in.append(j)
        j=P[j]
      P_group.append(ls)
  return P_group

def circle_maximum(A,K):
  max_val=max(A)
  for i in range(len(A)):
    val=0
    for k in range(K):
      pos=(i+k)%len(A)
      val+=A[pos]
      max_val=max(max_val,val)
  return max_val

score=max(C)
P_group=circle_grouping(P)
for A in P_group:
  k_rem=K%len(A)
  cycle=K//len(A)
  if cycle>=1:
    k_rem+=len(A)
    cycle-=1
  B=[C[i] for i in A]
  score=max(score,max(0,sum(B))*cycle+circle_maximum(B,k_rem))
print(score)

Submission status: Accepted

Solution code:
import copy
import math
import time
import statistics
import math
import itertools
import bisect
from decimal import *


# a = get_int()
def get_int():
    return int(input())


# a = get_string()
def get_string():
    return input()


# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]


# a_list = get_string_list():
def get_string_list():
    return input().split()


# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())


# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))


# print("{} {}".format(a, b))
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''


def main():
    start = time.time()

    n, k = get_int_multi()
    p = get_int_list()
    c = get_int_list()

    kaisuu = [-1] * n
    score = [0] * n
    score_max = [0] * n

    for i in range(n):
        wk = 0
        wk2 = 0
        ichi = i
        for ii in range(n):
            ichi = p[ichi] - 1
            wk += c[ichi]
            wk2 = max(wk2, wk)
            if i == ichi:
                kaisuu[i] = ii + 1
                score[i] = wk
                score_max[i] = wk2
                break

    wk = 0
    ans = - 10 ** 20
    for i in range(n):
        ichi = p[i] - 1
        wk = c[ichi]
        wk2 = c[ichi]
        idx = 0
        while idx < k - 1:
            ichi = p[ichi] - 1
            wk += c[ichi]

            wk2 = max(wk2, wk)
            idx += 1

            # ループするならメモを使って減らす
            if (k - 1 - idx > kaisuu[ichi] * 2) and kaisuu[ichi] > 0:
                roopsuu = ((k - 1 - idx) // kaisuu[ichi]) - 1
                wk += roopsuu * score[ichi]
                idx += roopsuu * kaisuu[ichi]
                wk2 = max(wk2, max(wk, score_max[ichi]))

        ans = max(ans, wk2)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
P=[int(a)-1 for a in input().split()]
C=[int(a) for a in input().split()]
ans=-float("inf")
for si in range(N):
  x=si
  S=[]
  tot=0
  while True:
    x=P[x]
    S.append(C[x])
    tot+=C[x]
    if x==si:
      break
  L=len(S)
  t=0
  for i in range(L):
    t+=S[i]
    if i+1>K:
      break
    now=t
    if tot>0:
      e=(K-i-1)//L
      now+=tot*e
    ans=max(ans,now)
    
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    P = [int(x) - 1 for x in input().split()]
    C = [int(x) for x in input().split()]

    ans = -10 ** 9
    # 全ての点を始点とした場合を考える(N通り)
    for start in range(N):
        # ループを探索．スコアの累積和も勘定しておく
        now = start
        loop = []
        total = 0
        for _ in [0] * N:  # while Trueでもおｋ
            now = P[now]
            loop.append(C[now])
            total += C[now]
            if now == start:
                break
        # 最大スコアを探索
        length = len(loop)
        score = 0
        for i in range(length):
            score += loop[i]
            # 操作回数 >= Kなら，ループ途中でも探索終了
            if i >= K:
                break
            # ループを周回するので，それを利用して探索を省略
            res = score
            if total > 0:
                laps = (K - (i + 1)) // length
                res += total * laps
            ans = max(ans, res)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
N,K=map(int,input().split())
plist=[0]+list(map(int,input().split()))
clist=[-float("inf")]+list(map(int,input().split()))

if max(clist)<=0:
  print(max(clist))
  sys.exit(0)
  
if K<=N:
  max_answer=0
  for i in range(1,N+1):
    pos=i
    max_score=0
    score=0
    for c in range(K):
      pos=plist[pos]
      score+=clist[pos]
      max_score=max(score,max_score)
      
    #print(i,max_score)
    max_answer=max(max_answer,max_score)
    
  print(max_answer)
  sys.exit(0)
  
max_answer=0
for i in range(1,N+1):  
  pos=i
  cycle_list=[]
  score_list=[]
  for _ in range(N):
    pos=plist[pos]
    cycle_list.append(pos)
    score_list.append(clist[pos])    
    if pos==i:
      break
      
  num_cycle=K//len(cycle_list)
  cycle_score=sum(score_list)
  #print(cycle_list,score_list,num_cycle,cycle_score)
  
  score=0
  max_score=0  
  if cycle_score>=0:
    score+=(num_cycle-1)*cycle_score
  K2=K-len(cycle_list)*(num_cycle-1)

  for _ in range(K2):
    pos=plist[pos]
    score+=clist[pos]
    max_score=max(score,max_score)
  
  #print(i,max_score)
  max_answer=max(max_answer,max_score)
  
print(max_answer)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
P = [0] + inpl()
C = [0] + inpl()

ans = 1000000010 * -1
for start in range(1,n+1):
    l = [0] * (n+1)
    l[start] = 1
    now = start
    score = []
    while True:
        l[now] = 1
        score.append(C[P[now]])
        if l[P[now]] == 1:
            break
        now = P[now]
    
    ruiseki = []
    for i in range(len(score)):
        if i == 0:
            ruiseki.append(score[i])
        else:
            ruiseki.append(ruiseki[i-1] + score[i])

    a = ruiseki[-1] #1ループでのスコア
    b = max(ruiseki) #1ループ中の最大スコア
    c = k // len(ruiseki) #ループ可能回数
    d = k % len(ruiseki) #ループ抜けてからのあまり回数

    tmp = 0
    if c == 0:
        tmp = max(ruiseki[:d])
    elif c > 0:
        if a <= 0:
            tmp = b
        elif d == 0:
            tmp = a*(c-1) + b
        else:
            tmp = max(a*c + max(ruiseki[:d]),a*(c-1) + b)
    ans = max(ans,tmp)

print(ans)

Submission status: Accepted

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

js = [None for _ in range(n)] # 周期とスコア増分

for s in range(n):
    if js[s]:
        continue
    m = s
    tmp = 0
    memo = [[] for _ in range(n)]
    i = 0
    while True:
        m = p[m] - 1
        tmp += c[m]
        memo[m].append((i, tmp))
        if len(memo[m]) > 1:
            js[m] = (memo[m][1][0] - memo[m][0][0], memo[m][1][1] - memo[m][0][1])
        if len(memo[m]) > 2:
            break
        i += 1

ans = -100000000000
for s in range(n):
    m = s
    tmp = 0
    visited = [0] * n
    for i in range(k):
        m = p[m] - 1
        if visited[m]:
            break
        visited[m] = 1
        tmp += c[m]
        if js[m] and js[m][1] > 0:
            ans = max(ans, tmp + js[m][1] * ((k - i - 1) // js[m][0]))
        else:
            ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
_c = list(map(int, input().split()))
c = [0]*n
for i in range(n):
    p[i] -= 1
    c[i] = _c[p[i]]
m = 31
MIN = - (1 << 63)
vertex = list()
score = list()
vertex.append(p)
score.append(c)
for a in range(1, m+1):
    p_ath = [0] * n
    c_ath = [0] * n
    for i in range(n):
        p_ath[i] = vertex[a-1][vertex[a-1][i]]
        c_ath[i] = score[a-1][i] + score[a-1][vertex[a-1][i]]
    vertex.append(p_ath)
    score.append(c_ath)
    
prv = [[MIN, 0] for _ in range(n)]
nxt = [[MIN, MIN] for _ in range(n)] 
for b in range(m, -1, -1):
    for i in range(n):
        if (k >> b) & 1:
            nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
            nxt[vertex[b][i]][1] = max(nxt[vertex[b][i]][1], prv[i][1] + score[b][i])
            nxt[i][0] = max(nxt[i][0], prv[i][0], prv[i][1])
        else:
            nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
            nxt[i][0] = max(nxt[i][0], prv[i][0])
            nxt[i][1] = max(nxt[i][1], prv[i][1])
    prv, nxt = nxt, prv
ans = max(max(x) for x in prv)
if ans == 0:
    ans = max(c)
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, k = nm()
    p = nl()
    _c = nl()
    c = [0]*n
    for i in range(n):
        p[i] -= 1
        c[i] = _c[p[i]]
    m = 31
    MIN = - (1 << 63)
    vertex = list()
    score = list()
    vertex.append(p)
    score.append(c)
    for a in range(1, m+1):
        p_ath = [0] * n
        c_ath = [0] * n
        for i in range(n):
            p_ath[i] = vertex[a-1][vertex[a-1][i]]
            c_ath[i] = score[a-1][i] + score[a-1][vertex[a-1][i]]
        vertex.append(p_ath)
        score.append(c_ath)
    
    prv = [[MIN, 0] for _ in range(n)]
    nxt = [[MIN, MIN] for _ in range(n)] 
    for b in range(m, -1, -1):
        for i in range(n):
            if (k >> b) & 1:
                nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
                nxt[vertex[b][i]][1] = max(nxt[vertex[b][i]][1], prv[i][1] + score[b][i])
                nxt[i][0] = max(nxt[i][0], prv[i][0], prv[i][1])
            else:
                nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
                nxt[i][0] = max(nxt[i][0], prv[i][0])
                nxt[i][1] = max(nxt[i][1], prv[i][1])
        prv, nxt = nxt, prv
    ans = max(max(x) for x in prv)
    if ans == 0:
        ans = max(c)
    print(ans)    
    return

solve()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():
    n, k = mi()
    p = list(map(lambda x: int(x)-1, input().split()))
    c = li()
    ans = -10**18
    for i in range(n):
        v = i
        cycle_cnt = 0
        cycle_sum = 0
        while True:
            cycle_cnt += 1
            cycle_sum += c[v]
            v = p[v]
            if v == i:
                break
        
        cnt = 0
        tmp = 0
        while True:
            tmp += c[v]
            cnt += 1
            if cnt > k:
                break
            r = (k-cnt)//cycle_cnt
            score = tmp+r*max(0, cycle_sum)
            ans = max(ans, score)
            v = p[v]
            if v == i:
                break
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
(n,k),p,c=[[*map(int,t.split())]for t in open(0)]
a=-9e9
for i in range(n):
 s=f=0;x,j,*l=i,k
 while~f:x=p[x]-1;s+=c[x];l+=s,;f-=x==i
 for t in l[:k]:j-=1;a=max(a,t+j//len(l)*s*(s>0))
print(a)

Submission status: Accepted

Solution code:
(n,k),p,c=[[*map(int,t.split())]for t in open(0)]
a=-9e9
for i in range(n):
 s=f=j=0;x,*l=i,
 while~f:x=p[x]-1;s+=c[x];l+=s,;f-=x==i
 for t in l[:k]:j-=1;a=max(a,t+(j+k)//len(l)*s*(s>0))
print(a)

Submission status: Accepted

Solution code:
(n,k),p,c=[[*map(int,t.split())]for t in open(0)]
a=-9e9
for i in range(n):
 s=f=m=0;x,*l=i,
 while~f:x=p[x]-1;s+=c[x];l+=s,;m+=1;f-=x==i
 for j in range(min(m,k)):a=max(a,l[j]+(~j+k)//m*s*(s>0))
print(a)

Submission status: Accepted

Solution code:
(n,k),p,c=[[*map(int,t.split())]for t in open(0)]
a=-9e9
for i in range(n):
 s=t=f=m=0;x,*l=i,
 while~f:x=p[x]-1;l+=c[x],;s+=c[x];m+=1;f-=x==i
 for j in range(min(m,k)):t+=l[j];a=max(a,t+(~j+k)//m*s*(s>0))
print(a)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
P = LIST()
C = LIST()

check = [0]*N 
score = []

for i in range(N):
	if check[i]:
		continue

	tmp = []
	while check[i] == 0:
		check[i] = 1
		i = P[i]-1
		tmp.append(C[i])
	score.append(tmp)

ans = -INF
for x in score:
	x_acc = list(accumulate([0] + x + x))
	n = len(x)
	tmp_max = -INF

	for i, j in combinations(range(2*n+1), 2):
		if j-i <= min(K, n):
			if tmp_max < x_acc[j]-x_acc[i]:
				tmp_max = x_acc[j]-x_acc[i]
				cnt = j-i
	tmp_ans = -INF

	if 0 >= x_acc[n]:
		tmp_ans = tmp_max

	else:
		if cnt <= K%n:
			tmp_ans = x_acc[n]*(K//n) + tmp_max
		else:
			tmp_max2 = 0
			for i, j in combinations(range(2*n+1), 2):
				if j-i <= K%n:
					if tmp_max2 < x_acc[j]-x_acc[i]:
						tmp_max2 = x_acc[j]-x_acc[i]
			tmp_ans = max(x_acc[n]*(K//n-1)+tmp_max, x_acc[n]*(K//n) + tmp_max2)

	ans = max(ans, tmp_ans)

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, K = LI()
    P = LI_()
    C = LI()
    G = [-1 for _ in range(N)]
    for i, p in enumerate(P):
        G[i] = p
    seen = set()

    loop_score = []
    loop_size = []
    loop_id2node = collections.defaultdict(list)

    _id = 0
    def calc_one_loop(v):
        nodes = set()
        if G[v] == -1:
            return -1, -1
        # calc loop, and return score
        score = 0
        size = 0
        while G[v] not in seen:
            v = G[v]
            seen.add(v)
            nodes.add(v)
            score += C[v]
            size += 1
        return score, size, nodes

    for i in range(N):
        if i in seen:
            continue
        score, size, nodes = calc_one_loop(i)
        if score == -1 and size == -1:
            continue
        loop_score.append(score)
        loop_size.append(size)
        loop_id2node[_id].extend(list(nodes))
        seen.add(i)
        _id += 1

    # print('loop_size: ', loop_size)
    # print('loop_score: ', loop_score)
    ans = -inf
    for i in range(_id):
        # i: id
        n_loop = K // loop_size[i]

        # score_afterを作る
        score_after = [[0] for _ in range(N)]
        for v in loop_id2node[i]:
            max_move_cnt = loop_size[i] + 1
            move_cnt = 0
            cum_score = 0
            cur_v = v
            while move_cnt < max_move_cnt:
                cur_v = G[cur_v]
                cum_score += C[cur_v]
                score_after[v].append(cum_score)
                move_cnt += 1
        # print('score_after: ', score_after)
        if loop_score[i] <= 0:
            max_step = min(K, loop_size[i])
            score = 0
        else:
            # 先に回る
            # ちょうど1周だったら、回らない
            score = 0
            max_step = loop_size[i]

            # if K == loop_size[i]:
            #     max_step = K
            #     score = 0
            # else:
            #     K -= n_loop * loop_size[i]
            #     max_step = K
            #     score = n_loop * loop_score[i]

        # loop_size[i]より小さい数で全探索
        for l in range(1, max_step + 1):
            for v in loop_id2node[i]:
                cp_score = score
                cnt = 0
                cp_score += score_after[v][l]
                # 実現不可能なら飛ばす
                if l > K:
                    continue
                # 回った時も試してみる
                if K - l >= loop_size[i]:
                    cp_score = max(cp_score, cp_score + loop_score[i] * ((K - l) // loop_size[i]))
                ans = max(ans, cp_score)
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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


ans = -INF
for i in range(N):
    nx = i
    total = 0
    L = [] 
    while True:
        nx = P[nx]
        total += C[nx]
        L.append(C[nx])
        if nx == i:
            break
    l = len(L)
    tmp = 0
    for j in range(l):
        if j + 1 > K:
            break
        tmp += L[j]
        now = tmp
        if total > 0:
            e = (K - j - 1) // l
            now += total * e
        ans = max(ans, now)
    # if total > 0:
    #     now = total * (K // l)
    #     ans = max(ans, now)
    #     r = K % l
    #     for j in range(r):
    #         now += L[j]
    #         ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
def solve():
    from collections import defaultdict
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.par = [-1] * n

        def find(self, x):
            if self.par[x] < 0:
                return x
            else:
                while self.par[x] >= 0:
                  x = self.par[x]
                return x

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

            if x == y:
                return

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

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

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

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

    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    mp = defaultdict(int)
    uf = UnionFind(n)

    for i in range(n):
        uf.unite(i, p[i] - 1)

    for i in range(n):
        mp[uf.find(i)] += c[i]

    ans = -10 ** 14
    for i in range(n):
        roop = uf.size(i)
        times = (k - 1) // roop if mp[uf.find(i)] > 0 else 0
        over = max(min(roop, k - roop * times), 1)
        tmp = 0
        s = -10 ** 10
        idx = i
        for j in range(over):
            tmp += c[idx]
            s = max(s, tmp)
            idx = p[idx] - 1
        s += times * mp[uf.find(i)]
        ans = max(ans, s)
    print(ans)


solve()

Submission status: Accepted

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()))
ans = -10**18

for i in range(N):
    now = i
    visit = [False]*N
    visit[now] = True
    l = []
    
    for _ in range(N+10):
        nex = P[now]-1
        l.append(C[nex])
        
        if visit[nex]:
            break
        
        visit[nex] = True
        now = nex
    
    s = sum(l)
    now = 0
    
    for i in range(min(K, len(l))):
        now += l[i]
        ans = max(ans, now+(K-i-1)//len(l)*max(0, s))
    
print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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

sumlist1 = [[0]*N for _ in range(N)]
walist = [[0]*N for _ in range(N)]
loopcount = [0]*N

for h in range(N):
    sumlist1[h][0] = C[h]
    walist[h][0] = C[h]
    now = h
    l = 0
    for i in range(1,N):
        now = P[now]-1

        if sumlist1[h][i-1] < 0:
            sumlist1[h][i] = C[now]
        else:
            sumlist1[h][i] += sumlist1[h][i-1] + C[now]
        walist[h][i] += walist[h][i-1] + C[now]
        
        l += 1
        if now == h:
            break
    else:
        l += 1
    loopcount[h] = l
#print(sumlist1)

maxlist = [0]*N
for i in range(N):
    T = loopcount[i]
    wa = walist[i][T-1]
    #print(wa,T)

    loop = K//T
    amari = K%T

    if wa >= 0:
        if loop == 0:
            if amari != 0:
                maxlist[i] = wa*loop + max(sumlist1[i][:amari])
            else:
                maxlist[i] = max(sumlist1[i][:amari])
        else:
            if amari != 0:
                maxlist[i] = max(wa*loop + max(sumlist1[i][:amari]), wa*(loop-1) + max(sumlist1[i]))
            else:
                maxlist[i] = max(wa*loop, wa*(loop-1) + max(sumlist1[i][:T]))
            

    else:
        if loop == 0:
            maxlist[i] = max(sumlist1[i][:amari])
        else:
            maxlist[i] = max(sumlist1[i])

print(max(maxlist))
#print(sumlist1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        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 solve():
    N, K = map(int, rl().split())
    P = list(map(lambda n: int(n) - 1, rl().split()))
    C = list(map(int, rl().split()))
    
    uf = UnionFind(N)
    for i in range(N):
        uf.union(i, P[i])
    roop_scores = defaultdict(int)
    for i in range(N):
        roop_scores[uf.find(i)] += C[i]
    
    ans = -(10 ** 18)
    K -= 1
    for s in range(N):
        cur = P[s]
        tmp = C[cur]
        ans = max(ans, tmp)
        roop_size = uf.size(s)
        roop_score = roop_scores[uf.find(s)]
        roop_cnt = K // roop_size
        if roop_cnt and 0 < roop_score:
            tmp += roop_score * roop_cnt
            rem = K % roop_size
            ans = max(ans, tmp)
            while rem:
                cur = P[cur]
                tmp += C[cur]
                ans = max(ans, tmp)
                rem -= 1
            continue
        cnt = min(roop_size, K)
        while cnt:
            cur = P[cur]
            tmp += C[cur]
            ans = max(ans, tmp)
            cnt -= 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
f=lambda:[*map(int,input().split())]
n,k=f()
p,c=f(),f()
p=[i-1 for i in p]
a=-10**9
for i in range(n):
  x,l,s,t=i,[],0,0
  while 1:
    x=p[x]
    l+=[c[x]]
    s+=c[x]
    if x==i: break
  m=len(l)
  for j in range(m):
    if j+1>k: break
    t+=l[j]
    a=max(a,t+(k-j-1)//m*s*(s>0))
print(a)

Submission status: Accepted

Solution code:
f=lambda:[*map(int,input().split())]
n,k=f()
p,c=f(),f()
p=[*map(lambda x:x-1,p)]
a=-10**9
for i in range(n):
  x=i
  l=[]
  s=0
  while 1:
    x=p[x]
    l+=[c[x]]
    s+=c[x]
    if x==i: break
  m=len(l)
  t=0
  for j in range(m):
    if j+1>k: break
    t+=l[j]
    a=max(a,t+(k-j-1)//m*s*(s>0))
print(a)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K = map(int, readline().split())
    P = [int(s) - 1 for s in readline().split()]
    C = list(map(int, readline().split()))

    ans = -INF
    for i in range(N):
        score = []
        total = 0
        x = i
        while True:
            x = P[x]
            score.append(C[x])
            total += C[x]
            if x == i:
                break

        l = len(score)
        csum = 0
        for i in range(l):
            if i + 1 > K:
                break
            csum += score[i]
            res = csum
            if total > 0:
                res += (K - (i + 1)) // l * total

            if ans < res:
                ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
for i in range(N):
    P[i] -= 1
C = list(map(int, input().split()))
 
ans = -(10 ** 18)
 
for si in range(N):
    x = si
    loop = []
    total = 0
    while 1:
        x = P[x]
        loop.append(C[x])
        total += C[x]
        if x == si:
            break
    T = len(loop)  # 周期の大きさ
    tmp = 0
    for i in range(T):
        tmp += loop[i]
        if K < i + 1:
            break
        now = tmp
        if total > 0:  # loopの和が正ならloopを回した方がお得
            loop_times = (K - (i + 1)) // T  # 何周できるか
            now += total * loop_times
        ans = max(ans, now)
 
print(ans)