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(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))
INF = 10**18
ans = -INF
for i in range(N):
    arr = []
    tot = 0
    rest = K
    visited = {}
    visited[i] = rest
    point = {}
    point[i] = 0
    nex = i
    while rest:
        nex = P[nex]
        tot += C[nex]
        arr.append(tot)
        rest -= 1
        if nex in visited:
            loop = visited[nex]-rest
            loop_point = tot-point[nex]
            if loop_point > 0:
                tot += (rest//loop)*loop_point
                arr.append(tot)
                rest = rest%loop
                # print("visited", loop, rest, arr)
            else:
                rest = min(rest, loop)
            while rest:
                nex = P[nex]
                tot += C[nex]
                arr.append(tot)
                rest -= 1
            break
        else:
            visited[nex] = rest
            point[nex] = tot
    #print(i, arr)
    ans = max(ans, max(arr))
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

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

p=list(map(int,input().split()))
p=[q-1 for q in p]
# 順列
c=list(map(int,input().split()))

# ループを発見したい
# from pprint import pprint

loopcnt=[]
visited=[]

for i in range(n):
    first=p[i]
    if first in visited:
        continue
    now=first
    vs=set([now])
    for j in range(n):
        now=p[now]
        if now in visited:
            continue
        visited.append(now)
        if now in vs:
            loopcnt.append(vs)
            continue
        vs.add(now)
        
lll=[]
for item in loopcnt:
    point=0
    for v in item:
        point+=c[v]
        
    lll.append((list(item),point))

anslist=[]

for sss,ppp in lll:
    # print(sss,pspp)
    ls=len(sss)
    if ppp<=0:
        ans=max(c)
        for i in range(ls):
            now=sss[i]
            point=0
            for j in range(ls):
                now=p[now]
                point+=c[now]
                ans=max(ans,point)
        anslist+=(ans),
    else:
        ans=max(c)
        for i in range(ls):
            now=sss[i]
            point=0
            for j in range(k%ls):
                now=p[now]
                point+=c[now]
                ans=max(ans,point)
        anslist+=(ans+ppp*(k//ls)),
        
print(max(anslist))

Submission status: Wrong Answer

Solution code:
def resolve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))

    ans = -100100100
    for i in range(N):
        node_set = set()
        n = P[i]
        score = 0
        t = []
        while n not in node_set:
            score += C[n-1]
            t.append(score)
            node_set.add(n)
            n = P[n-1]

        if K < len(t):
            max_t = max(t[:K])
        else:
            max_t = max(t)
            if t[-1] > 0:
                temp = t[-1] * int(K / len(t)) + max([0] + t[:K%len(t)])
                max_t = max(max_t, temp)
        ans = max(ans, max_t)

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
C=[0]+list(map(int,input().split()))
P=[0]+list(map(int,input().split()))
D=[0 for i in range(N+1)]
D[0]=2
ANS=-10**20
for z in range(1,N+1):
    if D[z]==0:
        D[z]=1
        X=[[0,z]]
        for i in range(N*2):
            if D[X[-1][1]]!=3:
                D[X[-1][1]]+=1
                X.append([X[-1][0]+P[C[X[-1][1]]],C[X[-1][1]]])
            else:
                break
        #print(X)
        roop=(len(X)-1)//2
        
        Roop=max(0,X[roop][0])
        #print(roop)
        k=K%roop
        f=0
        if k==0:
            f=1
            k=roop
        cnt=0
        for i in range(1,k+1):
            for j in range(roop):
                #print(i+j,j)
                cnt=max(cnt,X[i+j][0]-X[j][0])
                #print(cnt)
        #print(cnt)
        ANS=max(ANS,(K//roop)*(Roop)+cnt)
for i in range(1,N+1):
    if C[i]==i:
        if P[i]*K>ANS:
            ANS=P[i]*K
if max(P[1:])<0:
    print(max(P[1:]))
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()))

max_score = -10**18
for i in range(N):
  score = 0
  count = 0
  index = []
  j = i
  n = 0
  for _ in range(N):
    j = P[j]-1
    index.append(i)
    count += C[j]
    n += 1
    if j == i:
      break
  k = K%n
  score = (K//n)*count
  if score < 0:
    score = 0
    if k == 0:
      k = 1
  max_v = -10**18
  v = 0
  for _ in range(k):
    j = P[j]-1
    v += C[j]
    max_v = max(max_v, v)
  max_score = max(max_score, score+max_v)

print(max_score)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
L = [0]*N
Max = -10**9
for i in range(N):
    if L[i] != 0:
        continue
    else:
        c = 0
        L[i] = 1
        c += C[i]
        a = P[i] - 1
        Cs = [c]
        Ds = [c]
        l = 1
        while a != i:
            c += C[a]
            Ds.append(C[a])
            a = P[a]-1
            L[a] = 1
            l += 1
            Cs.append(c)
        if c > 0:
            m = -10**9
            k = K % l
            for i in range(1,k+1):
                for j in range(l):
                    if j + i > l:
                        M = Cs[l-1] - Cs[j]+Ds[j] + Cs[i+j-l-1]
                    else:
                        M = Cs[j+i-1]-Cs[j]+Ds[j]
                    if M > m:
                        m = M
            x = K // l
            max0 = c*x+m
        else:
            if K >= l:
                A = [0]*l
                A[0] = Ds[0]
                for i in range(1,l):
                    A[i] = min([A[i-1]+Ds[i],Ds[i]])
                max0 = c - A[l-1]
                if max0 == 0:
                    max0 = max(Ds)
            else:
                m = -10**9
                k = K
                for i in range(1,k+1):
                    for j in range(l):
                        if j + i > l:
                            M = Cs[l-1] - Cs[j]+Ds[j] + Cs[i+j-l-1]
                        else:
                            M = Cs[j+i-1]-Cs[j]+Ds[j]
                        if M > m:
                            m = M
                max0 = m
    if Max < max0:
        Max = max0
print(Max)

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
            lastCost = lastCost+Cs[curPos]
            cycles.append(lastCost)
            curPos= Ps[curPos]-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
        modK = K%lc
        if modK == 0:
            if cFlag:
                score = max(score, cycles[-1]*(divK-1)+max(cycles))
            else:
                score = max(cycles)
        else:
            if cFlag:
                score = max(score+max(cycles[:modK]+[0]),
                            cycles[-1]*(divK-1)+max(cycles))
                #score += max(cycles[:modK]+[0])
            else:
                score += max(cycles[:modK])
        


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

         
main()

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n,k = ma()
Pt = lma()
P = [p-1 for p in Pt]
C = lma()
class unionfind():
    def __init__(self,n):
        self.par = list(range(n))
        self.size = [1]*n
        self.rank = [0]*n

    def root(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:return
        else:
            if self.rank[x] < self.rank[y]:
                 x,y = y,x
            if self.rank[x] == self.rank[y]:
                self.rank[x]+=1
            self.par[y] = x
            self.size[x] +=self.size[y]
    def get_size(self,x):
        x = self.root(x)
        return self.size[x]
uf = unionfind(n)
for i in range(n):
    uf.unite(i,P[i])

def score(x):#xからスタートしたスコア
    l = uf.get_size(x)
    p,r = divmod(k,l)
    tmp = [-10**10 for i in range(l+1)]#一回の累積和
    tmp_p = [-10**10 for i in range(l+1)] #pサイクル目の累積和
    ret = 0
    if p==0:
        xt = x
        mx = -10**10
        for i in range(r):
            nex = P[xt]
            ret+=C[nex]
            xt = nex
            mx = max(mx,ret)
        return mx

    gain_cycle = 0
    xt=x
    for i in range(l):
        nex = P[xt]
        gain_cycle +=C[nex]
        ret+=C[nex]
        tmp[i+1] = ret
        if i<=r-1:
            tmp_p[i+1]=ret
        xt = nex
    if gain_cycle>0:
        return max(tmp_p) + p* gain_cycle
    else:
        return max(tmp)

        #print(ret,"ret")

ans = -10**10
for i in range(n):
    ans = max(ans,score(i))
print(ans)

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, 2*N+1):
            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)
                n = (K - m) // t
                u = 0
                ans = max(ans, u + pre + period * n)
                for p in range((K-m) % t):
                    u += val2[p]
                    ans = max(ans, u + pre + period * n)
                break

    return ans


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

Submission status: Wrong Answer

Solution code:
import sys, math
from functools import lru_cache
from collections import defaultdict
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, K = mi()
    P = list(mi())
    C = list(mi())
    m = -10**100

    loop = [(-1, 0)]*N
    for i in range(N):
        if loop[i][0] != -1:
            continue
        now = P[i]-1
        T = 1
        s = C[now]
        l = [now]
        while now != i:
            now = P[now]-1
            s += C[now]
            T += 1
            l.append(now)
        for v in l:
            loop[v] = (T, s)

    # print(*loop, sep='\n')

        

    ans = -10**100
    # iから始める
    for i in range(N):
        # loopの周期、総和を取得
        T, s = loop[i]

        # loop周回回数
        n = K//T if s > 0 else 0

        # loopをn周した後のscore
        tmp = s*n

        # 残り回数
        rest = K%T if s > 0 else T

        # 残りで移動させた時の最大値を計算
        now = i
        s = 0
        for _ in range(rest):
            now = P[now]-1
            s += C[now]
            m = max(m, s)

        ans = max(ans, tmp+m)

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, K = read_ints()
    P = [p-1 for p in read_ints()]
    C = read_ints()

    max_score = -math.inf
    for i in range(N):
        cycle_score = C[i]
        scores = [0, C[i]]
        j = P[i]
        k = K
        while k > 1 and i != j:
            cycle_score += C[j]
            scores.append(cycle_score)
            j = P[j]
            k -= 1
        max_score = max(max_score, max(scores[1:]))
        if i == j:
            cycle_size = len(scores)-1
            cycle_count = K//cycle_size
            max_score = max(max_score, max(scores[1:]), cycle_score*cycle_count+max(scores[:K%cycle_size+1]))
    return max_score


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

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
P = list(map(int,input().split()))
P.insert(0,0)
C = list(map(int,input().split()))
C.insert(0,0)

ans = -10**9
loops = {}
if 5000 < K:
    for i in range(1,N+1):
        p = i
        k = K
        max_score = -10**9
        score = 0
        visited = set([p])
        visited_lst = [p]
        score_lst = [0]
        while 0 < k:
            score += C[P[p]]
            max_score = max(max_score,score)
            score_lst.append(score)
            p = P[p]
            k -= 1
            if P[p] == p:
                score += C[P[p]]*k
                k = 0
            if p in visited:
                if p in loops:
                    if 0 < loops[p][0]:
                        score += loops[p][0]*(k//loops[p][1])
                        k %= loops[p][1]
                        visited = set([p])
                        visited_lst = [p]
                        score_lst = [score]
                    else:
                        break
                else:
                    idx = visited_lst.index(p)
                    l = len(score_lst)-1-idx
                    for j in range(idx,l):
                        loops[visited_lst[j]] = [score-score_lst[idx],l]
                    if 0 < score-score_lst[idx]:
                        score += (score-score_lst[idx])*(k//l)
                        k %= l
                        visited = set([p])
                        visited_lst = [p]
                        score_lst = [score]
                    else:
                        break
            else:
                visited.add(p)
                visited_lst.append(p)
        # print(max_score)
        max_score = max(max_score,score)
        ans = max(ans,max_score)
    # print(loops)
else:
    for i in range(1,N+1):
        p = i
        k = K
        max_score = -10**9
        score = 0
        while 0 < k:
            score += C[P[p]]
            max_score = max(max_score,score)
            p = P[p]
            k -= 1
        ans = max(ans,max_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()))
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 len(temp)>=K+1:
		ans=max(ans, max(temp[1:K+1]))
		continue
	if temp[-1]<=0:
		ans = max(ans, (max(temp[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 = [int(n) for n in input().split(" ")]
Ps = [int(n) for n in input().split(" ")]
Cs = [int(n) for n in input().split(" ")]

"""
N = 10
K = 58
Ps = [9, 1, 6, 7, 8, 4, 3, 2, 10, 5]
Cs = [695279662, 988782657, -119067776, 382975538, -151885171, -177220596, -169777795, 37619092, 389386780, 980092719]
"""
"""
N = 3
K = 3
Ps = [3, 1, 2]
Cs = [-1000,-2000,-3000]
"""

circles = []
already = {}
for p in range(N):
    if p not in already:
        tmp = []
        nowp = p
        while nowp not in tmp:
            tmp.append(nowp)
            already[nowp] = 1
            nowp = Ps[nowp] - 1
        circles.append(tmp)

#print(circles)

finalResult = -100000000000

def getCircleScore(circle, start, kk):
    #print(circle, start, kk)
    s = 0
    for k in range(kk):
        index = start + k
        if index >= len(circle):
            index = index % len(circle)
        s += Cs[circle[index]]
    return s

"""
maxCircle = []
maxCircleScore = -10000000000
maxIndex = 0
for circle in circles:
    CircleSum = sum([Cs[n] for n in circle])
    if maxCircleScore <= CircleSum:
        maxCircleScore = CircleSum
        maxCircle = circle
"""
#for circle in [maxCircle]:
for circle in circles:
    
    CircleSum = sum([Cs[n] for n in circle])
    #print(circle, CircleSum)
    score = 0
    if CircleSum > 0:
        score = K // len(circle) * CircleSum

    K = K % len(circle)
    if K == 0:
        K = len(circle)

    maxScore = -100000000000
    for start in range(len(circle)):
        #print("start", start)
        for kk in range(1, K+1):
            s = getCircleScore(circle, start, kk)
            #print(s)
            if maxScore <= s:
                maxScore = s

    final = score + maxScore

    if final >= finalResult:
        finalResult = final

print(finalResult)