Problem:


Score: 400 points

Problem Statement

The Kingdom of Takahashi has N towns, numbered 1 through N.

There is one teleporter in each town. The teleporter in Town i (1 \leq i \leq N) sends you to Town A_i.

Takahashi, the king, loves the positive integer K. The selfish king wonders what town he will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Help the king by writing a program that answers this question.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

1 \leq K \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the integer representing the town the king will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Sample Input 1

4 5
3 2 4 1

Sample Output 1

4

If we start at Town 1 and use the teleporter 5 times, our travel will be as follows: 1 \to 3 \to 4 \to 1 \to 3 \to 4.

Sample Input 2

6 727202214173249351
6 5 2 5 3 2

Sample Output 2

2



Sample input:
4 5
3 2 4 1


Sample output:
4

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
L = [1]
def f(L):
    if A[L[-1]-1] not in L:
        L.append(A[L[-1]-1])
        return f(L)
    else:
        return L
P = f(L)
a = A[P[-1]-1]
j = P.index(a)
r = len(P)
l = r - j
print(P)
if k+1 <= j:
    print(P[k])
else:
    print(P[j+(k-j)%l])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

n,k = map(int,input().split())
a = [int(x) for x in input().split()]
li = deque()

for i in range(n):
    tmp = i + 1
    if a[i] < tmp:
        k -= i
        loop = a[i]
        break

li.append(loop)
while(True):
    li.append(a[loop-1])
    if a[loop-1] == loop:
        print(loop)
        sys.exit()
    loop = a[loop-1]
    if loop == li[0]:
        break
del li[-1]

li = list(li)
buf = len(li) - (k%len(li))
print(li[-buf])

Submission status: Runtime Error

Solution code:
# input
N, M, X = map(int, input().split())

books = []
append = books.append
max_exp = [0] * M
for i in range(N):

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

    append(
        {
            'price': CA[0],
            'get_exp': CA[1:],
            'koritsu': sum(CA[1:]) / CA[0]
        }
    )
    for ind, j in enumerate(max_exp):
        max_exp[ind] += CA[ind + 1]

books = sorted(
    books,
    key=lambda x: x['price']
)
books = sorted(
    books,
    key=lambda x: x['koritsu'],
    reverse=True
)

# check
if min(max_exp) < X:
    print(-1)
else:
    exps = [0] * M
    price = 0

    while min(exps) < X:

        price += books[0]['price']

        for ind, exp in enumerate(books[0]['get_exp']):
            exps[ind] += exp

        del books[0]
        # min_idx = exps.index(min(exps))
        # books = sorted(
        #     books,
        #     key=lambda x: x['price']
        # )
        # books = sorted(
        #     books,
        #     key=lambda x: x['get_exp'][min_idx] / x['price'],
        #     reverse=True
        # )

    print(price)

Submission status: Runtime Error

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

visited_towns = []
for i in range(N):
    next_town  = al[visited_towns[i] - 1]
    if next_town in visited_towns:
        loop_sta = visited_towns.index((next_town)) #　visited_townsにおけるループ開始のインデックス
        loop_end = len(visited_towns) #visited_townsにおけるループの終わりのインデックス
        loop_length = loop_end - loop_sta #繰り返すループの長さ
        amari = (K - loop_sta) % loop_length
        ans = visited_towns[loop_sta + amari]
        print(ans)
        exit()
    else:
        visited_towns.append(next_town)

print(visited_towns[-1])

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
#N=6
#K=727202214173249351
#A=[6,5,2,5,3,2]
iti = 1
ex_A = []

for k in range(K):
    ex_A.append(iti)
    iti = A[iti-1]
    if iti in ex_A:
        maru = len(ex_A[:ex_A.index(iti)])
        break

nokori = (K-maru) % len(ex_A[ex_A.index(iti):])

for i in range(nokori):
    iti = A[iti-1]
#print(ex_A)
print(iti)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
L = [1]
def f(L):
    if A[L[-1]-1] not in L:
        L.append(A[L[-1]-1])
        return f(L)
    else:
        return L
P = f(L)
a = A[P[-1]-1]
j = P.index(a)
r = len(P)
l = r - j
print(P)
if k < j:
    print(P[k])
else:
    print(P[j+(k-j)%l])

Submission status: Runtime Error

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


# Generated by 1.1.6 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():
    # Failed to predict input format
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    visited = [0] * (N+1)
    seq = []

    step = 0
    current = 1

    n1 = n2 = 0
    while(step<len(A)):
        #print(visited)
        seq.append(current)
        step += 1
        visited[current] = step
        next_pos = A[current-1]
        if visited[next_pos]>0:
            n1 = visited[next_pos]
            n2 = step - n1 + 1
            break
        current = next_pos

    #print(n1, n2)
    #print(n1-1, ((K-(n1-1))%n2))
    #print(seq)
    if n1+n2<=K:
        print(seq[n1-1+((K-(n1-1))%n2)])
    else:
        print(seq[K])

    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

route = [1]
for i in range(N):
    next_town = al[route[i] - 1]
    if route.count(next_town) ==1 :
        loop_start = route.index(next_town)
        loop_end = len(route)
        loop_length = loop_end - loop_start
        if K >= loop_end:
            amari = (K - loop_start) % loop_length
            ans = route[loop_start + amari]
            # print(route)
            print(ans)
            exit()
    else:
        route.append(next_town)

ans = route[-1]
print(ans)

Submission status: Runtime Error

Solution code:
'''
Fuad Ashraful Mehmet
University of Asia Pacific,Bangladesh
Date: 7th May 2020
'''


n,k=[int(x) for x in input().split()]
vis=[-1 for i in range(n+4)]
node=0
a=[int(x) for x in input().split()]
a=[0]+a
#print(a)

def dfs(u,l,turn):
    if turn<=0:
        print(u)
        return -1
    if vis[u]!=-1:
        global node
        node=u
        #print("node "+str(node))
        return l-vis[node]
    vis[u]=l
    return dfs(a[u],l+1,turn-1)

diff=dfs(1,0,k)
if diff==-1:
    exit()
else:

    lo=1
    hi=10**25
    cost=vis[node]

    while lo<=hi:
        mid=(lo+hi)//2
        temp=mid*diff
        #print(lo,hi)
        if cost+temp<=k:
            lo=mid+1
        else:
            hi=mid-1


    t=hi*diff+cost
    #print("Node "+str(node))
    def dfs2(u,turn):
        if turn<=0:
            print(u)
            return
        
        dfs2(a[u],turn-1)

    dfs2(node,k-t)

Submission status: Runtime Error

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

route = []
i = 0

while True:
    ne = a[i]

    if i not in route and len(route) <= k:
        route.append(i)
    else:
        temp = len(route) - len(route[i:])
        if k <= temp:
            print(route[k] + 1)
            # print([i+1 for i in route])
        else:
            print(a[(k-temp)%len(route[i:])])
        break

    i = ne - 1

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
iti = 1
ex_A = []

for k in range(K):
    ex_A.append(iti)
    iti = A[iti-1]
    if iti in ex_A:
        break

nokori = K % len(ex_A)

for i in range(nokori):
    iti = A[iti]

print(iti)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
li=list(map(int,input().split()))
li=[0]+li
m=1
loop={1}
s="1"
for i in range(1,n+1):
    m=li[m]
    if m in loop:
        loopend=i
        break
    loop|={m}
    s+=str(m)
if k<loopend:
    print(int(s[k]))
else:
    loopstart=s.index(str(m))
    ind=(k+1-loopstart)%(loopend-loopstart)
    t=s[loopstart:loopend]
    print(int(t[ind-1]))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
L = [1]
def f(L):
    if A[L[-1]-1] not in L:
        L.append(A[L[-1]-1])
        return f(L)
    else:
        return L
P = f(L)
a = A[P[-1]-1]
j = P.index(a)
r = len(P)
l = r - j
if k+1 <= r:
  print(P[k])
else:
  print(P[j + (k-j)%l])

Submission status: Runtime Error

Solution code:
'''
Fuad Ashraful Mehmet
University of Asia Pacific,Bangladesh
Date: 7th May 2020
'''


n,k=[int(x) for x in input().split()]
vis=[-1 for i in range(n+4)]
node=0
a=[int(x) for x in input().split()]
a=[0]+a
#print(a)

def dfs(u,l,turn):
    if turn<=0:
        print(u)
        return -1
    if vis[u]!=-1:
        global node
        node=u
        #print("node "+str(node))
        return l-vis[node]
    vis[u]=l
    return dfs(a[u],l+1,turn-1)

diff=dfs(1,0,k)
if diff==-1:
    exit()
lo=1
hi=10**25
cost=vis[node]

while lo<=hi:
    mid=(lo+hi)//2
    temp=mid*diff
    #print(lo,hi)
    if cost+temp<=k:
        lo=mid+1
    else:
        hi=mid-1


t=hi*diff+cost

#print(k-t)

def dfs2(u,turn):
    if turn<=0:
        print(u)
        return
    
    dfs2(a[u],turn-1)

dfs2(node,k-t)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
L = [1]
def f(L):
    if A[L[-1]-1] not in L:
        L.append(A[L[-1]-1])
        return f(L)
    else:
        return L
P = f(L)
a = A[P[-1]-1]
j = P.index(a)
r = len(P)
l = r - j
if k <= j-1:
  print(P[k])
else:
  print(P[j + (k-j)%l])

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

def main():
    ans = 0
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = []
    next = a[0]
    b.append(next)
    
    s = 0
    e = 0
    for i in range(n-1):
        next = a[next-1]
        if next in b:
            e = i
            s = b.index(next)
            break
        b.append(next)
    ord = b[s:]
    if k > s:
        ans = (k - s)%(e-s)
        print(ord[ans])
    else:
        print(b[k])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
'''
Fuad Ashraful Mehmet
University of Asia Pacific,Bangladesh
Date: 7th May 2020
'''


n,k=[int(x) for x in input().split()]
vis=[-1 for i in range(n+4)]
node=0
a=[int(x) for x in input().split()]
a=[0]+a
#print(a)

def dfs(u,l,turn):
    if turn<=0:
        print(u)
        return -1
    if vis[u]!=-1:
        global node
        node=u
        #print("node "+str(node))
        return l-vis[node]
    vis[u]=l
    return dfs(a[u],l+1,turn-1)

diff=dfs(1,0,k)
lo=1
hi=10**24
cost=vis[node]

while lo<=hi:
    mid=(lo+hi)//2
    temp=mid*diff
    #print(lo,hi)
    if cost+temp<=k:
        lo=mid+1
    else:
        hi=mid-1


t=hi*diff+cost

#print(k-t)

def dfs2(u,turn):
    if turn<=0:
        print(u)
        return
    
    dfs2(a[u],turn-1)

dfs2(node,k-t)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
L = [1]
def f(L):
    if A[L[-1]-1] not in L:
        L.append(A[L[-1]-1])
        return f(L)
    else:
        return L
P = f(L)
a = A[P[-1]-1]
j = P.index(a)
r = len(P)
l = r - j
if k <= j:
  print(P[k])
else:
  print(P[j + (k-j)%l])

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
li=list(map(int,input().split()))
li=[0]+li
m=1
loop={1}
s="1"
mkr=0
for i in range(1,n+1):
    m=li[m]
    if m in loop:
        loopend=i
        break
    loop|={m}
    s+=str(m)
if k<loopend:
    print(int(s[k]))
else:
    loopstart=s.index(str(m))
    ind=(k+1-loopstart)%(loopend-loopstart)
    print(int(s[loopstart:loopend][ind-1]))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
L = [1]
def f(L):
    if A[L[-1]-1] not in L:
        L.append(A[L[-1]-1])
        return f(L)
    else:
        return L
P = f(L)
a = A[P[-1]-1]
j = P.index(a)
r = len(P)
l = r - j
print(P[j + (k-j)%l])

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
li=list(map(int,input().split()))
li=[0]+li
m=1
loop={1}
s="1"
mkr=0
for i in range(1,n+1):
    m=li[m]
    if m in loop:
        loopend=i
        break
    loop|={m}
    s+=str(m)
if k<=loopend:
    print(s[k])
else:
    loopstart=s.index(str(m))
    ind=(k+1-loopstart)%(loopend-loopstart)
    print(int(s[loopstart:loopend][ind-1]))

Submission status: Runtime Error

Solution code:
N,K=[int(x) for x in input().rstrip().split()]
A=[int(x) for x in input().rstrip().split()]
stack=[]
done=[0 for i in range(N)]
done[0]=0
now=1
amari=[]
cnt=0
for i in range(10**5):
  done[now-1]+=1
  if done[now-1]==2:
    cnt+=1

  if done[now-1]==3:
    break
  
  stack.append(now)
  now=A[now-1]

ans=K%cnt
print(stack[ans])

Submission status: Runtime Error

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

route = [1]
for i in range(N):
    next_town = al[route[i]-1]
    if len(route) != len(set(route)):
        loop_start = route.index(next_town)
        loop_end = len(route)
        loop_length = loop_end - loop_start
        if K >= loop_end:
            amari = (K - loop_start)%loop_length
            ans = route[loop_start + amari]
            #print(route)
            print(ans)
            exit()
    else:
        route.append(next_town)

ans = route[-1]
print(ans)

Submission status: Runtime Error

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

Town = []
#まだ訪れていない町は-1
rec = [-1] * (n+1)
idx = 1
#すべての町を訪れるまで
while (rec[idx] == -1):
    rec[idx] = len(Town)
    Town.append(idx)
    idx = A[idx-1]

Exce = rec.index(idx)
Cycl = len(Town) - Exce

if Cycl > k:
    print(Town[k])
else:
    k -= Exce
    k %= Cycl
    print(Town[Exce+k])

Submission status: Runtime Error

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


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

ar=[-1 for i in range(n+1)]
p=1

go=0


for i in range(1,k+1):
    
    
    
    

    ar[p]=i
    p=a[p-1]
    
    if ar[p]>0:
        j=ar[p]
        amari=(k-i-1)%(i-j)
        
        go=1
        break

if go==1:
    p=ar.index(j+amari)
    p=a[p-1]
    


print(p)

Submission status: Runtime Error

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

Town = []
#まだ訪れていない町は-1
rec = [-1] * (n+1)
idx = 1
#すべての町を訪れるまで
while (rec[idx] == -1):
    rec[idx] = len(Town)
    Town.append(idx)
    idx = A[idx-1]

Exce = rec[idx]
Cycl = len(Town) - Exce

if Cycl >= k:
    print(Town[k])
else:
    print(Town[Exce+(k-Exce)%Cycl])

Submission status: Runtime Error

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


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

ar=[-1 for i in range(n+1)]
p=1
h=[]
go=0


for i in range(1,k+1):
    
    
    
    

    ar[p]=i
    p=a[p-1]
    
    if ar[p]>0:
        j=ar[p]
        amari=(k-i-1)%(i-j)
        
        go=1
        break

if go==1:
    p=ar.index(j+amari)
    p=a[p-1]


print(p)

Submission status: Runtime Error

Solution code:
import numpy as np

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

is_loop = False
diff = [0] # start
pos = 0
for _ in range(k):
    pos = a_list[pos] - 1
    if pos in diff:
        diff.append(pos)
        is_loop = True
        break
    diff.append(pos)
tmp = list(np.where(np.array(diff)==pos)[0])

t = tmp[-1] - tmp[-2] # 周期
buff = tmp[-2] # 前半のバッファ

# 周期が見える前に終わった
if not is_loop:
    print(pos+1)
else:
    print(diff[buff+(k-buff)%t]+1)

Submission status: Runtime Error

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


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

ar=[-1 for i in range(n+1)]
p=1
h=[]
go=0


for i in range(1,k+1):
    
    
    
    

    ar[p]=i
    p=a[p-1]
    
    if ar[p]>0:
        j=ar[p]
        amari=(k-i-1)%(i-j)
        p=h[j+amari]
        go=1
        break

if go==1:
    p=ar.index(j+amari)
    p=a[p-1]


print(p)

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python3
 
# from fractions import gcd
from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
 
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
 
root = [1]
index = 0
 
for i in range(K):
    if A[index] in root:
        ho = root.index(A[index])
        hoge = root[ho:]
        break
 
    root += [A[index]]
    index = A[index] - 1
 
nokori = (K-ho) % len(hoge)
 
print(hoge[nokori])

Submission status: Runtime Error

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

Town = []
#まだ訪れていない町は-1
rec = [-1] * (n+1)
idx = 1
#すべての町を訪れるまで
while rec[idx] == -1:
    rec[idx] = len(Town)
    Town.append(idx)
    idx = A[idx-1]

Exce = rec[idx]
Cycl = len(Town) - Exce

if Cycl >= k:
    print(Town[k])
else:
    k -= Exce
    k %= Cycl
    print(Town[k+Exce])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a = list(map(int, input().split()))
l = 1
m = []

for i in range(10000):
    if a[l - 1] in m: #ループが始まったかどうか
        for j in range(len(m)):
            if m[j] == a[l - 1]:
                cnt = j #ループ開始までの端数
                loop = len(m) - cnt #ループの長さ
                break
    else:
        m.append(a[l - 1])
        l = a[l - 1]
        continue
    break


if (k - cnt)%loop == 0:
    l = loop + cnt - 1
else:
    l = (k - cnt)%loop - 1 + cnt

print(m[l])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a = list(map(int, input().split()))
l = 1
m = []

for i in range(10000):
    print(i)
    if a[l - 1] in m: #ループが始まったかどうか
        for j in range(len(m)):
            if m[j] == a[l - 1]:
                cnt = j #ループ開始までの端数
                loop = len(m) - cnt #ループの長さ
                break
    else:
        m.append(a[l - 1])
        l = a[l - 1]
        continue
    break


if (k - cnt)%loop == 0:
    l = loop + cnt - 1
else:
    l = (k - cnt)%loop - 1 + cnt

print(m[l])

Submission status: Runtime Error

Solution code:

class abc_167:
    
    def __init__(self):
        pass
    
    def A(self):
        S=input()
        T=input()
        if S==T[:len(S)]:print("Yes")
        else:print("No")
    
    def B(self):
        ABCK=list(map(int,input().split()))
        sum_num=0
        
        if ABCK[3]<=ABCK[0]+ABCK[1]:sum_num=ABCK[0]
        else:sum_num=ABCK[0]-(ABCK[3]-ABCK[0]-ABCK[1])
        
        print(sum_num)
            
    def C(self):
        pass
            
    def D(self):
        
        NK=list(map(int,input().split()))
        A=list(map(int,input().split()))
        stack=[]
        A_memo=[0]*(NK[0]+1)
        flag=False
        
        
        count=0
        stack.append(A[count])
        count+=1
        A_memo[1]=count
        
        max_data = NK[0]+1 if NK[0]<=NK[1] else NK[1]
        
        while(count<max_data):
            data=stack.pop()
            stack.append(A[data-1])
            count+=1
            
            if A_memo[A[data-1]]==0:
                A_memo[A[data-1]]=count
            else:
                loop_val=A[data-1]
                flag=True
                break
            
        #a=count-A[loop_val]
        #b=NK[1]-A[loop_val]
        #print(count-A[loop_val])
        #print(NK[1]-A[loop_val])
        #print((b%a)+A[loop_val]-1)
        ans_stack=[]
        ans_stack.append(A[0])
            
        if flag==True:
            ans=((NK[1]-A[loop_val])%(count-A[loop_val]))+(A[loop_val]-1)
            for i in range(ans):
                ans_data=ans_stack.pop()
                ans_stack.append(A[ans_data-1])
            end=ans_stack.pop()
            print(end)
        else:
            ans=count
            for i in range(ans):
                ans_data=ans_stack.pop()
                ans_stack.append(A[ans_data-1])
            end=ans_stack.pop()
            print(end)
            
            
           
            
    
    def E(self):
        pass
    
    def F(self):
        pass
    
    
if __name__=='__main__':
    obj=abc_167()
    obj.D()

Submission status: Runtime Error

Solution code:
D = 60
U = 2 * 10 ** 5 + 10
to = [[0] * D for _ in range(U)]

N, K = map(int, input().split())
for i, a in enumerate(map(int, input().split())):
    to[0][i] = a - 1
# 表の構築
for i in range(D - 1):
    for j in range(N):
        to[i + 1][j] = to[i][to[i][j]]

v = 0
for i in reversed(range(D)):
    x = 1 << i
    if x <= K:
        v = to[i][v]
        K -= x

print(v + 1)

Submission status: Runtime Error

Solution code:
import sys
import os

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    N,K=map(int, input().split())
    A=list(map(int, input().split()))

    d=1
    keys=list(range(N))
    li={s:-1 for s in keys}
    li[0]=0

    pre_d=0
    i=0
    while True:
        i+=1
        pre_d=d
        d=A[d-1]
        if li[d-1]!=-1:
            break
        else:
            li[d-1]=i

    # print(pre_d)
    # print(d)
    # roop=pre_d-d
    roop=i-li[d-1]
    print(A[(K-d)%roop+d])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import os

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    N,K=map(int, input().split())
    A=list(map(int, input().split()))

    d=1
    keys=list(range(N))
    li={s:-1 for s in keys}
    li[0]=0

    pre_d=0
    i=0
    while True:
        i+=1
        pre_d=d
        d=A[d-1]
        if li[d-1]!=-1:
            break
        li[d-1]=i

    # print(pre_d)
    # print(d)
    # roop=pre_d-d
    roop=i-li[d-1]
    print(A[(K-d)%roop+d])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import os

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    N,K=map(int, input().split())
    A=list(map(int, input().split()))

    d=1
    keys=list(range(N))
    li={s:-1 for s in keys}
    li[0]=0

    pre_d=0
    while True:
        pre_d=d-1
        d=A[d-1]
        if li[d-1]==0:
            break
        li[d-1]=0

    # print(pre_d)
    # print(d)
    roop=pre_d-d+1
    print(A[(K-d)%roop+d])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    s = input()
    data = s.split(" ")
    n = int(data[0])
    k = int(data[1])

    s = input()
    data = s.split(" ")
    ts = [int(i) for i in data]

    step_set = set()
    step = []
    nt = ts[0]
    step_set.add(nt)
    step.append(nt)
    for i in range(k):
        nt = ts[nt-1]
        if nt not in step_set:
            step_set.add(nt)
            step.append(nt)
        else:
            index = step.index(nt)
            step = step[index:]
            break;

    print(step[(k-index)%len(step)-1])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    A = [int(x) for x in stdin.readline().rstrip().split()]
    if A[0] == 1:
        print(1)
        exit()       
    X=1
    Log = [1]
    for i in range(K):
      X = A[X-1]
      if (X in Log) ==True:
        break
      Log += [X]
        #print(Log)
        #print(K - Log.index(X))
        #print(i - Log.index(X)+1)
    G = Log.index(X)
    K = (K - G)%(i - G + 1)
    #print(K)
    print(Log[G+K])
main()

Submission status: Runtime Error

Solution code:
from sys import stdin
def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    A = [int(x) for x in stdin.readline().rstrip().split()]
    if A[0] == 1:
        print(1)
        exit() 
    X=1
    Log = [1]
    for i in range(K):
      X = A[X-1]
      if (X in Log) ==True:
        break
      Log += [X]
        #print(Log)
        #print(K - Log.index(X))
        #print(i - Log.index(X)+1)
    K = (K - Log.index(X))%(i - Log.index(X)+1)
    #print(K)
    print(Log[Log.index(X)+K])    
main()

Submission status: Runtime Error

Solution code:
from collections import deque

n, k = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))

loop = []
visited = set()
s = set([1])
seq_s = [1]
loop_creating = False
last = 1

while True:
  if loop_creating and len(visited) == 0:
    break

  nex = a[last - 1]

  if nex in visited:
    visited.remove(nex)
    loop.append(nex)
    loop_creating = True
  elif nex in s:
    visited.add(nex)
  else:
    s.add(nex)
    seq_s.append(nex)

  last = nex

if k <= len(s):
  print(seq_s[k])
elif k > len(s):
  rem = k - len(s)
  print(loop[rem % len(loop)])

Submission status: Runtime Error

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

loop = []
visited = set()
stack = [1]
loop_creating = False
last = 1

while True:
  if loop_creating and len(visited) == 0:
    break

  nex = a[last - 1]

  if nex in visited:
    visited.remove(nex)
    loop.append(nex)
    loop_creating = True
  elif nex in stack:
    visited.add(nex)
  else:
    stack.append(nex)

  last = nex

if k <= len(stack):
  print(stack[k])
elif k > len(stack):
  rem = k - len(stack)
  print(loop[rem % len(loop)])

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = tuple( map(int, input().split()) )

L = [0 for i in range(N+1)]
L[1] = 1
x = 1
t = 1
while K>0:
  t += 1
  K -= 1
  x = A[x]
  if L[x] != 0:
    p = t - L[x]
    K %= p
    break
  else:
    L[x] = t
    
while K>0:
  x = A[x]
  K -= 1
print(x)

Submission status: Runtime Error

Solution code:
from sys import stdin
import math


def main():
    n, k = list(map(int, input().split()))
    A = list(map(int, stdin.readline().split()))
    roots = []
    roots.append(A)
    maxLoop = math.ceil(math.log(k)/math.log(2))
    for _ in range(1, maxLoop):
        roots_tmp = [None] * n
        for j in range(n):
            roots_tmp[j] = roots[-1][roots[-1][j]-1]
        roots.append(roots_tmp)

    position = 1
    for i in range(maxLoop+1):
        if k & (1 << (maxLoop-i)):
            position = roots[-1-i][position-1]

    print(position)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections
n,k = map(int,input().split())
a = list(map(int,input().split()))
list = [1]
i = 0
num = a[0]
for i in range(3*n):
    if i == n:
        i = 0
    list.append(num)
    num = a[num-1]

cnt = collections.Counter(list)
lstart = len(cnt.most_common()[-1])
lroop = len(set(list))-lstart

if k <= lstart:
    num = a[0]
    for i in range(k-1):
        num = a[num-1]
    print(num)
    exit()
else:
    k = (k-lstart)%lroop
    num = a[0]
    for i in range(lstart-1):
        num = a[num-1]
    for i in range(k):
        num = a[num-1]
    print(num)
    exit()

Submission status: Runtime Error

Solution code:
n, k = map(int,input().split())
a = list(map(int,input().split()))
from collections import deque

ans = deque()
ans.appendleft(1)
count = 1
s = -1
zeros = [0]*n

while True:
    if zeros[a[count-1]] == 1:
        s = a[count-1]
        break
    else:
        ans.append(a[count-1])
        zeros[count-1]=1
        count = a[count-1]

ans = list(ans)
if s == -1:
    print(ans[k])
else:
    t = ans.index(s)
    if t >= k:
        print(ans[k])
    else:
        ans = ans[t:]
        print(ans[(k-t)%len(ans)])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(input().split())
p = [0]*200000
q = [0]*200000
p[0]=1
p[1]=int(a[0])
q[0]=1
q[p[1]-1]=2
f=0
for i in range(k-1):
    p[i+2]=int(a[p[i+1]-1])
    if q[p[i+2]-1]>0:
        r=q[p[i+2]-1]-1
        q=i+2-r
        f=1
        break
    if f==1:
        break
    q[p[i+2]-1]=i+3
l=k-r
l%=q
s=p[r+l]
if f==0:    
    print(p[k])
else:
    print(s)

Submission status: Runtime Error

Solution code:
6 727202214173249351
6 5 2 5 3 2
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
s = []
o = [-1] * (n + 1)  # ord 訪れた箇所, v が1スタートなので注意
c, l = 1, 0  # 周期, 例外

v = 1
while o[v] == -1:
    o[v] = len(s)
    s.append(v)
    v = a[v-1]
c = len(s) - o[v]
l = o[v]

if k < l:
    print(s[k])
else:
    k -= l
    k %= c
    print(s[l + k])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(input().split())
p = [0]*200000
q = [0]*200000
p[0]=1
p[1]=int(a[0])
q[0]=1
q[p[1]-1]=2
f=0
for i in range(k-1):
    p[i+2]=int(a[p[i+1]-1])
    if q[p[i+2]]>0:
        r=q[p[i+2]]
        q=i+2-r
        f=1
        break
    if f==1:
        break
    q[p[i+2]]=i+3
l=k-r
l%=q
s=p[r+l]
if f==0:    
    print(p[k])
else:
    print(s)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
journey = [1]
dup = {}
for i in range(N+100000):
    journey.append(A[journey[-1] - 1])

end_idx, start_idx = 0, 0
dup = {}
for i, j in enumerate(journey):
    if j in dup:
        end_idx = i
        break
    else:
        dup[j] = 0
for i, j in enumerate(journey):
    if j == journey[end_idx]:
        start_idx = i
        break
        
if K >= start_idx:
    print(journey[K])
    exit()
b = end_idx - start_idx
m = (K - start_idx) % b
print(journey[start_idx + m])

Submission status: Runtime Error

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

genzaichi=1
rireki=set()
houmon=[0]*(N+1)
flag=0

for i in range(1,K+1):
    genzaichi=A[genzaichi-1]
    if genzaichi not in rireki:
        houmon[genzaichi]=i
        rireki.append(genzaichi)
    else:
        roop_from=genzaichi
        x=houmon[roop_from]
        roop=i-x
        flag=1
        break

if flag==0:
    print(genzaichi)
else:
    genzaichi=roop_from
    K=(K-x)-((K-x)//roop)*roop
    for i in range(K):
        genzaichi=A[genzaichi-1]
    print(genzaichi)

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools

def main():
  n,k = map(int, input().split())
  a = list(map(int,sys.stdin.readline().split()))

  now = 0
  times = 0
  visit =[[0],[0]]

  for _ in range(k):
    times += 1
    now = a[now] - 1

    if now in visit[0]:
      roop = times - visit[1][visit[0].index(now)] #何個の町でループしてるかをroopに代入
      roop_start = visit[1][visit[0].index(now)] #ループが始めった待ちの最初に訪れた時に何回ループしていたかをroop_startに代入
      break
    else:
      visit[0].append(now)
      visit[1].append(times)

  if roop > 0:
    k = (k - roop_start) % roop

  # print(roop_start)
  # print(roop)
  # print(k)
  # print(visit[0])
  print(visit[0][roop_start + k] + 1)

  # now = 0
  # for _ in range(roop_start):
  #   now = a[now] - 1

  # for _ in range(k):
  #   now = a[now] -1

  # print(now+1)


if __name__ == '__main__':
  main()

Submission status: Runtime Error

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

"""
1からのループだけを考えれば良い
"""

i = A[0]
ok = True
R = [1]
seen = [0] * N
seen[0] = 1
count = 1

while ok:
    count += 1
    seen[i-1] += count
    R.append(i)
    i = A[i-1]
    # 訪れたことがあれば
    if seen[i-1] != 0:
        k = seen[i-1]
        loop = R[k-1:]
        remain = R[:k-1]
        ok = False

L = len(loop)

if K < len(remain):
    print(remain[K])
else:
    print(loop[(K - len(remain)) % L])