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: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
 
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

_, k = Is()
towns = [i-1 for i in Is()]

now = 0
seen = [0]
seenx = {0: 0}

while k > 0:
  k -= 1
  now = towns[now]
  
  if now not in seen:
    seenx[now] = len(seen)
    seen.append(now)
  else:
    seen = seen[seenx[now]:]
    break

if k == 0:
  print(1 + now)
else:
  print(1 + (seen[k % len(seen)]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
 
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

_, k = Is()
towns = [i-1 for i in Is()]

now = 0
seen = [0]
seenx = {0: 0}

while k > 0:
  k -= 1
  now = towns[now]
  
  if now not in seen:
    seen.append(now)
    seenx[now] = len(seen) - 1
  else:
    seen = seen[seenx[now]:]
    break
    
    
if k == 0:
  print(1 + now)
else:
  print(1 + (seen[k % len(seen)]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
 
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

_, k = Is()
towns = [i-1 for i in Is()]

now = 0
seen = [0]

while k > 0:
  k -= 1
  now = towns[now]
  
  if now not in seen:
    seen.append(now)
  else:
    seen = seen[seen.index(now):]
    break

if k == 0:
  print(1 + now)
else:
  print(1 + (seen[k % len(seen)]))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
data = list(map(int, input().split()))
town = [0] * N
temp = []
once = []



p = 1 #pointer
for i in range(N):
  temp.append(p-1)
  if town[p-1] == 1:
    break
  else:
    town[p-1] = 1
    p = data[p-1]
    #print(town)
    #print("pointer = {}".format(p))

#print(temp)

while True:
  if temp[0] == temp[-1]:
    break
  else:
    once.append(temp[0])
    temp.pop(0)


temp.pop(-1)
#print(once)
#print(temp)

if (K + 1) <= len(once):
  print(once[K] + 1)
else :
  K = K - len(once)
  K = K % len(temp)
  print(temp[K]+1)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int, input().split())
a=list(map(int, input().split()))
alist=[]
i=1
while a[i-1] not in alist:
  i=a[i-1]
  alist.append(i)
loop1=alist.index(a[i-1])
if k<loop1+1:
  print(alist[k-1])
else:
  lenloop=len(alist)-loop1
  print(alist[((k-loop1-1)%lenloop)+loop1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a_list = [0] + list(map(int, input().split()))
from_town = 1
history = [from_town]

while True:
  next_town = a_list[from_town]
  if next_town in history:
    break
  history.append(next_town)
  from_town = next_town

roop = history[history.index(next_town):]
left = history[:history.index(next_town)]

if k < len(left):
  print(left[k])
else:
  print(roop[(k-len(left)) % len(roop)])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 
import sys 

readline = sys.stdin.readline

N, K = map(int, readline().split())
A = list(map(int, readline().split()))

# 愚直にやると計算量O(K)でTLEになる
# 同じ街にいったら操作打ち切りで配列を完結させる

# Teleport順の配列を作る
teleport = [1]
next_town = 1
for i in range(K):
    next_town = A[next_town - 1]
    if next_town in teleport:
        dupulicate_town = next_town
        dupulicate_index = teleport.index(dupulicate_town)
        dupulicate_list = teleport[dupulicate_index:]
        break
    else:
        teleport.append(next_town)


if len(teleport) - 1 == K:
    print(teleport[-1])
else: # ループに入る場合
    consumption = len(teleport) - 1
    roop_num = K - consumption
    roop_index = roop_num % len(dupulicate_list)
    if roop_index == 0:
        print(dupulicate_list[-1])
    else:
        print(dupulicate_list[roop_index - 1])

Submission status: Time Limit Exceeded

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

genzaiti=1
imamade=deque([1])
hantei=True

while k>0:
    k-=1
    genzaiti=a[genzaiti]

    if hantei:
        for i in range(len(imamade)):
            if imamade[i]==genzaiti:
                kaiten=len(imamade)-i
                k%=kaiten
                hantei=False
                break
    
    imamade.append(genzaiti)

print(genzaiti)

Submission status: Time Limit Exceeded

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

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = [1]
    for i in range(1,K + 1):
        a = A[B[i - 1] - 1]
        if a in B:
            x = B.index(a)
            y = i - x
            z = (K - x) % y
            print(B[x + z])
            exit()
        B.append(a)
    if len(B) == K + 1:
        print(B[K])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [1]
for i in range(1,K + 1):
    a = A[B[i - 1] - 1]
    if a in B:
        x = B.index(a)
        y = i - x
        z = (K - x) % y
        print(B[x + z])
        exit()
    B.append(a)
if len(B) == K + 1:
    print(B[K])

Submission status: Time Limit Exceeded

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

i = 0
his = []
n = 0
his.append(0)
while(1):
    #print(his)
    i = a[i] - 1
    if i not in his:
        his.append(i)
    else:
        n = len(his)-his.index(i)
        break
m = len(his) - n
p = 0
if k > m:
    p = (k-m)%n + m
else:
    p = k
i = 0
#print(n,m,p)
for j in range(p):
    #print(a[i])
    i = a[i] - 1
print(i+1)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.insert(0,0)
position=[]
unit=[]
position.append(1)

for i in range(k):
  judge=a[position[-1]] in position
  if judge==0:#まだそのノードは未探索
    position.append(a[position[-1]])
    if i==k-1:
      ans=position[-1]
  else:#そのノードは探索済み
    sta=position.index(a[position[-1]])
    end=i+1
    unit=position[sta:end+1]
    if (k-sta+1)%(end-sta)==0:
      ans=unit[-1]
    else:
      ans=unit[(k-sta+1)%(end-sta)-1]
    break
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n):
    a[i] -= 1
    
visited = [0]
now = 0
flag = 0

for i in range(k):
    now = a[now]
    
    if now in set(visited):
        loop_start = now
        flag = 1
        break
        
    else:
        visited.append(now)
        
if flag == 1:
    loop = visited[visited.index(loop_start):]
    m = len(loop)
    
    now = loop[(k-(len(visited)-m))%m]
    
print(now + 1)

Submission status: Time Limit Exceeded

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

for i in range(n):
    a[i] -= 1
    
visited = [0]
now = 0
flag = 0

for i in range(k):
    now = a[now]
    
    if now in set(visited):
        loop_start = now
        flag = 1
        break
        
    else:
        visited.append(now)
        
if flag == 1:
    loop = visited[visited.index(loop_start):]
    m = len(loop)
    
    now = loop[(k-(len(visited)-m))%m]
    
print(now + 1)

Submission status: Time Limit Exceeded

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

r = []

now = 1
while True:
    r.append(now)
    now = a[now - 1] 
    if now in r:
        roop = r[r.index(now):]
        break
        
if len(r) - 1 >= k: #ループに入らないとき
    print(r[k])
else:#ループに入ったとき
    print(roop[(k-len(r)) % len(roop)])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.insert(0,0)#これでi番目の要素の位置に町iが対応する。0番目のaにはテキトーに0を入れた。
position=1
for i in range(1,k+1):
  position=a[position]
print(position)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
A = list(map(int, input().split()))
now = 1
f = 0
past = [0]*n
if n>k:
	for i in range(k):
		now = A[now-1]
	print(now)
	exit()
c = 0
for i in range(n):
	past[c] = now
	now = A[now-1]
	c+=1
	if now in past:
		f = 1
		break


loop_end = c
loop_start = past.index(now)
#print(past, now, loop_end, loop_start)
res = (k-loop_start)%(loop_end-loop_start)
now = past[loop_start]
for i in range(res):
	now = A[now-1]
print(now)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

n,k = [int(x) for x in stdin.readline().rstrip().split()]
a = [0] + [int(x) for x in stdin.readline().rstrip().split()]

m = 0
b = [1]

c = 1
for i in range(n):
    c = a[c]
    if c not in b:
        b.append(c)
        if i == k-1:
            print(c)
            sys.exit()
    else:
        break

idx = b.index(c)
bn = len(b[idx:])
sn = len(b[:idx])

# print(b,idx,sn,bn)
kk = (k-sn) % bn
print(b[idx+kk])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

n,k = [int(x) for x in stdin.readline().rstrip().split()]
a = [0] + [int(x) for x in stdin.readline().rstrip().split()]

m = 0
b = [1]

c = 1
for i in range(k):
    c = a[c]
    if c not in b:
        b.append(c)
        if i == k-1: print(c); sys.exit()
    else:
        break

idx = b.index(c)
bn = len(b[idx:])
sn = len(b[:idx])

# print(b,idx,sn,bn)
kk = (k-sn) % bn
print(b[idx+kk])

Submission status: Time Limit Exceeded

Solution code:
D=60
f=lambda:[*map(int,input().split())]
n,k=f()
l=f()
t=[[0]*n for _ in range(D)]
for i in range(n):
  t[0][i]=l[i]-1
for i in range(D-1):
  for j in range(n):
    t[i+1][j]=t[i][t[i][j]]
a=0
for i in range(D):
  if k%2: a=t[i][a]
  k//=2
print(a+1)

Submission status: Time Limit Exceeded

Solution code:
N, K=map(int, input().split())
A=list(map(int,input().split()))
S=1
E=0
n=0
number=[0]*N
number[0]=1
while all(i<2 for i in number):
  n+=1
  E=A[S-1]
  number[E-1]+=1
  S=E
number2=[0]*N
number2[E-1]=1
nn=0
S2=E
E2=0
while all(i<2 for i in number2):
  nn+=1
  E2=A[S2-1]
  S2=E2
  number2[E2-1]+=1
  
if K<=n:
  S3=1
  E3=1
  for i in range(K):
    E=A[S3-1]
    S3=E3
  print(E3)
else:
  k=(K-n)%nn
  S3=E
  E3=E
  for i in range(k):
    E3=A[S3-1]
    S3=E3
  print(E3)

Submission status: Time Limit Exceeded

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

d = 60
dp = [[-1]*N for _ in range(d+1)]
for i in range(N):
    dp[0][i] = a[i]-1

for i in range(d):
    for j in range(N):
        dp[i+1][j] = dp[i][dp[i][j]]

ans = 0

for i in range(d):
    if K & (1<<i):
        ans = dp[i][ans]

print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
def f():
    n,k=map(int,input().split())
    l=list(map(int,input().split()))
    now=1

    for i in range(k.bit_length()):
        if k and k%2:now=l[now-1]
        l=[l[l[i]-1]for i in range(n)]
        k//=2
    print(now)
if __name__ == "__main__":
    f()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 
import sys 

readline = sys.stdin.readline

N, K = map(int, readline().split())
A = readline().split()

# 愚直にやると計算量O(K)でTLEになる
# 同じ街にいったら操作打ち切りで配列を完結させる

# Teleport順の配列を作る
teleport = [1]
next_town = 1
for i in range(K):
    next_town = int(A[next_town - 1])
    if next_town in teleport:
        dupulicate_town = next_town
        dupulicate_index = teleport.index(dupulicate_town)
        dupulicate_list = teleport[dupulicate_index:]
        break
    else:
        teleport.append(next_town)


if len(teleport) - 1 == K:
    print(teleport[-1])
else: # ループに入る場合
    consumption = len(teleport) - 1
    roop_num = K - consumption
    roop_index = roop_num % len(dupulicate_list)
    if roop_index == 0:
        print(dupulicate_list[-1])
    else:
        print(dupulicate_list[roop_index - 1])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
m = [0] + list(map(int,input().split()))
p = 1

q = [1]

while True:
  p = m[p]
  if (p in q):
    break
  q.append(p)
i = q.index(p)
q1 = q[:i]
q2 = q[i:]
if len(q1) > 0 and k < len(q1):
  print(q1[k])
else: 
  print(q2[(k - len(q1)) % len(q2)])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
m = [0] + list(map(int,input().split()))
p = 1

q = [1]

while True:
  p = m[p]
  if (p in q):
    break
  q.append(p)
i = q.index(p)
if len(q[:i]) > 0 and k < len(q[:i]):
  print(q[k])
else: 
  q2 = q[i:]
  print(q2[(k - len(q[:i])) % len(q2)])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
list_a = []
list_b =[]
list_a.append(1)
count_a = 1
count_b = 0
handan = False
for i in range(1,K+1):
  if i == 1:
    k = i
  if a[k-1] in list_b:
    break
  elif a[k-1] in list_a:
    list_b.append(a[k-1])
    count_b+=1
    if a[k-1] == 1:
      handan = True
  if a[k-1] not in list_a:
    list_a.append(a[k-1])
    count_a+=1
  k = a[k-1]
#print(list_a,list_b,count_a,count_b)
if count_b != 0:
  num_k = K-(count_a-count_b)
  num_k = num_k%count_b
  if handan == True and list_b[0]!=1:
    #list_b.remove(1)
    list_b.insert(0,1)
  print(list_b[num_k])
elif count_b ==0:
  print(list_a[count_a-1])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
list_a = []
list_b =[]
list_a.append(1)
count_a = 1
count_b = 0
for i in range(1,K+1):
  if i == 1:
    k = i
  if a[k-1] in list_b:
    break
  elif a[k-1] in list_a:
    list_b.append(a[k-1])
    count_b+=1
  if a[k-1] not in list_a:
    list_a.append(a[k-1])
    count_a+=1
  k = a[k-1]
#print(list_a,list_b,count_a,count_b)
if count_b != 0:
  num_k = K-(count_a-count_b)
  num_k = num_k%count_b
  if 1 in list_b and list_b[0]!=1:
    #list_b.remove(1)
    list_b.insert(0,1)
  print(list_b[num_k])
elif count_b ==0:
  print(list_a[count_a-1])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
list_a = []
list_b =[]
list_a.append(1)
for i in range(1,K+1):
  if i == 1:
    k = i
  if a[k-1] in list_b:
    break
  elif a[k-1] in list_a:
    list_b.append(a[k-1])
  if a[k-1] not in list_a:
    list_a.append(a[k-1])
  k = a[k-1]
count_a = len(list_a) 
count_b = len(list_b)
#print(list_a,list_b)
if count_b != 0:
  num_k = K-(count_a-count_b)
  num_k = num_k%count_b
  if 1 in list_b and list_b[0]!=1:
    #list_b.remove(1)
    list_b.insert(0,1)
  print(list_b[num_k])
elif count_b ==0:
  print(list_a[count_a-1])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
list_a = []
list_b =[]
list_a.append(1)
for i in range(1,K+1):
  if i == 1:
    k = i
  if a[k-1] in list_b:
    break
  elif a[k-1] in list_a:
    list_b.append(a[k-1])
  if a[k-1] not in list_a:
    list_a.append(a[k-1])
  k = a[k-1]
count_a = len(list_a) 
count_b = len(list_b)
#print(list_a,list_b)
if count_b != 0:
  num_k = K-(count_a-count_b)
  num_k = num_k%count_b
  if 1 in list_b:
    list_b.remove(1)
    list_b.insert(0,1)
  print(list_b[num_k])
elif count_b ==0:
  print(list_a[count_a-1])

Submission status: Time Limit Exceeded

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

root = [A[0]]

if k<= n:
    for i in range(k-1):
        root.append(A[root[-1]-1])
    print(root[-1])
    exit()
else:
    for i in range(n-1):
        next = A[root[-1]-1]
        if not next in root:
            root.append(next)
        else:
            index = root.index(next)
            f = root[:index]
            loop = root[index:]
    len_f = len(f)
    len_loop = len(loop)
    print(loop[(k-len_f)%len_loop-1])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
cc = list(map(int,input().split()))
aa = [1]
flag = True
a = 1
while flag:
  aa.append(cc[a-1])
  a = cc[a-1]
  if aa.count(a) == 2 or len(aa)==K+1:
    flag = False
if len(aa) == K+1:
  print(aa[-1])
else:
  b = aa.index(a)
  m = len(aa)-b-1
  mm = (K-b) % m
  del aa[:b]
  del aa[-1]
  print(aa[mm])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
A = list(map(int, input().split()))
now = 1
f = 0
past = [0]*n
if n>k:
	for i in range(k):
		now = A[now-1]
	print(now)
	exit()
c = 0
for i in range(n):
	past[c] = now
	now = A[now-1]
	c+=1
	if now in past:
		f = 1
		break


loop_end = c
loop_start = past.index(now)
#print(past, now, loop_end, loop_start)
res = (k-loop_start)%(loop_end-loop_start)
now = past[loop_start]
for i in range(res):
	now = A[now-1]
print(now)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = np.int32(A) - 1

nxt = np.zeros((60, N), dtype=int)
nxt[0] = A
for i in range(0, 59):
    for j in range(N):
        nxt[i + 1, j] = nxt[i, nxt[i, j]]

bits = reversed(bin(K)[2:])
pos = 0
for i, v in enumerate(bits):
    if v == '1':
        pos = nxt[i, pos]

print(pos + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N,K=list(map(int,input().split()))
A =[0]+list(map(int,input().split()))
town = 1
town_list = [1]
count = 0
while True:
    town = A[town]
    count +=1
    if count == K:
        print(town)
        exit()
    if town not in town_list:
        town_list.append(town)
    else:
        roop_town_num = town
        break
    
l_ini_index = town_list.index(roop_town_num)
len_roop = len(town_list)-l_ini_index 

if K <= l_ini_index:
    print(town_list[K])
else:
    print(town_list[((K-l_ini_index)%len_roop+l_ini_index)])

Submission status: Time Limit Exceeded

Solution code:

n,k=list(map(int,input().split()))
m=list(map(int,input().split()))
a=[]
p=1
while p not in a:
    a.append(p)
    p=m[p-1]

l=a.index(p)

if k<len(a):
    print(a[k])
else:
    k-=l
    print(a[l+k%(len(a)-l)])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [[0]*N for _ in range(60)]

for i in range(N):
    dp[0][i] = A[i] - 1

for k in range(1, 60):
    for n in range(N):
        dp[k][n] = dp[k - 1][dp[k - 1][n]]

res = []
for i in range(60):
    if (K>>i)&1:
        res.append(i)
    
pos = 0
for i in res:
    pos = dp[i][pos]
print(pos + 1)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(i) for i in input().rstrip().split(' ')]
W = [int(i) - 1 for i in input().rstrip().split(' ')]
R = [0]
now = 0
s = 0
r = 0
for i in range(N):
    now = W[now]
    if now in R:
        s = R.index(now)
        r = len(R) - s
        break
    R += [now]
#print(R)
#print(s,r,(K-s)%r)
if K < s:
    print(R[K]+1)
else:
    print(R[s+(K-s)%r]+1)

Submission status: Time Limit Exceeded

Solution code:
#####################################################################################################
##### 深さ優先探索 幅優先探索　（グラフ）
#####################################################################################################

'''

キューに頂点を入れる回数は各々高々１回のみ。
各辺を使う回数は高々一回のみ（辺を戻るような探索は枝切りされている）
結果として、計算量はO(N + M)

'''

from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline



def bfs(conj, start, goal=None, visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set = deque([(start, 0)])              # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        for q in conj[p]:                       # 頂点 p から進める経路の候補から一つ選ぶ
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1


def connection_counter(conj):                   # conj の連結成分の個数を返す。関数 bfs が必要
    cnt = 0
    visit = set()
    for start in range(N):
            if start not in visit:
                cnt += 1
                bfs(start, conj, visit)
    return cnt


def distance_list(conj, start, visit=set()):    # スタート地点からの距離の全列挙
    dist = [0]*N
    visit.add(start)
    next_set = deque([(start, 0)])
    while next_set:
        p, t = next_set.popleft()
        for q in conj[p]:
            if q in visit:
                continue
            dist[q] = t+1
            visit.add(q)
            next_set.append((q, t + 1))
    return dist


def dfs(conj, start, goal=None, visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set = [(start, 0)]                     # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.pop()                   # 要素を消去して、消去した要素を出力
        for q in conj[p]:                       # 頂点 p から進める経路の候補から一つ選ぶ
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられるる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1

#############################################################
# キャッシュにメモしながら動的計画法を行う場合など、
# 帰りがけ時に子ノードたちの結果をまとめるような処理が重要な場合には、
# 再帰関数を用いた DFS が簡明 (メモ化再帰)。
#############################################################


def dfs2(conj, p=0, goal=None, t=0, past_p=None, visit=set(), second_visit=set()):
    # global res
    visit.add(p)
    for q in conj[p]:
        if q == past_p:
            # 逆流した際の処理
            continue
        if q in second_visit:
            # 帰り道に訪れた際の処理
            continue
        if q in visit:
            continue
        if q == goal:
            # ゴール時の処理
            # return t+1
            continue
        # p から q への引継ぎ処理
        # res[q] += res[p]
        dfs2(conj, q, goal, t+1, p, visit, second_visit)
    second_visit.add(p)
    # 帰り際の処置（壊した道を元に戻す等)
    # visit.discard(p)
    return # res


def cycle_detector(conj, p=0, t=0, past_p=None, path=[], visit=set(), second_visit=set(), cycle=[]):
    visit.add(p)
    path.append(p)
    for q in sorted(conj[p]):
        if q == past_p:
            continue
        if q in second_visit:
            continue
        if q in visit:
            if not cycle:
                while path:
                    r = path.pop()
                    cycle.append(r)
                    if r == q:
                        break
            continue
        cycle_detector(conj, q, t+1, p, path, visit, second_visit,cycle)
    second_visit.add(p)
    return cycle


def tree_counter(conj, detail=False):           # 木（閉路を含まない）の個数を返す。detail = True で、閉路のリストを返す
    connection_number = 0
    cycle_list = []
    visit = set()
    second_visit = set()
    for start in range(N):
        if start not in visit:
            connection_number += 1
            cycle = cycle_detector(conj, start, visit=visit, second_visit=second_visit, cycle=[])
            if cycle:
                cycle_list.append(cycle)
    if not detail:
        return connection_number - len(cycle_list)
    else:
        return cycle_list


def path_detector(conj, p=0, t=0, past_p=None, full_path=[], visit=set(), second_visit=set(), decrement=False):   # 距離と探索経路を返す。デクリメントされている場合は、decrement=True にする
    visit.add(p)
    full_path.append((p + decrement,t))
    for q in sorted(conj[p]):
        if q == past_p:
            continue
        if q in second_visit:
            continue
        if q in visit:
            continue
        path_detector(conj, q, t+1, p, full_path, visit, second_visit, decrement)
    second_visit.add(p)
    full_path.append((p + decrement,t))
    return full_path

##################################################################


N, K = map(int, input().split())

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


M = N
conj = [set() for _ in range(N)]
for i in range(M):
    u = i
    v = A[i] - 1
    conj[u].add(v)

p = 0
cnt = 0
if K <= N:
    while cnt + 1 <= K:
        p = A[p] - 1
        cnt += 1
    res = p + 1
else:
    cycle = list(
        reversed(cycle_detector(conj, p=0, t=0, past_p=None, path=[], visit=set(), second_visit=set(), cycle=[])))
    len_cycle = len(cycle)

    p = 0
    cnt = 0
    res = 0
    if not len_cycle:
        while cnt < K:
            p = A[p] - 1
            cnt += 1
        res = p + 1
    else:
        while p != cycle[0]:
            p = A[p] - 1
            cnt += 1
        k = (K - cnt) % len_cycle
        res = cycle[k] + 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
now = 1
path = [now]

for i in range(k):
    now = a[now-1]
    if now in set(path):
        now = path[path.index(now) + (k-i-1)%(len(path) - path.index(now))]
        break
    path.append(now)

print(now)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
now = 1
path = [now]

for i in range(k):
    now = a[now-1]
    if now in path:
        now = path[path.index(now) + (k-i-1)%(len(path) - path.index(now))]
        break
    path.append(now)

print(now)

Submission status: Time Limit Exceeded

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

r=[0]*n
h=i=0
while i+1 not in r:
    r[h] = i+1
    if k == h:
        print(i+1)
        sys.exit()
    i = a[i] - 1
    h += 1

del r[h:]

p = r.index(i+1)
q = len(r)-p
r_q = r[p:]


j = (k+1-p)%q
print(r_q[j-1])

Submission status: Time Limit Exceeded

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

r=[]
h=i=0
while i+1 not in r:
    r.append(i+1)
    if k == h:
        print(i+1)
        sys.exit()
    i = a[i] - 1
    h += 1



p = r.index(i+1)
q = len(r)-p
r_q = r[p:]


j = (k+1-p)%q
print(r_q[j-1])

Submission status: Time Limit Exceeded

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

r=[]
h=i=0
while i+1 not in r:
    r.append(i+1)
    if k == h:
        print(i+1)
        sys.exit()
    i = a[i] - 1
    h += 1

r.append(i+1)

p = r.index(r[len(r)-1])
q = len(r)-1-r.index(r[len(r)-1])
r_q = r[p:p+q]


if k+1<p:
    print(r[k])
else:
    j = (k+1-p)%q
    print(r_q[j-1])

Submission status: Time Limit Exceeded

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

r=[]
i=0
while i+1 not in r:
    r.append(i+1)
    i = a[i]-1
r.append(i+1)

p = r.index(r[len(r)-1])
q = len(r)-1-r.index(r[len(r)-1])
r_q = r[p:p+q]


if k+1<p:
    print(r[k])
else:
    j = (k+1-p)%q
    print(r_q[j-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def Ii():return int(sys.stdin.buffer.read())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n,k = Mi()
a = Li()
b = [1]
b.append(a[0])
flag = False
for i in range(n):
  if len(b) > k:
    print(b[k])
    exit(0)
  for j in range(len(b)):
    if b[j] == a[b[-1]-1]:
      flag = True
      break
  if flag: 
    break
    
  b.append(a[b[-1]-1])

roop = len(b)-j
roopk = (k-j)%roop
print(b[roopk+j])

Submission status: Time Limit Exceeded

Solution code:
n,k = (int(a) for a in input().split())
A = list(map(int,input().split()))
t = [1]
x = 1
while len(t) == len(set(t)) :
    t.append(A[x-1])
    x = t[-1] 
l = [i for i , x in enumerate(t) if x == t[-1]]
if k < l[0] :
    print(t[k])
else :
    k = k-l[0]
    ans = k%(l[1]-l[0])
    print(t[l[0] + ans])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
data = stdin.readlines()

n = int(data[0].split()[0])
k = int(data[0].split()[1])
a = [int(s) for s in data[1].split()]

root = []
tmp = 1

for i in range(k+1):
    root.append(tmp)
    if a[tmp-1] in root:
        break
    else:
        tmp = a[tmp-1]

if len(root) >= k:
    print(root[k])
else:
    before = root.index(a[root[-1]-1])
    dif = len(root) - before
    print(root[before  + (k-before) % dif])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
data = stdin.readlines()

n = int(data[0].split()[0])
k = int(data[0].split()[1])
a = [int(s) for s in data[1].split()]

root = []
tmp = 1

for i in range(k+1):
    root.append(tmp)
    if a[tmp-1] in root:
        break
    else:
        tmp = a[tmp-1]

if len(root) >= k:
    print(root[k])
else:
    dif = len(root) - root.index(a[root[-1]-1])
    print(root[root.index(a[root[-1]-1])  + (k-root.index(a[root[-1]-1])) % dif])