Problem:


Score : 400 points

Problem Statement

Takahashi will play a game using a piece on an array of squares numbered 1, 2, \cdots, N. Square i has an integer C_i written on it. Also, he is given a permutation of 1, 2, \cdots, N: P_1, P_2, \cdots, P_N.

Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between 1 and K (inclusive):

In one move, if the piece is now on Square i (1 \leq i \leq N), move it to Square P_i. Here, his score increases by C_{P_i}.

Help him by finding the maximum possible score at the end of the game. (The score is 0 at the beginning of the game.)

Constraints

2 \leq N \leq 5000

1 \leq K \leq 10^9

1 \leq P_i \leq N

P_i \neq i

P_1, P_2, \cdots, P_N are all different.

-10^9 \leq C_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_1 P_2 \cdots P_N
C_1 C_2 \cdots C_N

Output

Print the maximum possible score at the end of the game.

Sample Input 1

5 2
2 4 5 1 3
3 4 -10 -8 8

Sample Output 1

8

When we start at some square of our choice and make at most two moves, we have the following options:

If we start at Square 1, making one move sends the piece to Square 2, after which the score is 4. Making another move sends the piece to Square 4, after which the score is 4 + (-8) = -4.

If we start at Square 2, making one move sends the piece to Square 4, after which the score is -8. Making another move sends the piece to Square 1, after which the score is -8 + 3 = -5.

If we start at Square 3, making one move sends the piece to Square 5, after which the score is 8. Making another move sends the piece to Square 3, after which the score is 8 + (-10) = -2.

If we start at Square 4, making one move sends the piece to Square 1, after which the score is 3. Making another move sends the piece to Square 2, after which the score is 3 + 4 = 7.

If we start at Square 5, making one move sends the piece to Square 3, after which the score is -10. Making another move sends the piece to Square 5, after which the score is -10 + 8 = -2.

The maximum score achieved is 8.

Sample Input 2

2 3
2 1
10 -7

Sample Output 2

13

Sample Input 3

3 3
3 1 2
-1000 -2000 -3000

Sample Output 3

-1000

We have to make at least one move.

Sample Input 4

10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719

Sample Output 4

29507023469

The absolute value of the answer may be enormous.



Sample input:
5 2
2 4 5 1 3
3 4 -10 -8 8


Sample output:
8

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = max(C)
for i in range(N):
    check = {i}
    loop_score =[]
    k = i
    while True:
        loop_score.append(C[k])
        k = P[k]-1
        t = len(check)
        check.add(k)
        if len(check)==t:
            break
    cum_score = 0
    cum_scores = []
    for j in loop_score:
        cum_score+=j
        cum_scores.append(cum_score)
    loop = cum_scores[-1]
    compare = min(0,max(cum_scores))
    loops = K//len(cum_scores)
    plus = K%len(cum_scores)
    if loop > 0:
        compare = 0
        compare+=loops*loop
    final = cum_scores[:plus]
    if K < len(cum_scores):
        cum_scores = cum_scores[:K]
    if plus != 0:
        compare+=max(final)
    if max(cum_scores)>compare:
        compare = max(cum_scores)
    if compare>ans and compare!=0:
        ans = compare
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
p_i = list(map(int, input().split()))
c_i = list(map(int, input().split()))
cnt = k % n
if cnt == 0: cnt += n
pList = [[0 for i in range(n)] for i in range((cnt) + 1)]
ansList = [[0 for i in range(n)] for i in range(cnt)]
ans = 0
score = [0] * n
for x in range(n):
    val = p_i[x]
    pList[0][x] = val
    score[x] = c_i[val - 1]
sumScore = sum(score)
if n < k and sumScore > 0: ans += (k // n) * sumScore
for x in range(cnt):
    for y in range(n):
        val = pList[x][y]
        pList[x+1][y] = pList[0][val - 1]
        if x != 0: ansList[x][y] = c_i[val - 1] + ansList[x - 1][y]
        else: ansList[x][y] = c_i[val - 1]
ans += max(list(map(lambda x: max(x), ansList)))
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=0
check=set()

for i in range(N):
    
    if i in check:
        continue
    
    # create loop
    tmpK=K
    tmpans=0
    loop_check=set()
    tmp_idx=i
    loop=[]
    while tmp_idx not in loop_check:
        loop.append(C[tmp_idx])
        loop_check.add(tmp_idx)
        check.add(tmp_idx)
        tmp_idx=P[tmp_idx]
    
    S=sum(loop)
    L=len(loop)
    if S>=0:
        tmpans=S*(tmpK//L)
        tmpK%=L
    
    # 部分最大列を検索
    #print('loop',loop)
    loop*=2
    for i in range(len(loop)-1):
        loop[i+1]+=loop[i]
    n=2*L
    def init_min(init_min_val):
        #set_val
        for i in range(n):
            seg_min[i+num_min-1]=init_min_val[i]    
        #built
        for i in range(num_min-2,-1,-1) :
            seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2])
    def query_min(p,q):
        if q<=p:
            return ide_ele_min
        p += num_min-1
        q += num_min-2
        res=ide_ele_min
        while q-p>1:
            if p&1 == 0:
                res = min(res,seg_min[p])
            if q&1 == 1:
                res = min(res,seg_min[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = min(res,seg_min[p])
        else:
            res = min(min(res,seg_min[p]),seg_min[q])
        return res
    #####単位元######
    ide_ele_min = 10**10
    #num_min:n以上の最小の2のべき乗
    num_min =2**(n-1).bit_length()
    seg_min=[ide_ele_min]*2*num_min

    init_min(loop)
    local_max=0
    for i,v in enumerate(loop):
        if i>0:
            #print('v,min=',v,query_min(max(0,i-tmpK),i),v-query_min( max(0,i-tmpK),i ))
            local_max=max(local_max,v-query_min( max(0,i-tmpK),i ) )
    
    ans=max(ans,local_max+tmpans)

if ans==0:
    print(max(C))
else:
    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 st in range(N):
	now = st+1
	temp=[0]
	while(P[now-1] != st+1):
		temp.append(temp[-1]+C[P[now-1]-1])
		now = P[now-1]
	temp.append(temp[-1]+C[P[now-1]-1])
	if temp[-1]<=0:
		ans = max(ans, (max(temp[1:min(len(temp), K+1)])))
	else:
		t=temp[-1]*(K//(len(temp)-1))
		t+=max(temp[:1+K%(len(temp)-1)])
		ans=max(ans, t)
		
print(int(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()))
sumC = sum(C)
if sumC > 0:
    t = sumC * (K // N)
    remainMove = K % N
    m = 10**9 * (-1) -1
    if remainMove ==0:
        m = 0

    for i in range(N):
      now = 0
      pos = P[i] - 1
      for j in range(remainMove):
        now += C[pos]
        pos = P[pos]-1
        m = max(now, m)
    print(m+t)
else:
    remainMove = N
    m = 10**9 * (-1) -1
    for i in range(N):
      now = 0
      pos = P[i] - 1
      for j in range(remainMove):
        now += C[pos]
        pos = P[pos]-1

        #print(now)
        m = max(now, m)
    print(m)

Submission status: Wrong Answer

Solution code:
# どう考えてもK>5000でループが起きるので，
# dp[k][i]:= k回まで，移動したときの最大の値とすればよい
# -infで初期化
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

dp = [[-float('inf') for _ in range(N)] for __ in range(5000)]
for i,c in enumerate(C):
    dp[0][i] = 0
max_val = -float('inf')
if K<(5000-1):
    for i in range(K):
        for j in range(N):
            next_cell = P[j] - 1
            dp[i + 1][next_cell] = max(dp[i][j] + C[next_cell], dp[i + 1][next_cell])
            max_val = max(dp[i + 1][next_cell], max_val)
    print(max_val)
    exit()

for i in range(5000-1):
    for j in range(N):
        next_cell = P[j]-1
        dp[i+1][next_cell] = max(dp[i+1][next_cell] + C[next_cell], dp[i+1][next_cell])
        max_val = max(dp[i+1][next_cell],max_val)
print(max_val)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, PS, CS):
    PS = [x - 1 for x in PS]
    CS = [CS[PS[i]] for i in range(N)]
    PSS = [PS]
    CSS = [CS]
    prevPS = PS
    prevCS = CS
    for i in range(30):
        PS2 = [prevPS[prevPS[i]] for i in range(N)]
        CS2 = [prevCS[i] + prevCS[prevPS[i]] for i in range(N)]
        PSS.append(PS2)
        CSS.append(CS2)
        prevPS = PS2
        prevCS = CS2

    score = [0] * N
    pos = list(range(N))
    length = [0] * N
    maxbit = K.bit_length() - 1
    for i in range(maxbit, -1, -1):
        # debug(": i", i)
        # debug(": 2**i", 2**i)
        # debug(": CSS[i]", CSS[i])
        # debug(": PSS[i]", PSS[i])
        # debug(": score", score)
        # debug(": length", length)
        for j in range(N):
            # debug(": length[j] + 2 ** i <= K", length[j] + 2 ** i <= K)
            # debug(": CSS[i][pos[j]]", CSS[i][pos[j]])
            if length[j] + 2 ** i <= K and CSS[i][pos[j]] > 0:
                # debug("add: j", j)
                score[j] += CSS[i][pos[j]]
                pos[j] = PSS[i][pos[j]]
                length[j] += 2 ** i
            if CSS[i][j] > score[j]:
                # debug("reset: j", j)
                # debug(": CSS[i][i], score[j]", CSS[i][i], score[j])
                pos[j] = PSS[i][j]
                score[j] = CSS[i][j]
                length[j] = 2 ** i

    # debug("finish: score", score)
    ret = max(score)
    if ret == 0:
        ret = max(CS)
    return ret


def main():
    # parse input
    N, K = map(int, input().split())
    PS = list(map(int, input().split()))
    CS = list(map(int, input().split()))
    print(solve(N, K, PS, CS))


# tests
T1 = """
5 2
2 4 5 1 3
3 4 -10 -8 8
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
8
"""

T2 = """
2 3
2 1
10 -7
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
13
"""

T3 = """
3 3
3 1 2
-1000 -2000 -3000
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
-1000
"""

T4 = """
10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
29507023469
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# 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 make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

n,k = lr()
p = lr()
c = lr()
visited = [True for i in range(n)]
ans = -inf

for i in range(n):
    if visited[i]:
        add_list = [i+1]
        visited[i] = False
        tmp = p[i]-1
        pre = 0
        while visited[tmp]:
            pre+=1
            visited[tmp] = False
            add_list.append(tmp+1)
            tmp = p[tmp]-1
        pre_ans = -inf
        length = len(add_list)
        a1 = [0]
        for m in range(2*length):
            a1.append(a1[-1]+c[add_list[m%length]-1])
        pre_total = a1[length]
        ret_ind = k%length
        for ind in range(1, ret_ind+1):
            for m in range(length):
                pre_ans = max(pre_ans, a1[m+ind]-a1[m])
        u = k//length
        if pre_total > 0:
            pre_ans+=(u*pre_total)
        ans = max(ans, pre_ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N,K = isRaw()
    Ps = isRaw()
    Cs = isRaw()
    ans = -INF
    for n in range(N):
        curPos = n
        cycles =[]
        visited = {}
        lastCost = 0
        vidx = 0
        loopStart = -1
        while True:
            visited[curPos] = vidx
            cycles.append(lastCost+Cs[curPos])
            curPos= Ps[curPos]-1
            lastCost = cycles[-1]
            if curPos in visited:
                loopStart = visited[curPos]
                break
        
        lc = len(cycles)
        divK = K//lc
        score = 0
        cFlag = False
        if divK>=1:
            if cycles[-1]>=0:
                score+=cycles[-1]*divK
                cFlag =True
        if K%lc ==0:
            if cFlag:
                score = max(score, cycles[-1]*(divK-1)+max(cycles))
            else:
                score = max(cycles)
        else:
            if cFlag:
                score += max(cycles[:K % lc]+[0])
            else:
                score += max(cycles[:K % lc])
        


        ans = max(score,ans)
    print (ans)

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

max_score = -10 ** 9 - 1
for i in range(n):
    tmp_score=-10**9 -1
    score = 0
    count = 0
    next_point = p[i] - 1
    while next_point != i and count < k:
        score += c[next_point]
        next_point = p[next_point] - 1
        count += 1
        if tmp_score < score:
            tmp_score = score
            max_count = count
    score += c[next_point]
    count += 1
    if tmp_score < score:
        tmp_score = score
        max_count = count

    cycle_score = score
    if cycle_score > 0 and count < k:
        score = cycle_score * (k // count)
        tmp_k = k - ((k // count)*count)
        count=0
        next_point=p[i]-1
        under_k_score=-10**9-1
        score2=0
        while next_point != i and count < tmp_k:
            score2 += c[next_point]
            next_point = p[next_point] - 1
            count += 1
            if under_k_score < score2:
                under_k_score = score2
                max_count = count
        if under_k_score+cycle_score > tmp_score:
            score += under_k_score
        else:
            score += -cycle_score + tmp_score
        if max_score < score:
            max_score=score
    else:
        if max_score < tmp_score:
            max_score=tmp_score

print(max_score)

Submission status: Wrong Answer

Solution code:
def func(i, k, tmp):
    score = -10**18
    ck = 0
    cycle = 1
    cp = i
    while ck < k:
        ck += 1
        np = p[cp]
        nc = c[np]
        tmp += nc
        score = max(score, tmp)
        
        cp = np
        if np == i:
            if tmp > 0:
                cycle = k // ck
                score = func(i, k % ck, tmp * cycle)
            break
    return score
  
  
n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

ans = -10**18
for i in range(1, n+1):
    score = func(i, k, 0)
    ans = max(ans, score)
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()))
raw = []
seen = [0 for _ in range(n)]
for i in range(n):
  now = int(i)
  tmp = []
  if seen[i]:
    continue
  while seen[now] == 0:
    tmp.append(c[now])
    seen[now] = 1
    now = p[now] - 1
  raw.append(tmp)
#print(raw)
can = 0
for x in raw:
  sun = sum(x)
  l = len(x)
  x = x + x + x
  #print(x)
  now = [0]
  for y in x:
    now.append(now[-1]+y)
  #print(now)
  if sun > 0 and k >= l:
    ans = sun* (k//l-1)
    k = k % l + l
    #print(ans,k)
    maxi = 0
    for i in range(3*l+1):
      for j in range(i+1,3*l+1):
        if j - i <= k:
          #print(now[j]-now[i],j-i,bool(268==now[j]-now[i]))
          maxi = max(maxi,now[j]-now[i])
    #print(maxi)
    #print('#',maxi)
    #print('#',sun)
    #print(k)
    can = max(ans+maxi,can)
    #print(maxi)
    #print(ans+maxi)
  else:
    maxi = 0
    for i in range(3*l+1):
      for j in range(i+1,3*l+1):
        if j - i <= k:
          maxi = max(maxi,now[j]-now[i])
    #print(maxi)
    can = max(maxi,can)
if can == 0:
  print(max(c))
else:
  print(can)

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()))
    max_cost = [0]*n
    ans = -10**10
    for i in range(n):
        s = i+1
        pi = p[i]
        cost = c[i]
        big = c[i]
        max_cost = [0]*n
        num = 1
        while pi != s:
            big = max(big, cost)
            max_cost[num] = big
            cost += c[pi-1]
            pi = p[pi-1]
            num += 1
        if cost <= 0:
            ans = max(ans, big)
        else:
            number = k//num
            ans = max(ans, number*cost + max(max_cost[k%num], 0))
    print(ans)
            

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections
def main():

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

    ans = float('-inf')
    if K <= N:
        for i in range(N):
            v = 0
            k = i
            for j in range(K):
                k = P[k]-1
                v += C[k]
                ans = max(ans, v)
        return ans

    for i in range(N):
        visited = dict()
        k = i
        visited[i] = 0
        val = [0]
        v = 0
        for j in range(1, N+2):
            k = P[k] - 1
            if k not in visited:
                visited[k] = j
                val.append(C[k])
                v += C[k]
                ans = max(ans, v)
            else:
                m = visited[k]
                t = j - m
                val.append(C[k])
                v += C[k]
                ans = max(ans, v)
                # print(val, j, visited[k])
                val1 = val[:m+1]
                val2 = val[m+1:]
                period = sum(val2)
                pre = sum(val1)
                if period > 0:
                    n = (K - visited[k]) // t
                    u = 0
                    max_u = 0
                    for p in range((K-visited[k]) % t):
                        u += val2[p]
                        max_u = max(max_u, u)
                    ans = max(ans, max_u + pre + period * n)
                break


    return ans


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
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()}

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
if K == 1:
    print(max(C))
    import sys
    sys.exit()
uf = UnionFind(N)
for i in range(N):
    uf.union(i, P[i]-1)

ans = -float("inf")
for x in uf.all_group_members().values():
    n = len(x)
    m_score = [-float("inf")] * (n+1)
    m_score[0] = 0
    sum_c = 0
    for i in x:
        tmp_score = 0
        tmp_pos = i
        sum_c += C[i]
        for j in range(n):
            tmp_pos = P[tmp_pos]
            tmp_pos -= 1
            tmp_score += C[tmp_pos]
            m_score[j+1] = max(tmp_score, m_score[j+1])
    if sum_c <= 0:
        ans = max(max(m_score[1:]), ans)
    elif K <= n:
        ans = max(ans, max(m_score[:K+1]))
    else:
        ans = max(sum_c * (K//n) + max(m_score[:(K%n)+1]), ans)
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
        _ans1=c*l[i][roop_count]
        k=K%roop_count
        _ans1+=max(l[i][1:k+1]+[0])
        if c>1:
          _ans2=(c-1)*l[i][roop_count]
          _ans2+=max(l[i][1:k+1]+[0])
          ans=max(ans,_ans1,_ans2)
        else:
          ans=max(ans,_ans1)

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
n,k= list(map(int, input().split()))
i= list(map(int, input().split()))
j= list(map(int, input().split()))
x=sum(j)

max_lis=[-1000000000000000]*n
kaisuu=k%n
if x>0:
    for aaa in range(1,kaisuu+1):
    
        
        for siten in range(n):
            ans=0
            l=0
            m=siten
            while l<aaa:
                ans+=j[i[siten]-1]
                siten=i[siten]-1
                if max_lis[m-1]<ans:
                    max_lis[m-1]=ans
                l+=1

    anns=k//n
    print(anns*x+max(max_lis))
else:
    if n>k:
        for aaa in range(1,k):
            
            
            for siten in range(n):
                ans=0
                l=0
                m=siten
                while l<k:
                    ans+=j[i[siten]-1]
                    siten=i[siten]-1
                    if max_lis[m-1]<ans:
                        max_lis[m-1]=ans
                    l+=1
    for aaa in range(1,n):
            
            
            for siten in range(n):
                ans=0
                l=0
                m=siten
                while l<k:
                    ans+=j[i[siten]-1]
                    siten=i[siten]-1
                    if max_lis[m-1]<ans:
                        max_lis[m-1]=ans
                    l+=1
    print(max(max_lis))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
lis=[]
op=p[:]
s=op.pop(0)
visited=set()
while op:
    flag=0
    while s in visited:
        if op: s=op.pop(0)
        else:
            flag=1
            break
    if flag: break
    temp=[]
    while s not in visited:
        temp.append(s)
        visited.add(s)
        s=p[s-1]
    lis.append(temp)
flag=0
ans=0
for t in lis:
    temp=len(t)
    j=0
    for i in t: j+=c[i-1]
    temp=k%temp
    l=t+t[0:temp]
    r=0
    for i in l[0:temp]: r+=c[i-1]
    m=r
    for i in range(len(t)):
        r-=c[l[i]-1]
        r+=c[l[i+temp]-1]
        m=max(m,r)
    ans=max(ans,m+(k//len(t))*j)
print(ans)

Submission status: Wrong Answer

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

pList = list(map(int,input().split()))

cList = list(map(int,input().split()))

cSum = sum(cList)

ans = 0
p = {}
c = {}

for i in range(n):
    p[i] = pList[i]
    c[i] = cList[i]


if k > n * 2:
    if cSum > 0:
        ans += cSum * ((k // n) - 1)
        k = n + k % n

highScore = min(c)
for i in range(n):
    count = 0
    zahyou = i
    score = 0
    while count < k:
        zahyou = p[zahyou] - 1
        score += c[zahyou]
        count += 1
        if highScore < score:
            highScore = score



#print(ans,highScore,cSum)
print(ans+highScore)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    P = tuple(map(lambda x: int(x) - 1, input().split()))
    C = tuple(map(int, input().split()))
    ans = -10**18

    for i in range(N):
        k = K
        D = [[0, 0] for i in range(N)]
        x = i
        X, Y = 0, 0
        count = 0
        score = 0
        for j in range(K):
            if D[P[x]][0] == 0:
                score += C[P[x]]
                D[P[x]][0] = score
                D[P[x]][1] = count
                x = P[x]
                count += 1
            else:
                X = D[P[x]][0] - C[P[x]]
                score -= X
                L = (count - D[P[x]][1])
                k -= D[P[x]][1]
                score2 = score
                score *= k // L
                l = K % L
                score += X
                ans = max(ans, score)
                for h in range(N):
                    if D[h][1] <= l + D[P[x]][1] - 1:
                        ans = max(ans, score + D[h][0] - X)
                        ans = max(ans, score2 + D[h][0] - X)
                break
            if score > ans:
                ans = score
    print(ans)


main()

Submission status: Wrong Answer

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()))
if max(c) <= 0:
    print(max(c))
    exit()
ans = 0
for begin in range(n):
    i = p[begin]
    s = c[i]
    round = 1
    score = 0
    kk = 0
    while i != begin:
        i = p[i]
        s += c[i]
        round += 1
    if k < round:
        kk = k
    else:
        if s > 0:
            score += s * (k // round)
            kk = k % round
        else:
            kk = round
    smax = 0
    now = 0
    i = begin
    while kk > 0:
        i = p[i]
        now += c[i]
        smax = max(now, smax)
        kk -= 1
    score += smax
    ans = max(ans, score)

print(ans)