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 math
import itertools

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

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

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

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

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

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

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

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

  # print(now+1)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))
C=[1]
for i in range(N):
  if C.count(A[C[i]-1])==0:
    C.append(A[C[i]-1])
  else:
    l=C.index(A[C[i]-1])+1
    break
if K+1<=l:
  print(C[K])
else:
  print(C[l-1+(K+1-l)%(len(C)-l+1)])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools

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

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

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

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

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

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

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

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

  # print(now+1)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
n, k = map(int, readline().split())
A = [i - 1 for i in map(int, readline().split())]

m = 64
d = [A]
pre = A
for i in range(m):
    current = [pre[pre[j]] for j in range(n)]
    d.append(current)
    pre = current

route = 0
for i in range(m-1, -1, -1):
    if k >= (x := 1 << i):
        route = d[i][route]
        k -= x
print(route+1)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
t=[[] for j in range(64)]
l=[0 for _ in range(n)]
ll=l[:]
for i in range(64):
    for j in range(n):
        if i == 0:
            l[j]=a[j]
        else:
            l[j]=ll[ll[j]-1]
    ll=l[:]
    t[i]=l[:]
ans=1

for i in range(64):
    r = k%2
    k = k//2
    if r == 1:
        ans = t[i][ans-1]
    if k == 0:
        print(ans)
        exit()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
city_list = list(map(int, input().split()))
th_list = []
n = 0
count = 0
for i in range(N):
    count += 1
    th_list.append(n)
#   print(n)
    n = city_list[n] - 1
''' if n in th_list:
        #繰り返されている個数を出す
        num = len(th_list)-th_list.index(n)
        break'''
 
#print(city_list, th_list)
count = -1
for i in range(N):
    if th_list.count(th_list[i]) > 1:
        break
list = [x for x, l in enumerate(th_list) if l == th_list[i]]
#print(list)
#print(list[0])
#print(th_list)
if K > N:
    print(th_list[(K-list[0])%(list[1]-list[0])+list[0]]+1)
else:
    print(th_list[K]+1)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
t=list(map(int,input().split()))
g=[1]
for i in range(N):
  gs=set(g)
  if t[g[i]-1] in gs:
    h=g.index(t[g[i]-1])
    s=i+1-h
    break
  g.append(t[g[i]-1])
if K>h:
  K=(K-h)%s+h
print(g[K])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
t=[[0 for i in range(n)] for j in range(64)]
for i in range(64):
    for j in range(n):
        if i == 0:
            t[i][j]=a[j]
        else:
            t[i][j]=t[i-1][t[i-1][j]-1]
ans=1
for i in range(64):
    r = k%2
    k = k//2
    if r == 1:
        ans = t[i][ans-1]
    if k == 0:
        print(ans)
        exit()

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
t=list(map(int,input().split()))
g=[1]
for i in range(N):
  if g.count(t[g[i]-1])!=0:
    h=g.index(t[g[i]-1])
    s=i+1-h
    break
  g.append(t[g[i]-1])
if K>h:
  K=(K-h)%s+h
print(g[K])

Submission status: Time Limit Exceeded

Solution code:
#abc_167_D
#doubling 
#類題:agc_006_c

n,k = [int(i) for i in input().split()]
a   = [int(i)-1 for i in input().split()]

#do doubling
s = list(range(n))
while k>0:
    if k&1:
        s = [s[a[i]] for i in range(n)]
    a = [a[a[i]] for i in range(n)]
    k >>= 1
    
#初期値0に対するk移動後の位置は、s[0]で求まる,
print(s[0]+1)


'''
pos = 1
move= 0
colors = [-1]*(n+1)

while(colors[pos]==-1):
    colors[pos] = move
    move += 1
    pos = a[pos]
    if move==k:
        print(pos)
        break
else:
    turn = move - colors[pos]
    rest = (k-colors[pos]) % turn
    while rest:
        pos = a[pos]
        rest -= 1
    print(pos)
'''

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=[[0 for j in range(60)] for i in range(n)]
for i in range(len(a)):
    a[i]-=1
    f[i][0]=a[i]
#do binary lifting 
for j in range(1,60):
    for i in range(n):
        f[i][j]=f[f[i][j-1]][j-1]
ans=0
for j in range(59,-1,-1):
    if 1<<j<=k:
        ans=f[ans][j]
        k-=1<<j
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
t_list = list(map(int, input().split()))
go_list = [1] + [-1]*N
hige = 0
syuuki = 0

i = 0
while i <= N:
  if go_list[i] == -1:
    if go_list.count(t_list[go_list[i-1]-1]) == 0:
      go_list[i] = t_list[go_list[i-1]-1]
    else:
      hige = go_list.index(t_list[go_list[i-1]-1])
      syuuki = i - hige
      break
  i += 1

if K > hige:
  K -= hige
  K %= syuuki
  K += hige

print(go_list[K])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
t_list = list(map(int, input().split()))
go_list = [-1]*N
go_list[0] = 1
hige = 0
syuuki = 0

i = 0
while i < N:
  if go_list[i] == -1:
    if go_list.count(t_list[go_list[i-1]-1]) == 0:
      go_list[i] = t_list[go_list[i-1]-1]
    else:
      hige = go_list.index(t_list[go_list[i-1]-1])
      syuuki = i - hige
      break
  i += 1

if K > hige:
  K -= hige
  K %= syuuki
  K += hige

print(go_list[K])

Submission status: Time Limit Exceeded

Solution code:
n,k = (int(x) for x in input().split())
a = [int(x) for x in input().split()]

l = [1]
now = 1
next = a[0]
notloop = 0
dupl = -1

for i in range(k):
  now = next
  next = 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())
a = [int(s)-1 for s in input().split()]

start = 0
for _ in range(k):
    start = a[start]

print(start + 1)

Submission status: Time Limit Exceeded

Solution code:
n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
idx=1
li=[]
idx_li=[1]
flag=False
for i in range(k):
    idx=a[idx-1]
    if idx in idx_li:
        flag=True
        break
    idx_li.append(idx)
if flag:
    #non_loop=idx_li[:idx_li.index(idx)]
    loop = idx_li[idx_li.index(idx):]
    
    size=len(loop)
    print(loop[(k-(len(idx_li)-len(loop)))%size])
else:
    print(idx)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
import sys
sys.setrecursionlimit(10**9)

def f(L):
    if A[L[-1]-1] not in L:
        L_next = L + [A[L[-1]-1]]
        return f(L_next)
    else:
      return L
L = [1]
P = f(L)
a = A[P[-1]-1]
j = P.index(a)
r = len(P)
l = r - j
if k+1 <= j:
    print(P[k])
else:
    print(P[j+(k-j)%l])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N,K = map(int, sysread().split())
    A = [0] + list(map(int, sysread().split()))

    seen = [False] * (N+1)
    arr = [1]
    seen[1] = True
    while True:
        next = A[arr[-1]]
        if seen[next]:
            arr.append(next)
            break
        arr.append(next)
        seen[next] = True

    x = int(math.log2(K)) + 1
    dub = [[0] * (N+1) for _ in range(x)]
    for idx, a in enumerate(arr[:-1]):
        dub[0][a] = arr[idx+1]
    for d in range(1,x):
        for k in arr[:-1]:
            tmp = dub[d - 1][k]
            #if tmp == 0:continue
            dub[d][k] = dub[d-1][tmp]

    ret = 1
    while K:
        d = int(math.log2(K))
        K -= 1 << d
        ret = dub[d][ret]
    print(ret)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N,K = map(int, sysread().split())
    A = [0] + list(map(int, sysread().split()))

    seen = [False] * (N+1)
    arr = [1]
    seen[1] = True
    while True:
        next = A[arr[-1]]
        if seen[next]:
            arr.append(next)
            break
        arr.append(next)
        seen[next] = True

    x = int(math.log2(K)) + 1
    dub = [[0] * (N+1) for _ in range(x)]
    for idx, a in enumerate(arr[:-1]):
        dub[0][a] = arr[idx+1]
    for d in range(1,x):
        for k in range(1, N+1):
            tmp = dub[d - 1][k]
            #if tmp == 0:continue
            dub[d][k] = dub[d-1][tmp]

    ret = 1
    while K:
        d = int(math.log2(K))
        K -= 1 << d
        ret = dub[d][ret]
    print(ret)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N,K = map(int, sysread().split())
    A = [0] + list(map(int, sysread().split()))

    seen = [False] * (N+1)
    arr = [1]
    seen[1] = True
    while True:
        next = A[arr[-1]]
        if seen[next]:
            arr.append(next)
            break
        arr.append(next)
        seen[next] = True

    x = int(math.log2(K)) + 1
    dub = [[-1] * (N+1) for _ in range(x)]
    for idx, a in enumerate(arr[:-1]):
        dub[0][a] = arr[idx+1]
    for d in range(1,x):
        for k in range(1, N+1):
            tmp = dub[d - 1][k]
            if tmp == -1:continue
            dub[d][k] =  dub[d-1][tmp]

    ret = 1
    while K:
        d = int(math.log2(K))
        K -= 1 << d
        ret = dub[d][ret]
    print(ret)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
pos=0
while(k!=0):
  m=l[pos]
  pos=m-1
  k-=1
print(pos+1)

Submission status: Time Limit Exceeded

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

ans =1
now = [1]
ed = set([1])

for i in range(n+1):
    if a[now[i]-1] in ed:
        break
    now.append(a[now[i]-1])
    ed = set(now)
    
t = len(now)-now.index(a[now[i]-1])
f = now.index(a[now[i]-1])


if k >= f + t:
    p = (k-f)%t
    k = f + p
    

print(now[k])

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):
    C = A[C-1]
    if C not in listb:
        listb.append(C)
    else:
        D = listb.index(C)
        listb.append(C)
        break

L = len(listb) -1

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

ans =1
now = [1]
ed = set([1])

for i in range(k):
    if a[now[i]-1] in ed:
        break
    now.append(a[now[i]-1])
    ed = set(now)
    
t = len(now)-now.index(a[now[i]-1])
f = now.index(a[now[i]-1])


if k >= f + t:
    p = (k-f)%t
    k = f + p
    

print(now[k])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
now = [1]
ans =1
 
for i in range(k):
    if a[now[i]-1] in now:
        break
    now.append(a[now[i]-1])
 
    
t = len(now)-now.index(a[now[i]-1])
f = now.index(a[now[i]-1])


if k >= f + t:
    p = (k-f)%t
    k = f + p
    

print(now[k])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
now = [1]
ans =1
 
for i in range(k):
    if a[now[i]-1] in now:
        break
    now.append(a[now[i]-1])
 
    
t = len(now)-now.index(a[now[i]-1])
f = now.index(a[now[i]-1])


if k >= f + t:
    p = (k-f)%t
    k = f + p
    
for _ in range(k):
    ans = a[ans-1]
print(ans)

Submission status: Time Limit Exceeded

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

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

else:
    print(visited[-1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
A = [-1] + A
memo = [1]
i = 0
town = 1
judge = True
while judge:
    town = A[town]
    i += 1
    if town in memo:
        judge = False
    memo.append(town)
outlier = memo.index(memo[-1])
T = len(memo) - memo.index(memo[-1]) - 1
if k <= outlier:
    print(memo[k])
else:
    print(memo[outlier + (k-outlier) % T])

Submission status: Time Limit Exceeded

Solution code:
import math

# doubling

n, k = list(map(int, input().split()))
nums = [-1] + list(map(int, input().split()))
doubling =[[0 for _ in range(n + 1)] for _ in range(62)]

for i in range(62):
	for j in range(1, n + 1):
		if i == 0:
			doubling[i][j] = nums[j]
		else:
			doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]

cur = 1
for i, x in enumerate(bin(k)[2:][::-1]):
	if x == "1":
		cur = doubling[i][cur]
print(cur)

Submission status: Time Limit Exceeded

Solution code:
import math

# doubling

n, k = list(map(int, input().split()))
nums = [-1] + list(map(int, input().split()))
doubling =[[0 for _ in range(n + 1)] for _ in range(int(math.log2(k)) + 1)]

for i in range(len(doubling)):
	for j in range(1, n + 1):
		if i == 0:
			doubling[i][j] = nums[j]
		else:
			doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]

cur = 1
for i, x in enumerate(bin(k)[2:][::-1]):
	if x == "1":
		cur = doubling[i][cur]
print(cur)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
bit = k.bit_length()
table = [[0]*bit for _ in range(n)]
for i in range(n):
    table[i][0] = A[i]

for i in range(1, bit):
    for j in range(n):
        table[j][i] = table[table[j][i-1]][i-1]

ans = 0
for i in reversed(range(bit)):
    if (1 << i) <= k:
        k -= 1 << i
        ans = table[ans][i]
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    # 町の数N, 町iの転送先はindexがAi-1の町
    N,K = map(int, input().split())
    A = list(map(int, input().split()))

    # K回移動した時の町番号を出力
    # もし一度出てきた番号が出てきたら記憶している道順リストを使う
    # 最初は道を覚えさせる作業が必要
    now = 0
    history = [0]
    i = 0
    for i in range(K):
        # まず進む
        now = A[now]-1
        # 道順登録
        if now not in set(history): # ここが線形探索なのが遅い
            history.append(now)
            i+=1
        # 以前出てきてる町ならそこから末尾までを自動で進めてiのカウントも進める
        else:
            start = history.index(now)
            r = start + (K-1-i)%(len(history)-start)
            now = history[r]
            break

    print(now+1)

main()

Submission status: Time Limit Exceeded

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

o = [0] * 63

def bi(x):
    i = 0
    while x != 0:
        o[i] = x%2
        x //= 2
        i += 1

bi(K)

n = 0
for i in range(63):
    if o[i]:
        n = A[n]
    A = [A[A[x]] for x in range(N)]
        
print(n+1)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
memo = []
memo_cir = []
index = 0
flag = True
while flag:
    if index in memo:
        flag = False
    else:
        memo.append(index)
        index = a[index] - 1
flag = False
for i_ in memo:
    if i_ == index:
        flag = True
    if flag:
        memo_cir.append(i_)
if k + 1 >= (len(memo) - len(memo_cir)):
    k -= (len(memo) - len(memo_cir) - 1)
    print(memo_cir[(k % len(memo_cir)) - 1] + 1)
else:
    print(memo[k] + 1)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
city_list = list(map(int, input().split()))
th_list = []
n = 0
count = 0
for i in range(N):
    count += 1
    th_list.append(n)
#   print(n)
    n = city_list[n] - 1
''' if n in th_list:
        #繰り返されている個数を出す
        num = len(th_list)-th_list.index(n)
        break'''

#print(city_list, th_list)
count = -1
for i in range(N):
    if th_list.count(th_list[i]) > 1:
        break
list = [x for x, l in enumerate(th_list) if l == th_list[i]]
#print(list)
#print(list[0])
#print(th_list)
if K > N:
    print(th_list[(K-list[0])%(list[1]-list[0])+list[0]]+1)
else:
    print(th_list[K]+1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    # 町の数N, 町iの転送先はindexがAi-1の町
    N,K = map(int, input().split())
    A = list(map(int, input().split()))

    # K回移動した時の町番号を出力
    # もし一度出てきた番号が出てきたら記憶している道順リストを使う
    # 最初は道を覚えさせる作業が必要
    now = 0
    history = [0]
    i = 0
    while i<K:
        # まず進む
        now = A[now]-1
        # 道順登録
        if now not in set(history): # ここが線形探索なのが遅い
            history.append(now)
            i+=1
        # 以前出てきてる町ならそこから末尾までを自動で進めてiのカウントも進める
        else:
            start = history.index(now)
            r = start + (K-1-i)%(len(history)-start)
            now = history[r]
            break

    print(now+1)

main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n,k = (int(x) for x in input().split())
a = [int(x) for x in input().split()]

l = [1]
now = 1
next = a[0]
count = 0
dupl = -1

for i in range(k):
  now = next
  next = a[now-1]
  
  if now in l:
    dupl = now
    break
  else:
    l.append(now)

if(dupl == -1):
  print(now)

else:
  length = len(l)
  for i in range(length):
    if l[0] == dupl:
      break
    else:
      count += 1
      l.remove(l[0])
    
  length = len(l)
  print(l[(k-count)%length])

Submission status: Time Limit Exceeded

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

N,K = map(int,readline().split())
A = [0] + list(map(int,readline().split()))

c = 1
while K:
  if K&1:
    c = A[c]
  na = [0] * (N+1)
  for i in range(N+1):
    na[i] = A[A[i]]
  A = na
  K >>= 1
print(c)

Submission status: Time Limit Exceeded

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

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


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

Submission status: Time Limit Exceeded

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

N,K = map(int,readline().split())
A = [0] + list(map(int,readline().split()))

c = 1
while K:
  if K&1:
    c = A[c]
  na = [0] * (N+1)
  for i in range(N+1):
    na[i] = A[A[i]]
  na,A = A,na
  K >>= 1
print(c)

Submission status: Time Limit Exceeded

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

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

print(t)

Submission status: Time Limit Exceeded

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

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

ans = route[-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

    is_loop = False
    diff = [0] # start
    pos = 0
    for _ in range(k):
        pos = a_list[pos] - 1
        if len(diff) != len(set(diff)):
            diff.append(pos)
            is_loop = True
            break
        diff.append(pos)

    # 周期が見える前に終わった
    if not is_loop:
        print(pos+1)
    else:
        last = len(diff)-1
        for i in range(len(diff)):
            if diff[i] == pos:
                break
        #tmp = list(np.where(np.array(diff)==pos)[0])
        first = i
        t = last - first # 周期
        buff = first # 前半のバッファ
        print(diff[buff+(k-buff)%t]+1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
A = input().split()
A.insert(0,0)
position = 1
B = []
C = []

for i in range(N):
  if (int(A[position]) in B):
    B.append(position)
    C = B[B.index(int(A[position])):]
    break
  else:
    B.append(position)
    if position in A:
      C.append(position)
    position = int(A[position])

if K > len(B):
  x = (K - len(B)) % len(C)
  print(C[x])
else:
  print(B[K])

Submission status: Time Limit Exceeded

Solution code:
n,k = [int(i) for i in input().split()]
data = [int(i) for i in input().split()]

d = 1
count = 0
loop = []
route = [-1] * n
data_len = len(data)

for i in range(data_len):
    route[i] = d
    d = data[d-1]
    if d in route:
        loop = route[route.index(d):route.index(-1)]
        break
loop_len = len(loop)
if loop_len > 0:
    a = len(route[:route.index(-1)]) - loop_len
    if k < a:
        print(route[k])
    else:
        print(loop[(k-a)%loop_len])
else:
    print(route[k])

Submission status: Time Limit Exceeded

Solution code:

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

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

    # 周期が見える前に終わった
    if not is_loop:
        print(pos+1)
    else:
        last = len(diff)-1
        for i in range(len(diff)):
            if diff[i] == pos:
                break
        #tmp = list(np.where(np.array(diff)==pos)[0])
        first = i
        t = last - first # 周期
        buff = first # 前半のバッファ
        print(diff[buff+(k-buff)%t]+1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n, k = na()
a = na()

dp = [[-1] * (n + 1) for _ in range(61)]
for i in range(n):
    dp[0][i] = a[i] - 1
for i in range(60):
    for j in range(n):
        dp[i + 1][j] = dp[i][dp[i][j]]

cur = 0
for i in range(60, -1, -1):
    if k & (1 << i):
        cur = dp[i][cur]

print(cur + 1)

Submission status: Time Limit Exceeded

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

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

ans = route[-1]
print(ans)

Submission status: Time Limit Exceeded

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

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

ans = route[-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

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

# 周期が見える前に終わった
if not is_loop:
    print(pos+1)
else:
    last = len(diff)-1
    for i in range(len(diff)):
        if diff[i] == pos:
            break
    #tmp = list(np.where(np.array(diff)==pos)[0])
    first = i
    t = last - first # 周期
    buff = first # 前半のバッファ
    print(diff[buff+(k-buff)%t]+1)