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: Runtime Error

Solution code:
X,K,D = map(int, input().split())  

if X == 0:
    if K % 2 == 0:
        print(0)
    else:
        print(D)
        
elif X > 0 :
    if X // D >= K:
        print(X - K*D)
    else:
        K -= X // D
        X %= D
        if K % 2 == 0:
            print(X)
        else:
            print(abs(X-D))
else:
    if (-X // D) >= K:
        print(X + K*D)
    else:
        X, K = X + (-X // D)*D , K - (-X // D)
        if K % 2 == 0:
            print(-X)
        else:
            print(abs(X+D))

Submission status: Runtime Error

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


visited = [False] * (N + 1)

def iter(i, cycle):
    global visited, P
    # print("#",i)
    if visited[i]:
        return cycle
    visited[i] = True
    return iter(P[i], cycle + [C[P[i]]])

def solve(cycle, k):
    ans = -10000000000000
    for i in range(len(cycle)):
        score = 0
        for j in range(k):
            score += cycle[(i + j) % len(cycle)]
            ans = max(ans, score)
            # print(score, ans)
    # print("#", ans)
    return ans

cycles = []
for i in range(1, N + 1):
    if visited[i]:
        continue
    cycles.append(iter(i, []))

# print(cycles)

ans = -10000000000000
for cycle in cycles:
    s = sum(cycle)
    l = len(cycle)
    if s < 0:
        score = solve(cycle, min(l, K))
    else:
        score = solve(cycle, min(l, K))
        score = max(score, solve(cycle, K % l) + K // l * s)
    ans = max(ans, score)

print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
for i in range(0,N):
  y = 0
  x = i
  for j in range(0,K):
    
    x = round(P[x])
    y = y+C[round(x)]
    z = max(0,y)
  w = max(0,z)
print(w)

Submission status: Runtime Error

Solution code:
x,k,d=map(int,input().split())
while k!=0:
    if x-(k*d)>0:
        x=x-(k*d)
        break
    if x-d==0:
        if k%2 ==0:
            break
        else:
            x=x-d
            break
    if x-d < 0 :
        if abs(x-d)<x:
            x=abs(x-d)
            break
        else:
            break
    else :
        x=x-d
        k=k-1

print (x)

Submission status: Runtime Error

Solution code:
def main():
    cells, moves = [int(x) for x in input().split()]
    nexts = [int(x) - 1 for x in input().split()]
    scores = [int(x) for x in input().split()]
    ans = - 10 ** 9 - 5
    for start in range(cells):
        route = []
        seen = [False] * cells
        now = start
        for _step in range(cells):
            nex = nexts[now]
            if seen[nex]:
                break
            route.append(scores[nex])
            now = nex
            seen[now] = True
        print(route)
        length = len(route)
        total = sum(route)
        if total > 0 and moves > length:
            q, mod = divmod(moves, length)
            candidate = max(sum(route[:x + 1]) for x in range(mod)) + total * q
        else:
            candidate = max(sum(route[:x + 1])
                            for x in range(max(min(moves, length), 1)))
        ans = max(ans, candidate)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n, k = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
c = [int(x) for x in input().split()]

ans = -float('inf')
for i in range(n):
    now = i
    cnt = 0
    c_sum = [0]
    s = set()
    while cnt < k:
        s.add(now)
        c_sum.append(c_sum[-1] + c[now])
        now = p[now]
        cnt += 1
        if now in s:
            break
    if k <= cnt:
        ans = max(ans, max(c_sum[1: min(k + 1, len(c_sum))]))
    else:
        temp = c_sum[-1]
        q = k // cnt
        temp *= q
        q = k - q*cnt
        temp += max(c_sum[1:min(q + 1, len(c_sum))])
        ans = max(ans, temp, max(c_sum[1:]))
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int, input().split())
P = list(map(int, input().split()))
P=[i-1 for i in P]
C = list(map(int, input().split()))
visited=[-1]*n
group=[]

for i in range(n):
    if visited[i]!=-1:
        continue
    visited[i]=0
    group.append([i])
    now=P[i]
    while now!=i:
        group[-1].append(now)
        visited[now]=0
        now=P[now]
dp=[[0] for i in range(n)]

from collections import defaultdict
d=defaultdict(list)
for g in group:
    for i in g:
        now=i
        point=0
        for j in range(len(g)):
            now=P[now]
            point+=C[now]
            d[i].append(point)
ans=-float('inf')

for i in range(n):
    dic=d[i]
    leng=len(dic)
    if k<=leng:
        ans=max(ans, max(dic[:k]))
    else:
        if dic[-1]<=0:
            ans=max(ans, max(dic))
        else:
            ans=max(ans,(k//leng)*dic[-1]+max(dic[:k%leng]))
            ans=max(ans,(k//leng-1)*dic[-1]+max(dic))
print(ans)

Submission status: Runtime Error

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

visited = [True for _ in range(N)]

def dfs(node,total,state,m):
    if visited[node]:
        return total,state,m
    state.append(C[node])
    nextM = max(total,total+C[node])
    total += C[node]
    visited[node] = True
    return dfs(P[node],total,state,nextM)

ans = -float('inf')

def calc(node):
    global visited,ans
    visited = [False for _ in range(N)]
    total,state,ma = dfs(P[node],0,[],-float('inf'))
    ans = max(ma,ans)
    K_ = K
    count = K // len(state)

    tmp = total * count
    for v in state[:K%len(state)]:
        tmp += v
    ans = max(ans,tmp)

    if total > 0:
        tmp = total * (count-1)
        for v in state:
            tmp += v
            ans = max(ans,tmp)






for i in range (N):
    calc(i)

print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
a=[]
s=set()
for i in range(N):
    idx=P[i]-1
    z=set()
    tl=[]
    rl=[]
    c=0
    tc=0
    while idx not in z and c<K:
        tl.append(C[idx])
        tc+=C[idx]
        rl.append(tc)
        s.add(tc)
        z.add(idx)
        idx=P[idx]-1
        c+=1
    d,m=divmod(K,c)
    tc=d*tc
    tc+=max(rl[:m])
    s.add(tc)
print(max(s))

Submission status: Runtime Error

Solution code:
import math
n,k = map(int,input().split())
plist= list(map(int,input().split()))
clist= list(map(int,input().split()))

n_max = [[] for _ in range(n)]

for i in range(n):
    start = plist[i]-1
    score = 0
    used = set()
    for j in range(n):
        if start in used:
            break
        score += clist[start]
        used.add(start)
        start = plist[start]-1
        n_max[i].append(score)

max_score = -math.inf
for i in range(n):
    i_score = n_max[i]
    if k < n:
        score = max(i_score[0:k])
    elif k >= n and i_score[-1] > 0:
        score = (k//len(i_score))*i_score[-1]+max(i_score[0:(k-(k//len(i_score)*len(i_score)))])
    else:
        score = max(i_score[0:k])
    max_score = max(score,max_score)

print(max_score)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
for i in range(0,N):
  y = 0
  x = i
  for j in range(0,K):
    
    x = P[x]
    m = P[x]
    y = y+C[m]
    z = max(0,y)
  w = max(0,z)
print(w)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
N, K = map(int, input().split())
Ps = list(map(int, input().split()))
Cs = list(map(int, input().split()))
scores = list()
max_list = list()
for i in range(N):
    next = Ps[i] - 1
    scores = [Cs[next]]
    while next != i:
        next = Ps[next] - 1
        scores.append(Cs[next]+scores[-1])
    l = len(scores)
    if scores[-1] < 0 or l >= K:
        max_list.append(max(scores[:K]))
    else:
        a, b = divmod(K, l)
        max_list.append(a*scores[-1] + max(scores[:b]))
    #print(scores)
print(max(max_list))

Submission status: Runtime Error

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

def score(i):
    log = [-1 for i in range(N)]
    log_score = []
    now = i
    count = 0
    while log[now] == -1:
        log[now] = count
        count += 1
        now = P[now]-1
        log_score.append(C[now])
    n = len(log_score)
    score = [sum(log_score[:i+1]) for i in range(n)]
    if log[now] == 0:
        lag = 0
        lag_score = 0
        roop_score = [sum(log_score[:i+1]) for i in range(n)]
        roop = len(roop_score)
    else:
        lag = log[now]
        lag_score = sum(log_score[:lag])
        roop_score = [sum(log_score[lag:i+1]) for i in range(lag,n)]   
        roop = len(roop_score)
    if K <= n:
        ans = max(score)
    else:
        num_roop = (K - lag)//roop
        amari = (K - lag)%roop
        ans = max(num_roop*roop_score[-1] + max(roop_score[:amari]) + lag_score,max(score))
    return ans
print(max([score(i) for i in range(N)]))

Submission status: Runtime Error

Solution code:
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):
  vis=set()
  now=i
  a=[0]
  m=k
  while m:
    vis.add(now)
    now=p[now]
    a+=[c[now]+a[-1]]
    m-=1
    if now in vis:break
  if m==0 or a[-1]<=0:
    cnt=max(a[1:])
  else:
    cnt=k//(k-m)*a[-1]+max(a[1:k%(k-m)+1])
  ans=max(ans,cnt)
print(ans)

Submission status: Runtime Error

Solution code:
P = list(map(int, input().split()))
C = list(map(int, input().split()))
min = 0
for i in range(N):
    if C[i] >0:
        min+=1
else:
    if min == 0:
        print(max(C))

Submission status: Runtime Error

Solution code:
from sys import exit

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

if max(c) < 0:
    res = max(c)
else:
    res = 0

for i in range(n):
    score = []
    s = 0
    pos = i
    visited = [False] * n
    loop = 0
    while True:
        if visited[pos]:
            break

        visited[pos] = True
        s += c[p[pos]-1]
        score.append(s)
        pos = p[pos] - 1
        loop += 1

    if len(score) == 0:
        print(-809984039214)
        exit()

    if k < loop:
        res = max(res, max(score[:k]))
    elif score[-1] <= 0:
        res = max(res, max(score))
    else:
        res = max(res, score[-1] * (k // loop) + max(score[:k%loop]), score[-1] * (k // loop - 1) + max(score))

print(res)

Submission status: Runtime Error

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


visited = [False] * (N + 1)

def iter(i, cycle):
    global visited, P
    # print("#",i)
    if visited[i]:
        return cycle
    visited[i] = True
    return iter(P[i], cycle + [C[P[i]]])

def solve(cycle, k):
    ans = -10000000000
    for i in range(len(cycle)):
        score = 0
        for j in range(k):
            score += cycle[(i + j) % len(cycle)]
            ans = max(ans, score)
            # print(score, ans)
    # print("#", ans)
    return ans

cycles = []
for i in range(1, N + 1):
    if visited[i]:
        continue
    cycles.append(iter(i, []))

# print(cycles)

ans = -10000000000
for cycle in cycles:
    s = sum(cycle)
    l = len(cycle)
    if s < 0:
        score = solve(cycle, min(l, K))
    else:
        score = solve(cycle, min(l, K))
        score = max(score, solve(cycle, K % l) + K // l * s)
    ans = max(ans, score)

print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -1000000000
for i in range(N):
  cost = 0
  S = []
  x = P[i] - 1
  l = 1
  while 1:
    cost += C[x]
    S.append(cost)
    if x == i:
      break
    l += 1
    x = P[x] - 1
  if cost > 0:
    if K % l != 0:
      ans = max(ans, cost * (K // l) + max(S[:K % l]))
    else:
      ans = max(ans, cost * (L // l))
  else:
    ans = max(ans, max(S))
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
for i in range(0,N):
  y = 0
  x = i
  for j in range(0,K):
    
    x = P[x]
    y = y+C[x]
    z = max(0,y)
  w = max(0,z)
print(w)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
p = na()
c = na()

s = set(range(n))

ans = 0
loops = []
while s:
    loop = [0]
    a = s.pop()
    while True:
        loop.append(loop[-1]+c[p[a]-1])
        if p[a]-1 not in s:
            break
        a = p[a]-1
        s.discard(a)
    loops.append(loop[1:])

ans = -1000000000000000
for tmp in loops:
    kk = k
    if k > len(tmp): kk = len(tmp) if k%len(tmp)==0 else k%len(tmp)
    loop = [0]+tmp+[tmp[-1]+u for u in tmp]
    print(loop)
    x = -1000000000
    for i in range(1,kk+1):
        for j in range(len(tmp)+1):
            print(j,i,loop)
            x = max(x,loop[j+i]-loop[j])
    if k > len(tmp) and tmp[-1] > 0:
        x += tmp[-1]*(k//len(tmp))
    ans = max(ans,x)

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, P: "List[int]", C: "List[int]"):

    if K > N-1:
        temp_max = C[0]
        for i in range(N):
            score_i = ["er"]*N 
            h = P[i]-1
            if h == i: break
            score_i[0] = C[h]
            for j in range(1, N):
                h = P[h]-1
                score_i[j] = score_i[j-1] + C[h]
                if h == i: break

            # print(score_i)
            mod_k = K % (j+1)
            rat_k = K //(j+1)
            if score_i[j] > 0:
                t = rat_k * score_i[j] + max(0,max(score_i[:mod_k]))
                temp_max = max(t, temp_max)
            else:
                temp_max = max(max(score_i[:j+1]), temp_max)
        print(temp_max)
    
    elif K <= N:
        score = [[0]*N for i in range(N)]
        for i in range(N):
            h = i
            for j in range(1, K):
                h = P[h]-1
                score[i][j] = score[i][j-1] + C[h]
        print(max(sum(score,[])))


    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, P, C)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
Ps = list(mapint())
Cs = list(mapint())
from collections import deque

s = set()
ans = -10**18
for i in range(1, N+1):
    now = i
    if now in s:
        continue
    lis = deque()
    s.add(now)
    while 1:
        nx = Ps[now-1]
        lis.append(Cs[nx-1])
        if nx in s:
            break
        s.add(nx)
        now = nx
    length = len(lis)
    lis = -(-K//length-1)*lis
    length = len(lis)
    cnt = 0
    res = 0
    for l in range(length):
        if cnt>=K:
            while lis:
                left = lis.popleft()
                if left<=0:
                    cnt -= 1
                    res -= left
                    continue
                else:
                    lis.appendleft(left)
                    break
            if cnt==K:
                if res-lis[l-K]+lis[l]>lis[l]:
                    res = res-lis[l-K]+lis[l]
                    cnt = K
                else:
                    res = lis[l]
                    cnt += 1
            else:
                if res+lis[l]>lis[l]:
                    res = res+lis[l]
                    cnt += 1
                else:
                    res = lis[l]
                    cnt = 1
        else:
            if res+lis[l]>lis[l]:
                res = res+lis[l]
                cnt += 1
            else:
                res = lis[l]
                cnt = 1
        ans = max(ans, res)
            
print(ans)

Submission status: Runtime Error

Solution code:

// Problem:
// 			D - Moving Piece
//
//
// Contest: AtCoder - AtCoder Beginner Contest 175
// URL: https://atcoder.jp/contests/abc175/tasks/abc175_d
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

// Muallif: Azimjon Mehmonali o'g'li

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

#define F first
#define S second
#define pb push_back
#define endl "\n"

#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SORT(a) sort(ALL(a))
#define rSORT(a) sort(rALL(a))
#define REV(a) reverse(ALL(a))
#define sqr(x) ((x) * (x))

//=========================================================
int recur_depth = 0;
#ifdef DEBUG
#define xtp(x)                                                           \
	{                                                                    \
		++recur_depth;                                                   \
		auto x_ = x;                                                     \
		--recur_depth;                                                   \
		cerr << string(recur_depth, '\t') << __func__ << ":" << __LINE__ \
			 << "\t" << #x << " = " << x_ << endl;                       \
	}
#else
#define xtp(x)
#endif
template <typename Ostream, typename Cont>
typename enable_if<is_same<Ostream, ostream>::value, Ostream&>::type operator<<(
	Ostream& os, const Cont& v) {
	os << "[";
	for (auto& x : v) {
		os << x << ", ";
	}
	return os << "]";
}
template <typename Ostream, typename... Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p) {
	return os << "{" << p.first << ", " << p.second << "}";
}
//=========================================================

#define TEZ                  \
	ios::sync_with_stdio(0); \
	cin.tie(0);

const long double PI = 3.1415926535897;
const int mod = 1000000007LL;
const int INF = 1e18;

signed main() {
	TEZ;

	int n, k;
	cin >> n >> k;

	vi p(n + 1), c(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> p[i];
	for (int i = 1; i <= n; i++)
		cin >> c[i];

	int jv = -INF;
	for (int i = 1; i <= n; i++) {
		int jj = 0;
		int t = i;
		for (int j = 1; j <= k; j++) {
			jj += c[t];
			jv = max(jj, jv);
			t = p[t];
		}
	}

	cout << jv << endl;

	return 0;
}

Submission status: Runtime Error

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

if max(c) < 0:
    res = max(c)
else:
    res = 0

for i in range(n):
    score = []
    s = 0
    pos = i
    visited = [False] * n
    loop = 0
    while True:
        if visited[pos]:
            break

        visited[pos] = True
        s += c[p[pos]-1]
        score.append(s)
        pos = p[pos] - 1
        loop += 1

    if k < loop:
        res = max(res, max(score[:k]))
    elif score[-1] <= 0:
        res = max(res, max(score))
    else:
        res = max(res, score[-1] * (k // loop) + max(score[:k%loop]), score[-1] * (k // loop - 1) + max(score))

print(res)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import sys

# 標準入力を取得
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
C = list(map(int, input().split()))

# 求解処理
ans = -sys.maxsize
for i in range(N):
    pos = i
    S = []
    score = 0
    while True:
        pos = P[pos] - 1
        score += C[pos]
        S.append(score)
        if pos == i:
            break
    length = len(S)

    if K <= length:
        ans = max(ans, max(S[:K]))
    else:
        if S[-1] > 0:
            ans = max(ans, int(K / length) * S[-1] + max(S[:(K % length)]))
        else:
            ans = max(ans, max(S))

# 結果出力
print(ans)

Submission status: Runtime Error

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()))
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)
    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 K <= n:
    #     ans = max(ans, max(m_score[:K+1]))
    if sum_c <= 0:
        ans = max(max(m_score), ans)
    else:
        ans = max(sum_c * (K//n) + max(m_score[1:(K%n)+1]), ans)
print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
p = [int(i)-1 for i in input().split()]
c = list(map(int,input().split()))

def calc_score(x):
    
    score = 0
    score_max = -10**10
    score_list = [-float("inf")]*n
    cnt = 0
    visit = [0]*n
    while not visit[p[x]]:
        x = p[x]
        visit[x] = 1
        cnt += 1
        if cnt<=k:
            score += c[x]
            score_max = max(score_max, score)
            score_list[cnt-1] = score
        else:
            return score_max
            
    if score>0:
        return max(score_list[:k%cnt]) + (k//cnt) * score
    else:
        return score_max

ans = max(calc_score(i) for i in range(n))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n, k = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
c = [int(x) for x in input().split()]

ans = -float('inf')
for i in range(n):
    now = i
    cnt = 0
    c_sum = [0]
    s = set()
    while True:
        s.add(now)
        c_sum.append(c_sum[-1] + c[now])
        now = p[now]
        cnt += 1
        if now in s:
            break
    if k <= cnt:
        ans = max(ans, max(c_sum[1: min(k + 1, len(c_sum))]))
    else:
        temp = c_sum[-1]
        q = k // cnt
        temp *= q
        q = k - q*cnt
        temp += max(c_sum[1:min(q + 1, len(c_sum))])
        ans = max(ans, temp, max(c_sum[1:]))
print(ans)

Submission status: Runtime Error

Solution code:
from copy import copy
import numpy as np

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

score = 0
if K > N:
    sho = K // N
    yo = K % N
    K = yo
    if sum(C) > 0:
        score += sho * sum(C)

score_list = np.zeros((N, K), dtype='int64')
for n in range(N):
    now = copy(n)
    s = copy(score)
    for k in range(K):
        now = P[now] - 1
        s += C[now]
        score_list[n, k] = s

print(score_list.max())

Submission status: Runtime Error

Solution code:
def score(p,c,i,k):
    k-=1
    start=p[i]-1
    s=c[p[i]-1]
    m=s
    c1=1
    while(start!=i and k>0):
        s+=c[p[start]-1]
        m=max(m,s)
        k-=1
        start=p[start]-1
        c1+=1
    if(s<=0 or k==0):
        return m
    else:
        s+=(s*(k//c1))
        k%=c1
        return s+score(p,c,i,k)
n,k=(int(i) for i in input().split())
p=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
m=score(p,c,0,k)
for i in range(1,n):
    m=max(m,score(p,c,i,k))
print(m)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    P=list(map(int,sys.stdin.readline().split()))
    C=list(map(int,sys.stdin.readline().split()))

    output=-10**20

    lst=[[0]*(N+1) for _ in range(N)]
    for i in range(N):
        st=set()
        now=i
        count=0
        score=0
        if K==1:
            output=max(output,C[P[i]])
            continue

        while True:
            count+=1
            now=P[now]-1

            if now in st:
                count-=1
                break
    
            lst[i][count]=lst[i][count-1]+C[now]
            st.add(now)
            
            if count==K:
                break
        
        if lst[i][count]>0 and K>=count:
            if K%count:
                s=lst[i][count]*(K//count)+max(lst[i][1:K%count+1])
            else:
                s=lst[i][count]*(K//count)
        else:
            s=max(lst[i][1:count+1])
        output=max(output,s)

    print(output)

main()

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = map(int, input().split())
P = np.array([*map(int, input().split())], dtype=int) - 1
C = np.array([*map(int, input().split())])

V = np.zeros(N)
V_max = np.zeros(K)
for i in range(K):
  V = C + V[P]
  V_max[i] = V.max()
print(int(V_max.max()))

Submission status: Runtime Error

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    P=list(map(int,sys.stdin.readline().split()))
    C=list(map(int,sys.stdin.readline().split()))

    output=-10**20

    lst=[[0]*(N+1) for _ in range(N)]
    for i in range(N):
        st=set()
        now=i
        count=0
        score=0
        if K==1:
            output=max(output,C[P[i]])
        else:
            while True:
                count+=1
                now=P[now]-1

                if now in st:
                    count-=1
                    break
        
                lst[i][count]=lst[i][count-1]+C[now]
                st.add(now)
                
                if count==K:
                    break
            
            if lst[i][count]>0 and K>=count:
                if K%count:
                    s=lst[i][count]*(K//count)+max(lst[i][1:K%count+1])
                else:
                    s=lst[i][count]*(K//count)
            else:
                s=max(lst[i][1:count+1])
            output=max(output,s)

    print(lst)
    print(output)

main()

Submission status: Runtime Error

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

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

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

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

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

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

  return ans

# main()
print(main())