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 numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit


@njit
def make_my_route(route,A,N):
    pre = 1
    for i in range(N):
        now = A[pre-1]
        temp = np.sum(route == now)
        if temp == 1:
            break
        route = np.append(route,now)
        pre = now
    return (route,now)


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

    route = np.array([1])

    route,now = make_my_route(route,A,N)
    start = int(np.where(route == now)[0])

    if K < start:
        res = route[K]
    elif start+1 != N:
        K -= start
        loop = route[start:]
        # print(loop,K)
        M = len(loop)
        K %= M
        res = loop[K]
    else:
        res = route[K]

    print(res)



main()

Submission status: Time Limit Exceeded

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

List = list(map(int, input().split()))
List2 = [1]

i = 0
while i < n:
  go = List[List2[i]-1]
  List2.append(go)
  if List2.count(go) == 2:
    loop_s = List2.index(go)
    loop_e = len(List2)-1
    break
  i += 1

t = loop_e - loop_s
if k < loop_s:
  print(List2[k])
else:
  k -= loop_s
  print(List2[loop_s + k % t])

Submission status: Time Limit Exceeded

Solution code:
import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
N, K = map(int, sys.stdin.readline().split())
A = inpl()
dic = {}
for i in range(N):
    dic[i+1] = A[i]
i = 1
visit = []
visit_set = set()
while i not in visit:
    visit.append(i)
    i = dic[i]
find = visit.index(i)
if K < find:
    print(visit[K])
else:
    root = visit[find:]
    length = len(root)
    K = (K-find) % length
    print(root[K])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 標準入力の取得
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

# 求解処理
city = 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)

Submission status: Time Limit Exceeded

Solution code:
D = 60

N, K = map(int, input().split())
to = [[None] * N for _ in range(D)]
to[0] = list(map(lambda x: int(x)-1, input().split()))

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 range(D, -1, -1):
    hops = 1 << i
    if K >= hops:
        K -= hops
        v = to[i][v]

print(v+1)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
for i in range(n):
  arr[i]-=1
flag=format(k,'b')
flag=flag[::-1]
pos=0
for i in range(len(flag)):
  if flag[i]=='1':
    pos=arr[pos]
  tmp=[]
  for j in range(n):
    tmp.append(arr[arr[j]])
  arr=tmp
print(pos+1)

Submission status: Time Limit Exceeded

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

# ループする数を求める
loop_num = 2 * 10 ** 5
loop_start_index = 0
point = 1
route_list = [1]

for i in range(K):
    point = Alist[point - 1]
    if point in route_list:
        loop_start_index = route_list.index(point)
        loop_num = i + 1 - loop_start_index
        break

    route_list.append(point)

print(route_list[loop_start_index  + ((K-loop_start_index) % loop_num)])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

city = 1
past = [1]

for i in range(K):
    city = A[city-1]
    if Counter(past).get(city):
        loopNumber = len(past) - past.index(city)#ループ１周の移動回数
        loopStart = past.index(city)
        loopAray = past[loopStart:]
        print(loopAray[(K - loopStart)%loopNumber])
        quit()
    else:
        past.append(city)
        continue

print(past[K])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a - 1 for a in A]
D = 60
MAX_N = 200005
to = [[0] * MAX_N for _ in range(D)]
for i, a in enumerate(A):
    to[0][i] = a

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 range(D - 1, -1, -1):
    l = 1 << i
    if l <= K:
        v = to[i][v]
        K -= l
print(v + 1)

Submission status: Time Limit Exceeded

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, k = input_to_int_map()
    a = {i + 1: int(val) for i, val in enumerate(input().split())}

    place = 1
    visit = {place}
    place_visits = [place]
    for i in range(k):
        place = a[place]
        if place in place_visits:
            left = place_visits.index(place)
            loop_list = place_visits[left:]
            return loop_list[(k - left) % len(loop_list)]
        else:
            visit.add(place)
            place_visits.append(place)

    return place


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

Submission status: Time Limit Exceeded

Solution code:
[N,K]=map(int,input().split())
A = list(map(int,input().split()))
t = 1
log = []
for i in range(K):
    t = A[t-1]
    if t in log:
        n = log.index(t)
        r = log[n:]
        nn = int((K-n)%len(r))
        t = r[nn-1]
        break
    log.append(t)
print(t)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,k = map(int,input().split())
a = list(map(int,input().split()))
roop_find_list = [0]
i = 0
count = 0
for _ in range(n):
    if a[i]-1 in roop_find_list:
        break
    else:
        roop_find_list.append(a[i]-1)
        i = a[i] - 1
        count += 1
b = roop_find_list.index(a[i]-1)

if k < b:
    print(roop_find_list[k]+1)
else:
    k-=b
    e = k % (count+1-b)
    print(roop_find_list[b+e]+1)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
l = [1,a[0]]
tp = a[0]-1
for i in range(n):  
  if a[tp] not in l: 
    l.append(a[tp])
    tp = a[tp] -1
  else:
    l.append(a[tp])
    break
    
last = l[-1]

loop = len(l[l.index(last):-1])
first = len(l[:l.index(last)])
if len(l)>k:
  print(l[k])
  exit()
k -=first
k %=loop
if k==0:
  k+=loop
print(l[k+first])

Submission status: Time Limit Exceeded

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

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

tele = [1,A[0]]
B = [0]
z = 0
s = 0
for i in range(N):
    if z in B and len(B) != 1:
        s = B.index(z)
        break
    tele.append(A[tele[-1]-1])
    B.append(tele[-2]-1)
    z = tele[-1]-1

if K <= s:
    print(tele[K])
else:
    K -= s
    amari = K%(len(tele[s:len(tele)-1]))
    tele = tele[s:len(tele)-1]*2
    print(tele[amari])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k, *a = map(int, open(0).read().split())
    a = [0] + a
    root = [1]
    nx = 1
    step = 0
    while True:
        step += 1
        now = nx
        nx = a[now]
        if step == k:
            print(nx)
            break
        if nx in root:
            end = step
            start = root.index(nx)
            d = end - start
            r = k - step
            index = start + r % d
            print(root[index])
            break

        root.append(nx)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
loop = []
loop.append(1)
n = A[0]
i = 0
flag = 0
while i <= K:
    i += 1
    if n in loop:
        idx = loop.index(n)
        flag = 1
        loop = loop[idx:].copy()
        break
    loop.append(n)
    n = A[n-1]
if flag == 1:
    K -= idx
r = K % len(loop)
print(loop[r])

Submission status: Time Limit Exceeded

Solution code:
n = input().split()
N = int(n[0])
K = int(n[1])

lista = []
listb = [1]
C = 1
A = list(map(int, input().split()))

for i in range(N):
    lista.append(int(A[i]))
                 
for j in range(20000000):
    C = lista[C-1]
    if C not in listb:
        listb.append(C)
    else:
        listb.append(C)
        break

L = len(listb) -1
                 
for i in range(L):
    if listb[i] == C:
        D = i

if K <= N:
    print(listb[K])
else:
    if L-D == 1 or L-D == 0:
        print(C)
    else:
        M = (K-D) % (L-D)
        print(listb[D+M])

Submission status: Time Limit Exceeded

Solution code:
N, K  = list(map(int,input().split()))
A  = list(map(int,input().split()))
table = [A]
for i in range(60):
  lst = [-1]*N
  for j in range(N):
    #print(table[-1])
    lst[j] = table[-1][table[-1][j]-1]
  table.append(lst)

b = bin(K)[2:]
now = 1
for i in range(len(b)):
  if b[len(b)-1-i] =="1":
    now = table[i][now-1]
    
#print(table)
print(now)

Submission status: Time Limit Exceeded

Solution code:
[N,K]=map(int,input().split())
A = list(map(int,input().split()))
t = 1
log = []
for i in range(K):
    t = A[t-1]
    if t in log:
        n1 = log.index(t)
        n2 = len(log)-n1
        nn = int((K-n1)%n2)
        r = log[n1:]
        t = r[nn-1]
        break
    log.append(t)
print(t)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
# 扱いやすいので1-indexedにする
A = [0] + A
# dp[2^k][i] はiから2^k回移動したときの移動先を表す
dp = {1: A}
for k in range(1, 100):
    dp[2 ** k] = [0]  # 先頭はダミー（1-indexedにするため）
    for i in range(1, N + 1):
        # jはiから2^{i - 1}回移動した先
        j = dp[2 ** (k - 1)][i]
        # iから2^k回移動した先 = jから2^{i - 1}回移動した先
        dp[2 ** k].append(dp[2 ** (k - 1)][j])
ans = 1
for k in range(100):
    if K & 2 ** k > 0:
        ans = dp[2 ** k][ans]
        K -= 2 ** k
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
B = []
b = 1
ans = 1
while ans:
  a = b
  b = A[a-1]
  B.append(b)
  if len(B) == k:
    ans = 0
B = B+B+B
print(B[k-1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = tuple(map(int, input().split()))
 
point = 1
cnt = 1
m = 0
mm = 0
ind = 0
l = [1]
for i in range(n):
    point = a[point-1]
    cnt += 1
    if point in l:
        mm = i+1
        ind = l.index(point)
        m = cnt - 1 - ind
        break
    l.append(point)
 
if k >= mm:
    print(l[(k-mm)%m+ind])
else:
    print(l[k])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
pl=1
visit=[1]
loop=0
q=True
v=True
cnt=0
br=False
while q:
    cnt+=1
    pl=a[pl-1]
    for i in visit:
        if pl==i:
            loop=visit.index(pl)
            br=not br
            break
    if br:
        break
    visit.append(pl)
    if cnt==k:
        print(pl)
        v=not v
        break
    if cnt==10**7:
        q=not q
if v:
    loop_len=cnt-loop
    q=True
    k=(k-loop)%loop_len
    cnt=0
    if k==0:
        print(pl)
    else:
        while q:
            cnt+=1
            pl=a[pl-1]
            if cnt==k:
                print(pl)
                break
            if cnt==10**7:
                q=not q

Submission status: Time Limit Exceeded

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, k = input_to_int_map()
    a = {i + 1: int(val) for i, val in enumerate(input().split())}

    place = 1
    place_goneds = [place]
    i = 0
    loop_start_index = 0
    while i < n:
        place = a[place]
        goned = False
        for j, place_goned in enumerate(place_goneds):
            if place_goned == place:
                loop_start_index = j
                goned = True
                break

        if goned:
            break

        place_goneds.append(place)
        i += 1

    if k < len(place_goneds):
        return place_goneds[k]

    move_cnt = k - loop_start_index
    loop_list = place_goneds[loop_start_index:]
    return loop_list[move_cnt % len(loop_list)]


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

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
# 循環を調べる
c=0
count=0
init_city=0
tmp_city = [0] * (n+1)

while (1):
    count+=1
#     print(c)
    tmp=a[c]
    if k==count:
        tmp_city.append(tmp)
        tmp_city=[1]+tmp_city
        break
    if tmp == 1:
        init_city=0
        tmp_city=[1]+tmp_city
        break
    if tmp in tmp_city:
        init_city=tmp_city.index(tmp)+1
        tmp_city=[1]+tmp_city
        break
    tmp_city[count-1]=tmp
    c=tmp-1
if k==count:
    print(tmp_city[-1])
else:
    print(tmp_city[init_city:count][(k-(init_city))%(count-init_city)])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
n,k = map(int,input().split())
a = list(map(int,input().split()))
roop_find = deque([0])
i = 0
count = 0
for _ in range(n):
    if a[i]-1 in roop_find:
        break
    else:
        roop_find.append(a[i]-1)
        i = a[i] - 1
        count += 1
b = roop_find.index(a[i]-1)

if k < b:
    print(roop_find[k]+1)
else:
    k-=b
    e = k % (count+1-b)
    print(roop_find[b+e]+1)

Submission status: Time Limit Exceeded

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

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

temp =1

road=[1]

while len(road) < K*2:
    temp =  A[temp-1]
    road.append(temp)

    
print(road[K])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
list = list(map(int,input().split()))
a = 1
list2=[]
begin = 0
time = 0
flag=False
flag2=False
while flag==False:
    a = list[a-1]
    for i,x in enumerate(list2):
        if i>=K:
            print(list2[i-1])
            flag=True
            flag2=True
        if x == a:
            begin=i
            time = len(list2)-begin
            flag=True
    list2.append(a)
if flag2==False:
    print(list2[begin:begin+time][(K-begin)%time-1])

Submission status: Time Limit Exceeded

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

n=[1]
t=1

while True:
  t=A[t-1]
  if t in n:
    f=n.index(t)
    break
  n.append(t)

k=len(n)-f

if K>=f:
  print(n[f+(K-f)%k])

else:
  print(n[K])

Submission status: Time Limit Exceeded

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

tele=[0]*N
for i in range(N):
    tele[i]=list[i]-1

temp=[0]*N
town=0
for i in range(N):
    temp[i]=tele[town]
    town=tele[town]

for i in range(N):
    for j in range(N):
        if temp[i]-temp[j]==0:
            m=abs(i-j)
            break
K_temp=K%m

city=0
for i in range(K_temp):
    city=tele[city]

print(city+1)

Submission status: Time Limit Exceeded

Solution code:
if __name__=="__main__":
    N, K = map(int, input().split(' '))
    _town_list = input().split(' ')
    town_list = [int(n) for n in _town_list]

    next_town = town_list[0]
    visited_town = [1]
    visited_town.append(next_town)
    counter = 1

    while True:
        counter += 1
        next_town = town_list[next_town-1]
        if counter == K:
            print(next_town)
            break
        if next_town in visited_town:
            repeated_town_idx = visited_town.index(next_town)
            loop_num = counter - repeated_town_idx
            print(visited_town[(K-repeated_town_idx)%loop_num + repeated_town_idx])
            break
        visited_town.append(next_town)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
tmp=0
tmplist=[0]
#loopしてない判定
loopinter=n
loopstart=0
for i in range(k):
    tmp=a[tmp]-1
    if tmp not in tmplist:
        tmplist.append(tmp)
    else:
        loopstart = tmplist.index(tmp)
        loopinter = len(tmplist)-tmplist.index(tmp)
        break
tmp=0
for i in range((k-loopstart)%loopinter+loopstart):
    tmp=a[tmp]-1
print(tmp+1)

Submission status: Time Limit Exceeded

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

a = [0] + list(map(int, input().split()))

step = 1
t = 0
if k<=5:
    for i in range(0, k):
        step = a[step]
    print(step)
else:

    for i in range(0, 4):
        step = a[step]

        step1 = step
    while(True):
        t += 1
        step1 = a[step1]
        if step1 == step:
            break
    result = step
    k = (k-4) % t
    for i in range(0, k):
        result = a[result]

    print(result)

Submission status: Time Limit Exceeded

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

index = 1
route = [index]
node = [index]

for i in range(1, K + 1):
    index = A[index - 1]
    if index in node:
        pre = route.index(index)
        loop = len(route)
        route_idx = (K - pre) % (loop - pre) + pre
        print(route[route_idx])
        break
    else:
        route.append(index)
        node.append(index)
else:
    print(index)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

n, k = map(int, input().split())
a = np.array(input().split(), dtype='int')
len_max = n
array1 = [1]
now_city = 1
loop = 0
flg = 0

for i in range(k):
    now_city = a[now_city - 1]
    if np.any(array1 == now_city) and i != 0:
        flg = 1
        loop_begin = np.where(array1 == now_city)[0][0]
        loop_end = i + 1
        break
    if i < len_max:
        array1.append(now_city)

if flg == 1:
    now_city = 1
    for i in range(loop_begin):
        now_city = a[now_city - 1]
    k -= loop_begin
    loop = loop_end - loop_begin
    k = k % loop
    for i in range(k):
        now_city = a[now_city - 1]

print(now_city)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
n,k = map(int,input().split())
a = list(map(int,input().split()))
roop_find = deque([0])
i = 0
count = 0
for _ in range(n):
    if a[i]-1 in roop_find:
        break
    else:
        roop_find.append(a[i]-1)
        i = a[i] - 1
        count += 1
b = roop_find.index(a[i]-1)

if k < b:
    print(list(roop_find)[k]+1)
else:
    k-=b
    e = k % (count+1-b)
    print(list(roop_find)[b+e]+1)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
now=0
l=[1]
ll=[]
for i in range(n*2):
    now=a[now]
    if now not in l:
        l.append(now)
    elif now in l and now not in ll:
        ll.append(now)
    else:
        break
    now-=1

b=len(l)
c=len(ll)
num=b-c
if k>num:
    k=(k-num)%c
    print(ll[k])
else:
    k=k%b
    print(l[k])

Submission status: Time Limit Exceeded

Solution code:
def resolve():
  N, K = map(int, input().split(" "))
  A = [int(x) - 1 for x in input().split(" ")]

  history = []
  current = 0
  if K < N:
    for i in range(K):
      current = A[current]
    print(current + 1)
    return True
  else:
    while True:
      history.append(current)
      current = A[current]
      if current in history:
        loop_length = len( history[history.index(current):] )
        if loop_length == 0:
          print(current + 1)
          return True

        length_to_loop = len( history[:history.index(current)] )
        additional_way = (K-length_to_loop)%loop_length
        print(history[length_to_loop + additional_way] + 1)
        return True

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
[N,K]=map(int,input().split())
A = list(map(int,input().split()))
t = 1
log = []
for i in range(K):
    tbk = t
    t = A[t-1]
    if t in log:
        n1 = log.index(t)
        n2 = len(log)-n1
        nn = int((K-n1)%n2)
        t = tbk
        for i in range(nn):
            t = A[t-1]
        break
    log.append(t)
print(t)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
list = list(map(int,input().split()))
a = 1
list2=[]
begin = 0
time = 0
flag=False
while flag==False:
    a = list[a-1]
    for i,x in enumerate(list2):
        if x == a:
            begin=i
            time = len(list2)-begin
            flag=True
    list2.append(a)
if K<=begin:
    print(list2[K-1])
else:
    print(list2[begin:begin+time][(K-begin)%time-1])

Submission status: Time Limit Exceeded

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

for i in range(n*2):
    road.append(now)
    now = a[now-1]

loop = [x for x in dict.fromkeys(road) if road.count(x) > 1]
ans = loop[(k-road.index(loop[0]))%len(loop)]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
d={}
l = list(map(int, input().split()))
for i in range(len(l)):
    d[i+1] = l[i]

city = 1
l2 = [1]
while True:
    city = d[city]
    if city in l2:
        break
    l2.append(city)

first = l2.index(city)
if len(l2) <= k:
    if city == l2[-1]:
        print(city)
    else:
        l2 = l2[first:]
        print(l2[(k-first)%(len(l2))])
else:
    print(l2[k])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
memo1 = [0]*(n+1)
memo2 = [0]*1000000
tmp = 0
t = 1
index = 0

for i in range(10000000):
    tmp = l[t-1]
    if memo1[t-1] != tmp:
        memo1[t-1] = tmp
        memo2[i] = tmp
        t = tmp 
    else:
        memo2[i] = tmp
        indexes = [i for i, x in enumerate(memo2) if x == memo1[t-1]]
        index = indexes[1] - indexes[0]
        exit

tmp2 = k - indexes[1]
if tmp2 <= 0:
    print(memo2[k-1])
else:
    tmp2 = tmp2%index
    if tmp2 == 0:
        print(memo1[indexes[0]])
    else:
        print(memo2[indexes[0]+tmp2-1])

Submission status: Time Limit Exceeded

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

history = []

index = 0
cnt = 0
loop_start_city_index = 0
for i in range(k+1):
    if i == k:
        print(index+1)
        exit()

    if index in history:    # すでに訪れた街にきた
        loop_start_city_index = index
        break
    history.append(index)
    index = a[index] - 1
    cnt += 1

from_start_to_loop_start = history.index(loop_start_city_index)
loop_length = len(history) - from_start_to_loop_start

print(history[from_start_to_loop_start + (k-from_start_to_loop_start)%loop_length] + 1)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
tmp = 1
route = [tmp]

for i in range(1, k + 1):
    tmp = A[tmp - 1]
    if tmp in route:
        left = route.index(tmp)
        right = len(route)
        idx = left + (k - left) % (right - left)
        print(route[idx])
        break
    else:
        route.append(tmp)
        continue
else:
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
T_list = list(map(int, input().split()))
T_list = [T_list[i]-1 for i in range(N)]
count_list = []

for s_point in range(N):
  point = s_point
  count = 0
  i = 0
  while i < N:
    point = T_list[point]
    if point == s_point:
      count = i+1
      break
    i += 1
  count_list.append(count)

point = 0
while count_list[point] == 0:
  point = T_list[point]
  count += 1

L = (K-count) % count_list[point]

i = 0
while i < L:
  point = T_list[point]
  i += 1

print(point+1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N, K = map(int, input().split())
# 文字列の入力
A = list(map(int, input().split()))
#開業されたN個要素を受け付ける
#list = [input() for i in range(N)]
#print(A)
ans=1
rireki = [1]
for i in range(K):
    if A[ans-1] in rireki:
        #print(rireki)
        #print(A[ans-1])
        n = rireki.index(A[ans-1])
        #print(n)
        l = len(rireki[n:])
        #print(l)
        #print(K-i-1)
        a=(K-i-1)%l
        ans=rireki[n:][a]
        break

    else:
        rireki.append(A[ans-1])
        ans=A[ans-1]
        #print(ans)
        #print(rireki)

print(ans)

Submission status: Time Limit Exceeded

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

rute = list()
visited = dict()
city = A[0]
i = 0
while city not in rute:
    rute.append(city)
    visited[city] = i
    city = A[city]
    i += 1

loopstart = visited[city]
rute_nonloop = rute[0:loopstart]
rute_loop = rute[loopstart:]

if K < len(rute_nonloop):
    print(rute[K-1]+1)
else:
    K -= len(rute_nonloop)
    K %= len(rute_loop)
    print(rute_loop[K-1]+1)

Submission status: Time Limit Exceeded

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

done = [1]
now = 1
for i in range(1,N+1):
    nexttown = A[now-1]
    #print(now, "->", nexttown)
    if nexttown not in done:
        done.append(nexttown)
        now = nexttown
    else:
        break

start = done.index(nexttown)
end = len(done)-1
before = start #ループに入るまでの転移数
loop = done[start:]

if K < before:
    saisyuu = done[K]
else:
    nokori = K-before
    n_loop = int(nokori/len(loop))
    hasuu = nokori%len(loop)
    loopfirst = A[done[-1]-1]
    saisyuu = loop[hasuu]
    #print("1から",before,"回転移して",loopfirst,"に到着した後、大きさ",loop,"のループを",n_loop,"回転移して",loopfirst,"にいます。")
    #print("その後、",hasuu,"回の転移をして",saisyuu,"に到着します。")
print(saisyuu)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    prev_p = 1
    g = []
    while True:
        if g[:len(g)//2]==g[len(g)//2:] and len(g) > 0:
            break
        g.append(A[prev_p-1])
        prev_p = g[-1]  

    K = K % len(g)
    print(g[K-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# ループの値を取得
work = 1
a_set = set()
loop_start_num = 0
loop_start_count = 0
for _ in range(K):
    work = A[work - 1]
    if work in a_set:
        loop_start_num = work
        break
    else:
        a_set.add(work)
        loop_start_count += 1

if K <= loop_start_count:
    print(work)
else:
    work = loop_start_num
    count = 1
    a_list = [loop_start_num]
    for _ in range(K):
        work = A[work - 1]
        if work in a_list:
            break
        else:
            a_list.append(work)
            count += 1
    print(a_list[(K - loop_start_count - 1) % count])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N, K = map(int, input().split())
# 文字列の入力
A = list(map(int, input().split()))
#開業されたN個要素を受け付ける
#list = [input() for i in range(N)]
#print(A)
ans=1
rireki = [1]
for i in range(K):
    if not A[ans-1] in rireki:
        rireki.append(A[ans-1])
        ans=A[ans-1]
        #print(ans)
        #print(rireki)
    else:
        #print(rireki)
        #print(A[ans-1])
        n = rireki.index(A[ans-1])
        #print(n)
        l = len(rireki[n:])
        #print(l)
        #print(K-i-1)
        a=(K-i-1)%l
        ans=rireki[n:][a]
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
s = list(map(int, input().split()))
N = s[0]
K = s[1]
l = list(map(int, input().split()))

count1 = 1
hd = [1]
now = 1

for i in range(N):
  now = l[now-1]
  if now in hd:
    break
  else:
    hd.append(now)
    count1 += 1

start = now
count2 = 1
for i in range(N):
  now = l[now-1]
  if now == start:
    break
  else:
    count2 += 1

answer = 1

if K <= count1:
  for i in range(K):
    answer = l[answer - 1]
else:
  answer = start
  new_k = K-count1
  reduced = new_k - ((new_k//count2)*count2)
  for i in range(reduced):
    answer = l[answer - 1]

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys

def mink(numk,l):
    x = 1
    for _ in range(k):
        x = a[x-1]
    return x

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

# kが小さい時
if k <= 10**5:
    print(mink(k,a))
    sys.exit()

# ans = 0

z = 1
p = [1]
for _ in range(k):
    z = a[z-1]
    if z in p:
        p.append(z)
        break
    p.append(z)

# 周期の来る前の回数
num = p.index(p[-1])

p = p[num:]

# 周期
pn = len(p)-1

k -= num

# 回数/周期のあまり
anum = k%pn
print(p[anum])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
i = 0
his = []
 
if K >= N:
  for j in range(N+1):
    i = A[i]-1
    his.append(i)
    K -= 1
 
    for k in range(1, j):
      if his[j] == his[j-k]:
        K = K % k
        break
      
while K > 0:
  i = A[i]-1
  K -= 1
    
print(i+1)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
def has_duplicates(seq):
    return len(seq) != len(set(seq))
load=[1]
Y=A[0]
c=0
while(has_duplicates(load)==False and c<=N):
    load.append(Y)
    Y=A[Y-1]
    c+=1
l_s=load.index(load[len(load)-1])
if(len(load)>=K+1):
    print(load[K])
else:
    x=l_s
    loop_n=K-x
    loop=load[l_s:len(load)-1]
    place=loop[loop_n%len(loop)]
    print(place)

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
 
def func1(lst, value):
    return [i for i, x in enumerate(lst) if x == value]
  
temp=1
trace=[1]
circle=[]
for i in range(K):
  temp=A[temp-1]
  ans=func1(trace,temp)
  if len(ans)==1:
    circle.append(i-ans[0]+1)
    #print(circle)
    break
  trace.append(temp)
  #print("temp",temp)
#print((K-i)%len(circle)-1)
if len(circle)!=0:
  amari=(K-i)%circle[0]
  temp=1
  for j in range(i+amari):
    temp=A[temp-1]

print(temp)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
B = []
b = 1
ans = 1
while ans:
  a = b
  b = A[a-1]
  B.append(b)
  if len(B) == k:
    ans = 0

print(B[k-1])