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())
telep = list(map(int, input().split()))
check = [1] #テレポi回やったときの位置をcheck[i]で示す。
now = 1 #テレポi回目の現在地

if telep[0] == 1:
  print(1)
  exit()
else:
  for i in range(1, n+1):
    now = telep[check[i-1]-1]
    if not now in check:
      check.append(now)
    else:
      s = check.index(now)
      roop = i - s
      break
      
  def tel_n(i): #テレポi回目での地点。0から。
    if i <= s+roop-1:
      return check[i]
    else:
      for r in range(s, s+roop):
        if (i-r)%roop == 0:
          return check[r]

  print(tel_n(k))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
A=[0]+A
B=[]
C=[0]+[-1]*n
now_city=1
seen=set()
for i in range(1,len(A)):
    now_city=A[now_city]
    if now_city in B:
        route=B[C[now_city]-1:i-1]
        break
    B.append(now_city)
    C[now_city]=i
if k <= len(B):
    print(B[k-1])
else:
    k = k- len(B)
    x = k % len(route)
    if x ==0:
        print(route[-1])
    else:
        print(route[x-1])

Submission status: Time Limit Exceeded

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

def memorize(f):
  table = {}
  def func(*args):
    if not args in table:
      table[args] = f(*args)
    return table[args]
  return func

@memorize
def tel(i): #i回テレポやったときの地点
  if i == 1:
    return telep[i-1]
  return telep[tel(i-1)-1]
  
# N回回したときにループする点を探す。
check = []
for i in range(1, n+1):
  if not tel(i) in check:
    check.append(tel(i))
  else: #i回目でかぶりが見つかった.roop = i -(最初のかぶりのリスト番号)
    s = check.index(tel(i))+1
    roop = i - s
    break
    
#テレポs回目からループ開始。roop回数でループする。(s=2, roop=2のとき、tel(2k+2)=tel(2))

def tel_n(i): #テレポi回目での地点。0から。
  if i <= s+roop-1:
    return tel(i)
  else:
    for r in range(s, s+roop):
      if (i-r)%roop == 0:
        return tel(r)
      
print(tel_n(k))

Submission status: Time Limit Exceeded

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

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)%L])

Submission status: Time Limit Exceeded

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

X = 0
town = 1
counted = [0 for _ in range(N)]
for k in range(N):
  X += 1
  counted[k] = town
  town = A[town-1]
  if town in counted:
    ini = counted.index(town)
    Q = X - ini
    break
if K >= ini:    
  num = (K-ini) % Q
  print(counted[ini+num])
else:
  print(counted[K])

Submission status: Time Limit Exceeded

Solution code:
now = 1
n,k = map(int,input().split())
a = []
a = list(map(int,input().split()))
for i in range(k):
    now = a[now-1]
print(now)

Submission status: Time Limit Exceeded

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

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

explored = [0] * (n+1)
t = 1
cycle = 0
while True:
    if explored[t] == 2:
        k %= cycle
        explored[t] += 1
    elif explored[t] == 1:
        explored[t] += 1
        cycle += 1
    elif explored[t] == 0:
        explored[t] += 1
    k -= 1

    if k == 0:
        break
    else:
        t = a[t]
    

print(a[t])

Submission status: Time Limit Exceeded

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

array=map(int,input().split())

A=list(array)
A.insert(0,0)

visit=[]
visited=1
once=0
while True:
    visit.append(visited)
    once+=1
    if A[visited] in visit:
        break
    visited=A[visited]

roop=visit[visit.index(A[visited]):]
if K<once:
    print(visit[K])
else:
    order=K-once
    print(roop[order%len(roop)])

Submission status: Time Limit Exceeded

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

array=map(int,input().split())

A=[0]
for i in array:
    A.append(i)

visit=[]
visited=1
once=0
while True:
    visit.append(visited)
    once+=1
    if A[visited] in visit:
        break
    visited=A[visited]

roop=visit[visit.index(A[visited]):]
if K<once:
    print(visit[K])
else:
    order=K-once
    print(roop[order%len(roop)])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
s = list(map(int,input().split()))
# print(s)
now_city = 1
s_l_city = 1
t = [1] #何回そこを通ったか
f = [0] #何回目にそこを通ったか
a=0
b = 0#サイクルありなし
f_l=0
for i in range(n-1):
    t.append(0)
    f.append(-1)
# print(s)
sycle = 0
for i in range(1,n+1):
    now_city = s[now_city-1]
    t[now_city-1]+=1
    for j in range(n):
        if t[j]==2:
        #  print(i,f[j])
         sycle=i-f[j]
         f_l=f[j]
         a = 1
         b = 1
         s_l_city=j+1
         break
    if a==1:
        break
    f[now_city-1]=i
# print(t)
# print(f_l,sycle,s_l_city)
if b==1:
    now_city=s_l_city
    for j in range((k-f_l)%sycle):
        now_city = s[now_city-1]
    print(now_city)
else:
    for j in range(k):
        now_city=s[now_city]
    print(now_city)

Submission status: Time Limit Exceeded

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

A=[0]
INPUT=map(int,input().split())
for i in INPUT:
    A.append(i)

dist=[1]
pre=[]
num=0
K_cp=K
while dist:
    tele=dist.pop()
    if tele in pre:
        flg=False
        break
    dist.append(A[tele])
    num+=1
    if num==K:
        flg=True
        break
    pre.append(tele)
    K_cp-=1

if not flg:
    start=pre.index(tele)
    cir=pre[start:]
    cir_len=len(cir)
    dist_num=(K_cp%cir_len)
    dist.append(cir[dist_num])
    flg=True

if flg:
    print(dist.pop())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    N,K=map(int,input().split())

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

    loop=[]

    slack_que=deque([])
    flag=0
    t=0
    start=0
    while flag==0:
        slack_que.append(t)
        t=A[t]
        slack_que.append(t)
        ind=slack_que.index(t)
        if (ind!=len(slack_que)-1):
            start=ind
            flag=1
        slack_que.pop()

    slack=list(slack_que)
    slack_num=start
    loop_num=len(slack)-slack_num

    # print(slack)
    # print(start)
    # print(slack_num)
    # print(loop_num)
    #
    loop=slack[start:]
    # print(loop)
    if (K-slack_num)<0:
        res=slack[K]+1
    else:
        tele_num=((K-slack_num)%loop_num)
        town=loop[tele_num]
        res=town+1

    print(res)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    N,K=map(int,input().split())

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

    loop=[]
    slack=[]

    flag=0
    t=0
    start=0
    while flag==0:
        slack.append(t)
        t=A[t]
        if (t in slack):
            start=slack.index(t)
            flag=1

    slack_num=start
    loop_num=len(slack)-slack_num

    # print(slack)
    # print(start)
    # print(slack_num)
    # print(loop_num)
    #
    loop=slack[start:]
    # print(loop)
    if (K-slack_num)<0:
        res=slack[K]+1
    else:
        tele_num=((K-slack_num)%loop_num)
        town=loop[tele_num]
        res=town+1

    print(res)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

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

A0 = A[0]
for _ in range(K-1):
    A0 = A[A0-1]

print(A0)

Submission status: Time Limit Exceeded

Solution code:

def parse():
  N, K = map(int, input().split(" "))
  A = []
  for a in input().split(" "):
    A.append(int(a) - 1)
  return N, K, A

def fast_pow(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

def fast_mod(x, N):
  # return x % N
  if N % 2 == 0:
    return x & (N - 1)
  else:
    return x % N

def main():
  N, K, A = parse()
  # print(N, K, A)

  # 移動
  town = 0
  route = [0]
  loop_start_index = None
  i = 0
  for i in range(K):
    # 次の町に移動
    town = A[town]

    if town in route:
      # ループ検出
      loop_start_index = route.index(town)
      break

    route.append(town)

  if loop_start_index == None:
    print(town + 1)
  else:
    loop_route = route[loop_start_index:]
    # print(loop_route, K, i)
    print(loop_route[(K - (i + 1)) % len(loop_route)] + 1)
    # print(loop_route[])
  # print(town)
  exit(0)

  # 経路の計算
  route = []
  next_town = A[0]
  town = 0
  while not (next_town in route):  # 既出の町に行く場合
    route.append(town)
    next_town = A[town]
    town = next_town
  once_route = route[:route.index(next_town)]
  loop_route = route[route.index(next_town):]
  # print("once_route:", once_route)
  # print("loop_route:", loop_route)
  
  

  # print([town + 1 for town in route])
  # print("K %% len(loop_route):", K % len(loop_route))
  # print(route[K % len(loop_route) + len(once_route)] + 1)
  if K >= len(route) and len(once_route) > 0:
    # print("loop")
    loop_K = K - len(route)
    print(loop_route[fast_mod(loop_K, len(loop_route))] + 1)
    # print(loop_route[loop_K % len(loop_route)] + 1)
  else:
    # print("normal")
    # print(route[fast_mod(K, len(loop_route))] + 1)
    # print("K:", K)
    # print("K %% len(route):", K % len(route))
    print(route[fast_mod(K, len(route))] + 1)
    # print(route[K % len(route)] + 1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().rstrip().split())
route = [0] + list(map(int, input().rstrip().split()))

# 愚直解 計算時間大
current = 1
for _ in range(K):
    current = route[current]

print(current)

Submission status: Time Limit Exceeded

Solution code:

def parse():
  N, K = map(int, input().split(" "))
  A = []
  for a in input().split(" "):
    A.append(int(a) - 1)
  return N, K, A

def fast_mod(x, N):
  return (x * N) >> 32

def main():
  N, K, A = parse()
  # print(N, K, A)

  # 経路の計算
  route = []
  next_town = A[0]
  town = 0
  while not (next_town in route):  # 既出の町に行く場合
    route.append(town)
    next_town = A[town]
    town = next_town
  once_route = route[:route.index(next_town)]
  loop_route = route[route.index(next_town):]
  # print("once_route:", once_route)
  # print("loop_route:", loop_route)
  
  # print([town + 1 for town in route])
  # print("K %% len(loop_route):", K % len(loop_route))
  # print(route[K % len(loop_route) + len(once_route)] + 1)
  if K > len(route) and len(once_route) > 0:
    # print("loop")
    loop_K = K - len(route)
    print(loop_route[loop_K % len(loop_route)] + 1)
  else:
    # print("normal")
    # print(route[fast_mod(K, len(loop_route))] + 1)
    # print("K:", K)
    # print("K %% len(route):", K % len(route))
    print(route[K % len(route)] + 1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
towns = list(map(int, input().split()))
towns.insert(0, -1)
p = 1
tmp_move, first_move, roop_move = [1], [], []
res = -1

while True:
    if towns[p] in tmp_move:
        roop_move = tmp_move[tmp_move.index(towns[p]):]
        first_move = tmp_move[:tmp_move.index(towns[p])]
        break
    else:
        tmp_move.append(towns[p])
        p = towns[p]

if K < len(first_move):
    res = first_move[K]
else:
    index = (K - len(first_move)) % len(roop_move)
    res = roop_move[index]

print(res)

Submission status: Time Limit Exceeded

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

a = 0
n = A[0]
lis = [1,n]

while a < K - 1:
    a = a + 1
    n = A[n-1]
    if n == 1:
        break
    lis.append(n)

print(lis[K % len(lis)])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
town=[1]
cnt=0
loop=0
index=0
while(cnt == index):
    town.append(a[town[-1]-1])
    cnt+=1
    index=town.index(town[-1])

town.pop(-1)
loop=cnt-index


if k<index:
    print(town[k])
else:
    k-=index
    k%=loop
    print(town[index+k])

Submission status: Time Limit Exceeded

Solution code:

n, k = map(int, input().split()) 
X = list(map(int, input().split()))
cc = []
dd = 0
ff = []
gg = []
for i in range(n+1):
    if i == 0:
        aa = 1
    else:
        aa = X[aa-1]
    cc = cc + [aa]
    for i in range(len(cc)):
        for j in range(i):
            if i != j and cc[i] == cc[j]:
                dd = j
                ee = i
                ff = ff + [j]
                gg = gg + [i]
                break
        if len(ff) > 1:
            break


hh = gg[0] - ff[0]
ii = (k-ff[0]) % (gg[0] - ff[0])
jj = ff[0] + ii
print(cc[jj])

Submission status: Time Limit Exceeded

Solution code:

n, k = map(int, input().split()) 
X = list(map(int, input().split()))
cc = []
dd = 0
for i in range(n+1):
    if i == 0:
        aa = 1
    else:
        aa = X[aa-1]
    cc = cc + [aa]

ff = []
gg = []
for i in range(len(cc)):
    for j in range(i):
        if i != j and cc[i] == cc[j]:
            dd = j
            ee = i
            ff = ff + [j]
            gg = gg + [i]
            break
    if len(ff) > 1:
        break
hh = gg[0] - ff[0]
ii = (k-ff[0]) % (gg[0] - ff[0])
jj = ff[0] + ii
print(cc[jj])

Submission status: Time Limit Exceeded

Solution code:

n, k = map(int, input().split()) 
X = list(map(int, input().split()))
cc = []
dd = 0
for i in range(n+1):
    if i == 0:
        aa = 1
    else:
        aa = X[aa-1]
    cc = cc + [aa]

ff = []
gg = []
for i in range(len(cc)):
    for j in range(i):
        if i != j and cc[i] == cc[j]:
            dd = j
            ee = i
            ff = ff + [j]
            gg = gg + [i]
            break
        if len(ff) > 1:
            break
hh = gg[0] - ff[0]
ii = (k-ff[0]) % (gg[0] - ff[0])
jj = ff[0] + ii
print(cc[jj])

Submission status: Time Limit Exceeded

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

for i in range(K):
    next=A[next-1]

print(next)

Submission status: Time Limit Exceeded

Solution code:


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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split()) 
X = list(map(int, input().split()))
cc = []
dd = 0
for i in range(n+1):
    if i == 0:
        aa = 1
    else:
        aa = X[aa-1]
    cc = cc + [aa]

ff = []
gg = []
for i in range(len(cc)):
    for j in range(i):
        if i != j and cc[i] == cc[j]:
            dd = j
            ee = i
            ff = ff + [j]
            gg = gg + [i]
            break
            break
hh = gg[0] - ff[0]
ii = (k-ff[0]) % (gg[0] - ff[0])
jj = ff[0] + ii
print(cc[jj])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split()) 
X = list(map(int, input().split()))
cc = []
dd = 0
for i in range(n+1):
    if i == 0:
        aa = 1
    else:
        aa = X[aa-1]
    cc = cc + [aa]

ff = []
gg = []
for i in range(len(cc)):
    for j in range(i):
        if i != j and cc[i] == cc[j]:
            dd = j
            ee = i
            ff = ff + [j]
            gg = gg + [i]
            break
hh = gg[0] - ff[0]
ii = (k-ff[0]) % (gg[0] - ff[0])
jj = ff[0] + ii
print(cc[jj])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split()) 
X = list(map(int, input().split()))
cc = []
dd = 0
for i in range(n+1):
    if i == 0:
        aa = 1
    else:
        aa = X[aa-1]
    cc = cc + [aa]

ff = []
gg = []
for i in range(len(cc)):
    for j in range(i):
        if i != j and cc[i] == cc[j]:
            dd = j
            ee = i
            ff = ff + [j]
            gg = gg + [i]
hh = gg[0] - ff[0]
ii = (k-ff[0]) % (gg[0] - ff[0])
jj = ff[0] + ii
print(cc[jj])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ruto = [1]
cnt = 0
saki = a[0]
for i in range(n):
    if cnt != k:
        if saki not in ruto:
            ruto.append(saki)
            cnt += 1
            saki = a[saki-1]
        else:
            where = ruto.index(saki)
            ruto = ruto[where:]
            K = k-where
            ans = K%len(ruto)
            print(ruto[ans])
            break
    else:
        print(ruto[-1])
        break

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
l = [0]+list(map(int, input().split()))
#tp = {key: l[key-1] for key in range(1, n+1)}
path = [-1]*n
to = 1

if n > k:
    for i in range(k):
        to = l[to]
    print(to, end="")
    exit()

for i in range(n):
    if to in path:
        path[i] = (to)
        p = i
        break
    path[i] = (to)
    to = l[to]

lp_st = (path.index(path[p]))
loop = p - lp_st

k -= lp_st
k = k % loop
to = path[lp_st]
for i in range(k):
    to = l[to]
#print(path[k+lp_st], end="")
print(to, end="")

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
l = [0]+list(map(int, input().split()))
#tp = {key: l[key-1] for key in range(1, n+1)}
path = []
to = 1
if n > k:
    for i in range(k):
        to = l[to]
    print(to, end="")
    exit()

for i in range(n):
    if to in path:
        path.append(to)
        break
    path.append(to)
    to = l[to]

lp_st = (path.index(path[-1]))
loop = len(path) - lp_st - 1

k -= lp_st
k = k % loop
to = path[lp_st]
for i in range(k):
    to = l[to]
#print(path[k+lp_st], end="")
print(to, end="")

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [1]
cnt = 0
next_town = 0

l = len(a)
for j in range(l):
    cnt += 1
    if j==0:
        b.append(a[0])
        next_town = a[0]
        continue
    
    b.append(a[next_town - 1])
    next_town = a[next_town -1]
    for i in range(l):
        if b.count(i+1)==2:
            k -= cnt
            idx_f = b.index(i+1)
            roop_list = b[idx_f:-1]
            roop_num = len(b[idx_f:-1])
            last = k %roop_num

            print(roop_list[last])
            sys.exit()

Submission status: Time Limit Exceeded

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

A.insert(0,-1)
root = [1]
next = A[1]
rf = 0

for _ in range(K):
    if next in root:
        rf = root.index(next)
        root = root[rf:]
        break
    root.append(next)
    next = A[next]

print(root[(K - rf) % len(root)])

Submission status: Time Limit Exceeded

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

A.insert(0,-1)
root = [1]
next = A[1]
rf = 0

for _ in range(K):
    if next not in root:
        root.append(next)
        next = A[next]
    else:
        rf = root.index(next)
        root = root[rf:]
        break

print(root[(K - rf) % len(root)])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    path = [-1] * N * 2
    idx = 0
    visited = [False] * N
    cur = 0
    while K:
        if visited[cur]:
            loop = idx - path.index(cur)
            K %= loop
        path[idx] = cur
        visited[cur] = True
        cur = A[cur] - 1
        K -= 1
        idx += 1
    print(cur + 1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    path = []
    visited = set()
    cur = 0
    while K:
        if cur in visited:
            loop = len(path) - path.index(cur)
            K %= loop
        path.append(cur)
        visited.add(cur)
        cur = A[cur] - 1
        K -= 1
    print(cur + 1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k = [int(i) for i in input().split()]
 
a = [int(i) - 1  for i in input().split()]
 
l = [a[0]]
j = a[0]
for i in range(1,k):
    j = a[j]
    if j in l:
        break
    else:
        l.append(j)
        
m = l.index(j) 
 
length = len(l) - m
l = l[m:]
 
l = {idx + 1:i for idx,i in enumerate(l)}
l[0] = l[length]
del l[length]
 
m = (k - m) % length
 
print(l[m] + 1)

Submission status: Time Limit Exceeded

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

array = input().split()
for i in range(len(array)):
    array[i] = int(array[i])

now = 1

history = []
start_number = -1

for i in range(K):
    history.append(now)
    now = array[now - 1]
    if(now in history):
        start_number = now
        break

if not(start_number == -1):
    start_ind = history.index(start_number)
    length = len(history) - start_ind
    mod = (K - start_ind) % length
    now = history[start_ind + mod]

print(now)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [int(t) - 1 for t in input().split()]

loc = 0
visited_list = []
loop_idx = -1
while True:
    visited_list.append(loc + 1)
    loc = a[loc]
    if loc + 1 in visited_list:
        loop_idx = visited_list.index(loc + 1)
        break
loop_len = len(visited_list) - loop_idx
start_len = len(visited_list) - loop_len
print(visited_list[start_len + (k - start_len) % loop_len] if k >= len(visited_list) else visited_list[k])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
dic = {}
l = list(map(int, input().split()))
for i in range(1,n+1):
    
    dic[i] = l[i-1]
j = 1
reached=[1]
for _ in range(k):
    
    ans = dic[j]
    if ans in reached:
        break
    reached.append(ans)
    
    j = ans

for i in range(len(reached)):
    if ans == reached[i]:
        break

loc = (k-i) % (len(reached[i:]))

print(reached[i+loc])

Submission status: Time Limit Exceeded

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

A={}

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

f=True
U=[]

v=1

k=0

while (v not in set(U)) and (k<=K):
    U.append(v)
    v=A[v]
    k+=1
    
if v not in U:
    print(U[-1])
else:
    g=U.index(v)
    U=U[g:]
    K-=g

    m=len(U)
    print(U[K%m])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = []
S.append(1)
S.append(A[0])
while True:
    idx = S[-1]
    loc = A[idx-1]
    if loc not in S:
        S.append(loc)
    else:
        start = S.index(loc)
        end = len(S)
        span = end - start
        break

if K <= end:
    print(S[K])
else:
    n = (K-start)%span
    print(S[start:][n])

Submission status: Time Limit Exceeded

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

A={}

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

f=True
U=[]
v=1

k=0

while (v not in U) and (k<=K):
    U.append(v)
    v=A[v]
    k+=1
    
if v not in U:
    print(U[-1])
else:
    g=U.index(v)
    U=U[g:]
    K-=g

    m=len(U)
    print(U[K%m])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())
A = list(map(lambda s: int(s)-1, input().split()))

n = 0
visit = [0]
for _ in range(K):
    n = A[n]
    if n not in visit:
        visit += [n]
    else:
        loop_start = visit.index(n)
        loop_length = len(visit) - loop_start
        print(visit[loop_start + ((K-loop_start) % loop_length)]+1)
        break
else:
    print(visit[-1]+1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

rem=k
nxt=1
visit=[]
for i in range(k):
    visit.append(nxt)
    nxt=a[nxt-1]
    if nxt in visit:
        break
    rem-=1

if rem==0:
    print(nxt)
else:
#    print('-'*60)
#    print('nxt=', nxt)
#    print('rem=', rem)
#    print('visit=', visit)
    
    loops=visit[visit.index(nxt):]
    print(loops[(rem-1)%len(loops)])    
    
#    print('-'*60)
#    print('loops=', loops)

Submission status: Time Limit Exceeded

Solution code:
            
import sys
stdin=sys.stdin

ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))

N,K=nm()
A=nl()

D=60
MAX_N=2000005
to=[[0]*MAX_N for i in range(D)]

to[0][1:N+1]=A

for i in range(D-1):
    for j in range(1,N+1):
        to[i+1][j]=to[i][to[i][j]]

v=1
for i in range(D-1,-1,-1):
    l = 1<<i
    if(l<=K):
        v=to[i][v]
        K-=l

print(v)

Submission status: Time Limit Exceeded

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

p = 1
points = [p]
for _ in range(N):
    p = A[p]
    if p in points:
        break
    points.append(p)

idx = points.index(p)

if idx > K:
    print(points[K])
    exit()

cycle = points[idx:]

print(cycle[(K - idx) % len(cycle)])

Submission status: Time Limit Exceeded

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

p = 1
points = [p]
for _ in range(N):
    p = A[p]
    if p in points:
        break
    points.append(p)

idx = points.index(p)

if idx > K:
    print(points[K])
    exit()

head = points[:idx]
cycle = points[idx:]

print(cycle[(K - len(head)) % len(cycle)])

Submission status: Time Limit Exceeded

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

p = 1
points = [p]
for _ in range(N):
    p = A[p]
    if p in points:
        break
    points.append(p)

idx = points.index(p)

if idx > K:
    print(points[K])
    exit()

head = len(points[:idx])
cycle = len(points[idx:])

for _ in range((K - head) % cycle):
    p = A[p]

print(p)

Submission status: Time Limit Exceeded

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

p = 1
points = [p]
for _ in range(K):
    p = A[p]
    if p in points:
        break
    points.append(p)

head = len(points[:points.index(p)])
cycle = len(points[points.index(p):])

for _ in range((K - head) % cycle):
    p = A[p]

print(p)

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
# -*- coding:utf-8 -*-

def dest_deleport(K, A):
    route = []
    now = 1
    num_step = 0
    while not now in route:
        route.append(now)
        dest = A[now - 1]
        num_step += 1
        if num_step == K: return dest
        now = dest
    loop_link = route[route.index(now):]
    len_loop = len(loop_link)
    return loop_link[(K-(len(route)-len_loop))%len_loop]

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

if __name__ == "__main__":
    main()

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))

c=[1]
i=0
for _ in range(N+1):
    if has_duplicates(c):
        break
    d=c[-1]-1
    c.append(A[d])
if K <=len(c):
    print(c[K])
else:
    p=c.pop()
    i=c.index(p)
    c_=c[i:]
    e=(K-i)%len(c_)
    print(c_[e])

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int,sys.stdin.readline().rstrip().split())
a = list(map(int,sys.stdin.readline().rstrip().split()))
dict={}
for i in range(1,n+1):
  dict[i] = a[i-1]
key = 1
for i in range(k):
    next = dict[key]
    key = next
print(key)

Submission status: Time Limit Exceeded

Solution code:
#import logging
#logging.basicConfig(level=logging.INFO)
#info = logging.getLogger(__name__).info

N,K = [int(x) for x in input().split()]
An = [int(x) for x in input().split()]

dupAn = list(An)
dupAn.append(1)
dupAn = {x for x in set(dupAn) if dupAn.count(x) > 1}

Ai = An[0]
loopi = 0
loopdict = {"1":[0]}
#info("dupAn: {}".format(dupAn))
while loopi <= K:
  #info("{}/{} {}".format(loopi,K,Ai))
  loopi += 1
  if Ai in dupAn:
    if loopdict.get(str(Ai)):
      loopdict[str(Ai)].append(loopi)
      break
    else:
      loopdict[str(Ai)] = [loopi]
  Ai = An[Ai-1]


def getA(An, K):
  #info("getA {} {}".format(An,K))
  Ai = An[0]
  for _ in range(K-1):
    Ai = An[Ai-1]
  return Ai

if loopi > K:
  print(getA(An, K))
else:
  #info("find loop index{}".format(loopdict[str(Ai)]))
  loopstart,loopend = loopdict[str(Ai)]
  k = (K - loopstart) % (loopend - loopstart)
  print(getA(An, loopstart+k))

Submission status: Time Limit Exceeded

Solution code:
import math

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

fk = k
crnt = 1
st = set()
wl = []
key = crnt
cy = 0
mg = 0

for i in range(n):
    if crnt in st:
        key = crnt
        cy = i - wl.index(crnt)
        mg = wl.index(crnt)
        break
    st.add(crnt)
    wl.append(crnt)
    crnt = li[crnt - 1]

k -= mg
if cy != 0:
    k %= cy
crnt = key
if n > k:
    k = fk
    crnt = 1
for i in range(k):
    crnt = li[crnt - 1]

print(crnt)

Submission status: Time Limit Exceeded

Solution code:
import logging
logging.basicConfig(level=logging.INFO)
info = logging.getLogger(__name__).info

N,K = [int(x) for x in input().split()]
An = [int(x) for x in input().split()]

Aline = [1]
info(An)

count = 1
Ai = An[0]
while not Ai in Aline and count < K:
  info("Ai:{}".format(Ai))
  count += 1
  Aline.append(Ai)
  Ai = An[Ai-1]

info("Ai:{}".format(Ai))
Aline.append(Ai)
loopi = Aline.index(Ai)
if loopi == len(Aline)-1:
  print(Aline[K])
else:
  step = len(Aline) - 1 - loopi
  info("Ai:{} and loop {} to {} {}steps".format(Ai,loopi, len(Aline)-1,step))

  info("Aloop: {}".format(Aline))
  k = (K - loopi) % (step)

  info("K:{} -> start:{} loop:{} * {}count".format(K,loopi, step, int((K-loopi) / step)))

  info("so we stop index:{}".format(loopi+k))
  print(Aline[loopi+k])

Submission status: Time Limit Exceeded

Solution code:
import logging
logging.basicConfig(level=logging.INFO)
info = logging.getLogger(__name__).info

N,K = [int(x) for x in input().split()]
An = [int(x) for x in input().split()]

Aline = [1]
info(An)

count = 1
Ai = An[0]
while not Ai in Aline:
  info("Ai:{}".format(Ai))
  count += 1
  Aline.append(Ai)
  Ai = An[Ai-1]

Aline.append(Ai)
loopi = Aline.index(Ai)
step = len(Aline) - 1 - loopi
info("Ai:{} and loop {} to {} {}steps".format(Ai,loopi, len(Aline)-1,step))

info("Aloop: {}".format(Aline))
k = (K - loopi) % (step)

info("K:{} -> start:{} loop:{} * {}count".format(K,loopi, step, int((K-loopi) / step)))

if loopi <= K:
  info("so we stop index:{}".format(loopi+k))
  print(Aline[loopi+k])
else:
  info("so we stop index:{}".format(K))
  print(Aline[K])