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:
n, k = map(int, input().split())
a = list(map(int, input().split()))

t = [1]
for i in range(n):
    t.append(a[t[-1] -  1])

for i in range(n):
    for j in range(i + 1, n):
        if t[i] == t[j]:
            s = j - i
            break
    else:
        continue

    break

if k < i:
    print(t[k])
else:
    print(t[(k - i) % s + i])

Submission status: Time Limit Exceeded

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

loop_li = []
a = 1 

while a not in loop_li:
    loop_li.append(a)
    a = a_li[a-1]

length = len(loop_li)
if k<length:
    print(loop_li[k])
else:
    bp = a_li[loop_li[-1]-1] # back point
    bp_idx = loop_li.index(bp)
    t = length - bp_idx
    amari = (k-bp_idx)%t
    print(loop_li[bp_idx+amari])

Submission status: Time Limit Exceeded

Solution code:
import array
n, k = map(int, input().split())
tel = array.array('i', list(map(int, input().split())))
log = array.array('i', [1])
end = True
while(end):
    log.append(tel[log[-1] - 1])
    for i in range(len(log) - 1):
        if(log[i] == log[-1]):
            star = i
            mod = len(log) - star - 1
            end = False
if(k < len(log)):
    print(log[k])
else:
    print(log[(k - star) % mod + star])

Submission status: Time Limit Exceeded

Solution code:
import array
n, k = map(int, input().split())
tel = list(map(int, input().split()))
log = array.array('l', [1])
end = True
while(end):
    log.append(tel[log[-1] - 1])
    for i in range(len(log) - 1):
        if(log[i] == log[-1]):
            star = i
            mod = len(log) - star - 1
            end = False
if(k < len(log)):
    print(log[k])
else:
    print(log[(k - star) % mod + star])

Submission status: Time Limit Exceeded

Solution code:
n,k = (int(x) for x in input().split())
a =tuple([int(x) for x in input().split()])
 
l = [1]
now = 1
notloop = 0
dupl = -1

for i in range(k):
  now = a[now - 1]
  
  if now in l:
    dupl = now
    break
  else:
    l.append(now)
    
if(dupl == -1):
  print(now)
else:
  notloop = l.index(dupl)
  length = len(l)-notloop
  print(l[(k-notloop)%length+notloop])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
tel = list(map(int, input().split()))
log = [1]
end = True
while(end):
    log.append(tel[log[-1] - 1])
    for i in range(len(log) - 1):
        if(log[i] == log[-1]):
            star = i
            mod = len(log) - star - 1
            end = False
if(k < len(log)):
    print(log[k])
else:
    print(log[(k - star) % mod + star])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int,input().split()))
T = 1
cnt = 0
for k in range(K):
    T = A[T-1]
    cnt += 1
    if T == 1:
        break
if k == K-1:
    print(T)
else:
    for k in range(K%cnt):
        T = A[T-1]
    print(T)

Submission status: Time Limit Exceeded

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

b = [1]
x = 0
y = a[0]
for _ in range(n+1):
    b.append(y)
    x = y
    y = a[x-1]

#print(b)

for i in range(n):
    if b.count(b[i]) < 2:
        continue
    f_ind = b.index(b[i])
    l_ind = b[f_ind+1:].index(b[i])+f_ind

#print('f_ind = {0}'.format(f_ind))
#print('l_ind = {0}'.format(l_ind))

d = l_ind-f_ind+1
r = 0
ans = -1
if f_ind == 0:
    ans = b[k%d+r]
elif k > l_ind:
    r = (k-f_ind)%d
    ans = b[f_ind+r]
else:
    ans = b[k]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
f_ind = -1
l_ind = -1
flag = False

b = [1]

x = 0
y = a[0]
for _ in range(n+1):
    b.append(y)
    x = y
    y = a[x-1]



for i in range(n):
    if flag:
        break
    for j in range(i+1, n):
        if i > len(a) or j-i > len(a):
            break
        if b[i] == b[j]:
            f_ind = i
            l_ind = j-1
            flag = True
            break

d = l_ind-f_ind+1
r = 0
ans = -1
if f_ind == 0:
    ans = b[k%d+r]
elif k > l_ind:
    r = (k-f_ind)%d
    ans = b[f_ind+r]
else:
    ans = b[k]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
visit=[1]
pos=0
while True:
    visit.append(a[pos])
    pos=a[pos]-1
    if a[pos] in visit:
        break
loop=[]
looppos=visit[-1]-1
while True:
    loop.append(a[looppos])
    looppos=a[looppos]-1
    if a[looppos] in loop:
        break
if len(visit)>k:
    print(visit[k])
else:
    t=(k-len(visit)+len(loop))%len(loop)
    print(loop[t])

Submission status: Time Limit Exceeded

Solution code:
import math
N, K = map(int, input().split())
S = list(map(int, input().split()))
d = [[0]*(N+1) for _ in range(math.ceil(math.log2(K)))]

for i in range(N):
    d[0][i+1] = S[i]

for i in range(1, math.ceil(math.log2(K))):
    for j in range(1, N+1):
        d[i][j] = d[i-1][d[i-1][j]]

ans = 1
for i in range(math.ceil(math.log2(K))):
    if (K >> i)&1:
        ans = d[i][ans]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k=map(int,input().split())
twon=np.zeros(n)
twon=list(map(int,input().split()))
data=twon[0]
array=[-1]*n
count=0
for i in range(1,k):
    if array[data-1]==-1:
        array[data-1]=i
    else:
        cnout=(k-i)%(i-array[data-1])
        i=k-count
    data=twon[data-1]
for j in range(count):
    data=twon[data-1]
print(data)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
to = [[0] * n for i in range(60)]
to[0] = list(map(int, input().split()))

# ダブリング
for i in range(n):
    to[0][i] -= 1
DOUBLING = 60
for i in range(DOUBLING-1):
    for j in range(n):
        to[i+1][j] = to[i][to[i][j]]
v = 0
for d in range(DOUBLING, -1, -1):
    l = (1 << d)
    if l <= k:
        v = to[d][v]
        k -= l

print(v + 1)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
      
A =  list(map(int, input().split()))
B = [0] * (N + 1)
 
for i in range(N):
  B[i+1] = A[i]

start = 1
d = []
first = 0
while True:
  a = B[start]
  start = a
  first += 1
  if d.count(a) == 1:
    break
  d.append(a)

'''second = 0
start_ = start
while True:
  start_ = B[start_]
  second += 1
  if start_ == start:
    break'''
second  =  len(d) - d.index(start)
#print(first, second, start, d, len(d) - d.index(start))

if K <= first:
  S = 1
else:
  K -= first
  K %= second
  S = start

for i in range(K):
  S = B[S]
print(S)

Submission status: Time Limit Exceeded

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


def get_input() -> tuple:
    """
    標準入力の取得

    Returns:\n
        tuple: 標準入力
    """
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    return N, K, A


def main(N: int, K: int, A: list) -> None:
    """
    求解処理.

    Args:\n
        N (int): 町の数
        K (int): テレポーターの使用回数
        A (list): テレポーターの転送先
    """
    # タブリング表の作成
    to = [A]
    for i in range(math.ceil(math.log2(K))):
        to_i = to[i]
        to_next = []
        for j in range(N):
            to_next.append(to_i[to_i[j]-1])

        to.append(to_next)

    # 到着する町の計算
    result = 1
    for i in range(math.ceil(math.log2(K))):
        if ((K >> i) & 1):
            result = to[i][result-1]

    # 結果出力
    print(result)


if __name__ == "__main__":
    N, K, A = get_input()
    main(N, K, A)

Submission status: Time Limit Exceeded

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


def get_input() -> tuple:
    """
    標準入力の取得

    Returns:\n
        tuple: 標準入力
    """
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    return N, K, A


def main(N: int, K: int, A: list) -> None:
    """
    求解処理.

    Args:\n
        N (int): 町の数
        K (int): テレポーターの使用回数
        A (list): テレポーターの転送先
    """
    # タブリング表の作成
    bit_num = math.ceil(math.log2(K))
    to = [A]
    for i in range(bit_num):
        to_i = to[i]
        to_next = []
        for j in range(N):
            to_next.append(to_i[to_i[j]-1])

        to.append(to_next)

    # 到着する街の計算
    result = 1
    for i in range(bit_num):
        if ((K >> i) & 1):
            result = to[i][result-1]

    # 結果出力
    print(result)


if __name__ == "__main__":
    N, K, A = get_input()
    main(N, K, A)

Submission status: Time Limit Exceeded

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

# 標準入力の取得
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

# 求解処理
to = [A]
# ダブリング表の作成
for i in range(math.ceil(math.log2(K))):
    to_i = to[i]
    to_next = []
    for j in range(N):
        to_next.append(to_i[to_i[j]-1])

    to.append(to_next)

result = 1
for i in range(math.ceil(math.log2(K))):
    if ((K >> i) & 1):
        result = to[i][result-1]


print(result)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
town = 1
record = [1]
for i in range(N):
    town = A[town-1]
    if town in record:
        break
    record.append(town)
    
newrecord = record[record.index(town):]
roop = len(newrecord)
newK = K-(len(record)-roop)
if newK>=0:
    answer = newrecord[newK%roop]
else:
    answer = record[K]

print(answer)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def get_input() -> tuple:
    """
    標準入力の取得.

    Returns:\n
        tuple -- 標準入力
    """
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    return N, K, A


def main(N: int, K: int, A: list) -> None:
    """
    求解処理.\n
    巡回路を探し出し、見つかったら巡回路分は処理を省略する.

    Args:\n
        N (int): 町の数
        K (int): テレポーターの使用回数
        A (list): テレポーターの転送先
    """
    city = 1  # 町1から出発
    cities = [city]
    remain = []
    remain_count = 0
    loop = []
    loop_count = 0
    while True:
        city = A[city-1]
        if city in cities:
            remain_count = cities.index(city)
            remain = cities[:remain_count-1]
            loop = cities[remain_count:]
            loop_count = len(loop)
            break
        else:
            cities.append(city)

    result = int()
    if K < remain_count:
        result = remain[K]
    else:
        result = loop[(K - remain_count) % loop_count]

    # 結果出力
    print(result)


if __name__ == "__main__":
    N, K, A = get_input()
    main(N, K, A)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
town = 1
record = [1]
for i in range(K):
    town = A[town-1]
    if town in record:
        break
    record.append(town)
    
newrecord = record[record.index(town):]
roop = len(newrecord)
amari = K%roop
newK = K-(len(record)-roop)
if newK>=0:
    newamari = newK%roop
    answer = newrecord[newamari]
else:
    answer = record[K]

    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
a, b = list(map(int, input().split()))
c = list(map(int, input().split()))
itta = []
mati = 1
i = 0
while True:
    if mati in itta:
        saisyo = mati
        break
    else:
        itta.append(mati)
        mati = c[mati-1]
        i += 1
risuto = []
while True:
    if mati in risuto:
        break
    else:
        risuto.append(mati)
        mati = c[mati-1]
if b <= i-1:
    print(itta[b])
else:
    print(risuto[(b-i) % len(risuto)])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
result=[1]
temp=1
i=0
while i<k:
  temp=a[temp-1]
  if temp in result:
    break
  result.append(temp)
  i=i+1
result.append(temp)
l=len(result)
temp=result.index(result[l-1])
if k<l:
  print(result[k+1])
else:
  l2=l-1-temp
  print(result[temp+(k-temp)%l2])

Submission status: Time Limit Exceeded

Solution code:
def inp():exec('global inppp\ninpmoto,inppp=input().split(),[]\nfor i in inpmoto:\n try:inppp.append(int(i))if float(i).is_integer()else inppp.append(float(i));\n except:\n  try:inppp.append(str(i))\n  except:print("error in inp")');return inppp[0]if len(inppp)==1else list(inppp)
a, b = inp()
c = inp()
if type(c) == int:
    c = [c]
itta = []
mati = 1
i = 0
while True:
    if mati in itta:
        saisyo = mati
        break
    else:
        itta.append(mati)
        mati = c[mati-1]
        i += 1
risuto = []
while True:
    if mati in risuto:
        break
    else:
        risuto.append(mati)
        mati = c[mati-1]
if b <= i-1:
    print(itta[b])
else:
    print(risuto[(b-i) % len(risuto)])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
result=[1]
temp=1
i=0
while i<k:
  temp=a[temp-1]
  if temp in result:
    break
  result.append(temp)
  i=i+1
result.append(temp)
temp=0
l=len(result)
for i in range(0,l):
  if result[l-1]==result[i]:
    temp=i
    break
if k<l:
  print(result[k+1])
else:
  l2=l-1-temp
  print(result[temp+(k-temp)%l2])

Submission status: Time Limit Exceeded

Solution code:
def inp():exec('global inppp\ninpmoto,inppp=input().split(),[]\nfor i in inpmoto:\n try:inppp.append(int(i))if float(i).is_integer()else inppp.append(float(i));\n except:\n  try:inppp.append(str(i))\n  except:print("error in inp")');return inppp[0]if len(inppp)==1else list(inppp)
a, b = inp()
c = inp()
if type(c) == int:
    c = [c]
d = []
for i in c:
    d.append(i-1)
itta = []
mati = 0
i = 0
while True:
    if mati in itta:
        saisyo = mati
        break
    else:
        itta.append(mati)
        mati = d[mati]
        i += 1
risuto = []
while True:
    if mati in risuto:
        break
    else:
        risuto.append(mati)
        mati = d[mati]
if b <= i-1:
    print(itta[b]+1)
else:
    print(risuto[(b-i)%len(risuto)]+1)

Submission status: Time Limit Exceeded

Solution code:
l = list(map(int,input().split(' ')))
N = l[0]
K = l[1]
A = list(map(int,input().split(' ')))
x = 1
for i in range(K):
    x = A[x-1]
print(x)

Submission status: Time Limit Exceeded

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

lim=60
to=[[0]*n for i in range(lim)]

for i in range(n):
  aft=a[i]
  aft-=1
  to[0][i]=aft

for i in range(lim-1):
  for j in range(n):
    to[i+1][j]=to[i][to[i][j]]

v=0
for i in range(lim,-1,-1):
#  l=2**i
  l=1<<i
  if l<=k:
    v=to[i][v]
    k-=l

print(v+1)

Submission status: Time Limit Exceeded

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

lim=60
to=[[0]*n for i in range(lim)]

for i in range(n):
  aft=a[i]
  aft-=1
  to[0][i]=aft

for i in range(lim-1):
  for j in range(n):
    to[i+1][j]=to[i][to[i][j]]

v=0
for i in range(lim,-1,-1):
  l=2**i
  if l<=k:
    v=to[i][v]
    k-=l

print(v+1)

Submission status: Time Limit Exceeded

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

n=[0]*(N+2) #i回目ワープ後にいる場所
n[0]=1
 
for i in range(1,N+1):
  if A[n[i-1]-1] in n:
    a=n.index(A[n[i-1]-1]) #ループの開始点
    le=i-a #ループする長さ
    n[i]=A[n[i-1]-1]
    break
  n[i]=A[n[i-1]-1] #i回目ワープ後にいる場所

 

if a>=K:
  print(n[K])
elif a<K:
  k_remain=(K-a)%le
 
  print(n[a:i][k_remain])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = [0] + [int(i) for i in input().split()]

route = [1]
start = 1
cnt = 0
while True:
  if cnt == K:
    print(route[-1])
    exit()
  elif A[start] in route:
    index = route.index(A[start])
    loop = len(route) - index
    break
  else:
    route.append(A[start])
    start = A[start]
    cnt += 1

K -= index
K = K % loop
print(route[index:][K])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, K = map(int, input().split())
      
A =  list(map(int, input().split()))
B = [0] * (N + 1)

for i in range(N):
  B[i+1] = A[i]

start = 1
d = deque([])
first = 0
while True:
  a = B[start]
  start = a
  first += 1
  if d.count(a) == 1:
    break
  d.append(a)

second = 0
start_ = start
while True:
  start_ = B[start_]
  second += 1
  if start_ == start:
    break

if K <= first:
  S = 1
else:
  K -= first
  K %= second
  S = start

for i in range(K):
  S = B[S]
print(S)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, K = map(int, input().split())
      
A =  list(map(int, input().split()))
B = [0] * (N + 1)

for i in range(N):
  B[i+1] = A[i]
#print(B)

start = 1
d = deque([])
first = 0
while True:
  a = B[start]
  start = a
  first += 1
  if a in d:
    break
  d.append(a)
    
#print(first, start)

second = 0
start_ = start
while True:
  start_ = B[start_]
  second += 1
  if start_ == start:
    break
#print(second)

if K <= first:
  S = 1
else:
  K -= first
  K %= second
  S = start

for i in range(K):
  S = B[S]
print(S)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math 
N, K=map(int,input().split())
A2 = np.zeros(N)
A = list(map(int,input().split()))
A = list(map(lambda x: x -1 , A))
current_town = 0



i=0
while i<K:
    current_town = A[current_town]
    if  A2[current_town] != 0:
        cycle = i - A2[current_town] 
        i = K - (K-i) % cycle
    else:
        A2[current_town] = i

print(current_town+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math 
N, K=map(int,input().split())
A2 = np.zeros(N)
A = list(map(int,input().split()))
A = list(map(lambda x: x -1 , A))
current_town = 0




for i in range(K):
    current_town = A[current_town]
    if  A2[current_town] != 0:
        cycle = i - A2[current_town] 
        i = K - (K-i) % cycle
    else:
        A2[current_town] = i

print(current_town+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math 
N, K=map(int,input().split())
A2 = np.zeros(N)
A = list(map(int,input().split()))
A = list(map(lambda x: x -1 , A))
current_town = 0

K2 = K % math.factorial(N)



for i in range(K2):
    current_town = A[current_town]
    if  A2[current_town] != 0:
        cycle = i - A2[current_town] 
        i = K2 - (K2-i) % cycle
    else:
        A2[current_town] = i

print(current_town+1)

Submission status: Time Limit Exceeded

Solution code:
import math 
N, K=map(int,input().split())
#A = np.zeros(N)
A = list(map(int,input().split()))
A = list(map(lambda x: x -1 , A))
current_town = 0

K2 = K % math.factorial(N)

for i in range(K2):
    current_town = A[current_town]

print(current_town+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math 
N, K=map(int,input().split())
A = np.zeros(N)
A = list(map(int,input().split()))
A = list(map(lambda x: x -1 , A))
current_town = 0

K2 = K % math.factorial(N)

for i in range(K2):
    current_town = A[current_town]

print(current_town+1)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
L = list(map(int,input().split()))
X = [0]*(n+1)
X[0] = 1
for i in range(n):
  if L[X[i]-1] in X:
    X[i+1] = L[X[i]-1]  
    break
  X[i+1] = L[X[i]-1]
    
def f(lst,value):
  return [i for i,x in enumerate(lst) if x == value]
for x in X:
  if X.count(x) == 2:
    a = f(X,x)
    X_ans = X[a[0]:a[1]]
    break

if k <= a[0]:
  print(X[k])
else:
  b = (k - a[0] + 1) % (a[1]-a[0])
  print(X_ans[b-1])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = [0] + [int(i) for i in input().split()]

route = [1]
start = 1
duplicate = 0
cnt = 1

while True:
  start = A[start]
  if start in route:
    route.append(start)
    duplicate = start
    break
  else:
  	route.append(start)
  
  if cnt == K:
    print(start)
    exit()
  cnt += 1
  
loop = len(route) - route.index(duplicate) - 1
bias = route.index(duplicate) 

K -= bias
K = K % loop
route = route[route.index(duplicate):-1]

print(route[K])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
*l, = map(int,input().split())
seenl = [1]
temp=1
for i in range(k):
  temp=l[temp-1]
  if temp in set(seenl):
    lenloop = len(seenl)-seenl.index(temp)
    r = (k-i-1)%lenloop
    temp = seenl[seenl.index(temp):][r]
    break
  seenl.append(temp)
print(temp)

Submission status: Time Limit Exceeded

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

visited = []
pos = 0
count = 0

while pos not in visited:
	visited.append(pos)
	pos = a[pos]-1
	count += 1
	if count >= k:
		print(pos+1)
		exit()

loop_start = visited.index(pos)
loop_length = len(visited)-loop_start
pos_t = (k-loop_start) % loop_length + loop_start
print(visited[pos_t]+1)

Submission status: Time Limit Exceeded

Solution code:
s1 = input()
s2 = input()
n, k = list(map(lambda x : int(x), s1.split(' ')))
town = list(map(lambda x : int(x), s2.split(' ')))
i = 1
for j in range(k):
  dst = town[i - 1]
  i = dst
print(i)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    n, k, *a = map(int, sys.stdin.read().split())
    a = [0] + a
    check = [0] * (n + 1)
    check[1] = 1

    i = 0
    nw = 1
    path = [1]
    while 1:
        nx = a[nw]
        i += 1
        if i == k:
            print(nx)
            break
        if check[nx]:
            j = path.index(nx)
            d = j + (k - i) % (i - j)
            print(path[d])
            break
        path = path + [nx]
        check[nx] = 1
        nw = nx


if __name__ == '__main__':
    main()

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 i in range(d+1)]
for i,aa in enumerate(a):
  dp[0][i]=aa-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:
# coding: utf-8
# Your code here!

n,k = map(int,input().split())
li = list(map(int,input().split()))
for i in range(len(li)):
    li[i] -= 1

#何回でループするかシミュレーション
p = 0
t = 0
u = [0]
for i in range(k):
    t += 1
    p = li[p]
    if p in u:
        break
    u.append(p)
#print(p) #ループの始点
#print(t) #ループするまでにかかった数
#print(len(u)-u.index(p)) #1ループの長さ
#print(u)
#print(u.index(p))

l = (k-t) % (len(u)-u.index(p))
#print(l)

for i in range(l):
    t += 1
    p = li[p]
    if i >= 1 and p == 0:
        break
print(p+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
n,k = map(int,input().split())
ls = list(map(int,input().split()))
def sub(k,s):
    return k-s
p = [1]
i = 0
a = 0
t = 0
ans1 = 0
ans2 = 0
e = 3
while i<k-1:
    if i ==0:
        a = ls[i]
        p.append(a)
        if len(p) != len(list(set(p))):
            q = [p[-1]]*(len(p))
            p.pop()
            new = list(map(sub,p,q))
            t = new.index(0)
            ans1 = len(p[:t])
            ans2 = len(p[t:])
            print(p[((k+1-ans1)%ans2)-1])
            sys.exit()
        b = ls[a-1]
        p.append(b)
        if len(p) != len(list(set(p))):
            q = [p[-1]]*(len(p))
            p.pop()
            new = list(map(sub,p,q))
            t = new.index(0)
            ans1 = len(p[:t])
            ans2 = len(p[t:])
            print(p[((k+1-ans1)%ans2)-1])
            sys.exit()
        i += 1
    else:
        a = b
        b = ls[a-1]
        p.append(b)
        e += 1
        f = len(list(set(p)))
        if e != f:
            q = [p[-1]]*(e)
            p.pop()
            new = list(map(sub,p,q))
            t = new.index(0)
            ans1 = len(p[:t])
            ans2 = e-1 - ans1
            ansl = p[t:]
            print(ansl[((k+1-ans1)%ans2)-1])
            sys.exit()
        i += 1
print(b)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = [int(i) - 1 for i in input().split()]
r = []
nx = 0
for i in range(n):
    r.append(nx)
    if k < i:
        print(r[k] + 1)
        break
    if a[nx] in r:
        m = r.index(a[nx])
        d = i - m + 1
        k = k - m
        k = k % d
        print(r[k + m] + 1)
        break  
    nx = a[nx]

Submission status: Time Limit Exceeded

Solution code:
def main():

    N_machi, K_teleport = map(int, input().split())
    to_teleport = list(map(int, input().split()))

    def find_double_town():
        visited_city = [0]
        first_twice = N_machi
        
        next_city = 0
        
        for i in range(N_machi):
            next_city = to_teleport[next_city] - 1
            visited_city.append(next_city)
            if (len(visited_city) != len(set(visited_city))):
                first_twice = i + 1
                break
        
        return (next_city, first_twice)


    index_city, second_visit = find_double_town()
    if (index_city == 0):
        first_visit = 0
    else:
        next_city = 0        
        for i in range(N_machi):
            next_city = to_teleport[next_city] - 1
            
            if (next_city == index_city):
                first_visit = i + 1
                break

    if (K_teleport >= first_visit):
        mod = (K_teleport - first_visit) % (second_visit - first_visit)
        next_city = index_city
        
    else:
        mod = K_teleport
        next_city = 0

    for i in range(mod):
        next_city = to_teleport[next_city] - 1

    ans = next_city + 1

    print(ans)
    # print(first_visit,second_visit)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    N_machi, K_teleport = map(int, input().split())
    to_teleport = list(map(int, input().split()))

    def find_double_town():
        visited_city = [0]
        first_twice = N_machi
        
        next_city = 0
        
        for i in range(N_machi):
            next_city = to_teleport[next_city] - 1
            visited_city.append(next_city)
            if (len(visited_city) != len(set(visited_city))):
                first_twice = i + 1
                break
        
        return (next_city, first_twice)


    index_city, second_visit = find_double_town()
    if (index_city == 0):
        first_visit = 0
    else:
        next_city = 0        
        for i in range(N_machi):
            next_city = to_teleport[next_city] - 1
            
            if (next_city == index_city):
                first_visit = i + 1
                break

    if (K_teleport >= first_visit):
        mod = (K_teleport - first_visit) % (second_visit - first_visit)
        next_city = index_city
        
    else:
        mod = K_teleport
        next_city = 0

    for i in range(mod):
        next_city = to_teleport[next_city] - 1

    ans = next_city + 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
doubleA = {}
doubleA[1] = A
now = 1
 
for i in range(len(bin(k))-2):
    if (k>>i)&1:
        now = doubleA[i+1][now-1]
    doubleA[i+2] = {}
    for j in range(n):
        doubleA[i+2][j] = doubleA[i+1][doubleA[i+1][j]-1]
print(now)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    db = [a]
    cnt = k.bit_length()
    for c in range(1, cnt):
        temp = []
        for i in range(n):
            temp.append(db[c-1][db[c-1][i]-1])
        db.append(temp)

    res = 1
    for i in range(cnt):
        if (k>>i) & 1:
            res = db[i][res-1]
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
doubleA = {}
doubleA[1] = A
for i in range(2, 73):
    doubleA[i] = {}
    for j in range(n):
        doubleA[i][j] = doubleA[i-1][doubleA[i-1][j]-1]
now = 1 
for i in range(len(bin(k))-2):
    if (k>>i)&1:
        now = doubleA[i+1][now-1]
print(now)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    db = [a]
    cnt = 1
    while 2**cnt <= k:
        temp = [0]*n
        for i in range(n):
            temp[i] = db[cnt-1][db[cnt-1][i]-1]
        db.append(temp)
        cnt += 1

    res = 1
    for i in range(cnt):
        if (k>>i) & 1:
            res = db[i][res-1]
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

counter = 0
place_list = []
next = 1
while True:
    
    if  next in place_list:
        break
        
    else:
        place_list.append(next)
        next = A[next-1]
        
    counter += 1

duration_cycle = len(place_list)- place_list.index(next)
if K <len(place_list):
    print(place_list[K])
else:
    print(place_list[(K-place_list.index(next))%duration_cycle+place_list.index(next)])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
T=str(bin(K))
S=len(T)-2
A = list(map(int,input().split()))
lst=[[0 for e in range(N+1)] for f in range(S)]
for i in range(1,N+1):
 lst[0][i]=A[i-1]
for j in range(1,S):
 for i in range(1,N+1):
  lst[j][i]=lst[j-1][lst[j-1][i]]
ans=1
for k in range(S):
 if int(T[k+2])==1:
  ans=lst[S-1-k][ans]
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def check(n,seq):
    for i in range(len(seq)):
        if n == seq[i]:
            return True
    return False

if __name__ == '__main__':
    nk = input()
    nk = nk.split()
    n = int(nk[0])
    k = int(nk[1])

    A_N = input()
    A_N = A_N.split()
    a_n = list(map(int,A_N))

    now = 1
    nows = [0]*(n+1)
    nows[0] = now
    nows[n] = now
    for i in range(n+1):
        now = a_n[now-1]
        if check(now,nows):
            target = now
            target_loc = i
            break
        nows[i+1] = now

    start = nows.index(target)
    end = target_loc+1
    new_now = nows[start:end]
    if k >= start:
        k -= start
        m = len(new_now)
        print(new_now[k%m])
    else:
        print(nows[k])