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
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N, K = MI()
    # A = LI1()

    D = [[0] * N for _ in range(int(log2(K))+1)]
    D[0] = LI1()
    
    for i in range(1, int(log2(K))+1):
        for j in range(N):
            tmp = D[i-1][j]
            D[i][j] = D[i-1][tmp]
    # print(D)
    
    v = 0
    while K > 0:
        tmp = int(log2(K))
        K = K - 2 ** tmp
        v = D[tmp][v]
        # print(tmp, K, v)
    print(v+1)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

tere = {}
for i in range(n):
    tere[i+1] = a[i]

mati = [1]
tugi = 1
for i in range(1, k+1):
    if tere[tugi] not in mati:
        mati.append(tere[tugi])
    else:
        mati.append(tere[tugi])
        break
    tugi = tere[tugi]
else:
    print(tugi)
    exit()


cnta = len(mati)-1
i = mati.index(mati[-1]) + 1
cntroop = cnta - i + 1
roop = mati[i:]

print(roop[(k-cnta)%cntroop-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

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

graph = {}
count = 1
for value in input().split():
    graph[count] = int(value)
    count += 1

queue = deque()
queue.append(1)
now_pos = 1
start = 0

for i in range(N + 1):
    next_pos = graph[now_pos]
    if not next_pos in queue:
        queue.append(next_pos)
        now_pos = next_pos

    # 循環した
    else:
        start = next_pos
        break

if K <= N:
    print(queue[K])
    sys.exit()

before_len = queue.index(start)
roop = len(queue) - before_len

print(queue[before_len + (K - before_len) % roop])

Submission status: Time Limit Exceeded

Solution code:
import sys

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

graph = {}
count = 1
for value in input().split():
    graph[count] = int(value)
    count += 1

queue = [1]
now_pos = 1
start = 0

for i in range(N + 1):
    next_pos = graph[now_pos]
    if not next_pos in queue:
        queue.append(next_pos)
        now_pos = next_pos

    # 循環した
    else:
        start = next_pos
        break

if K <= N:
    print(queue[K])
    sys.exit()

before_len = len(queue[:queue.index(start)])
roop = queue[queue.index(start):]

print(roop[(K - before_len) % len(roop)])

Submission status: Time Limit Exceeded

Solution code:
import sys

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

graph = {}
count = 1
for value in input().split():
    graph[count] = int(value)
    count += 1

queue = [1]
now_pos = 1
start = 0

for i in range(K + 1):
    next_pos = graph[now_pos]
    if not next_pos in queue:
        queue.append(next_pos)
        now_pos = next_pos

    # 循環した
    else:
        start = next_pos
        break

if K < N:
    print(queue[K])
    sys.exit()

before_len = len(queue[:queue.index(start)])
roop = queue[queue.index(start):]

print(roop[(K - before_len) % len(roop)])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [1]
B_append = B.append
a = 0
i = 0
while a == 0:
  i = A[i] - 1
  B_set = set(B)
  if (i + 1) in B_set:
    b = B.index(i + 1)
    a = 1
    break
  else:
    B_append(i + 1)
d = len(B) - b 
if K < b:
  ans = B[K]
else:
  ans = B[b + (K - b) % d]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [1]
B_append = B.append
a = 0
i = 0
while a == 0:
  i = A[i] - 1
  B_set = set(B)
  if (i + 1) in B_set:
    b = B.index(i + 1)
    C = B[:b]
    D = B[b:]
    a = 1
    break
  else:
    B_append(i + 1)
  
c = len(C)
d = len(D)
if K < c:
  ans = C[K]
else:
  ans = D[(K - c) % d]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [1]
B_append = B.append
a = 0
i = 0
while a == 0:
  i = A[i] - 1
  if (i + 1) in B:
    b = B.index(i + 1)
    C = B[:b]
    D = B[b:]
    a = 1
    break
  else:
    B_append(i + 1)
  
c = len(C)
d = len(D)
if K < c:
  ans = C[K]
else:
  ans = D[(K - c) % d]
print(ans)

Submission status: Time Limit Exceeded

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

B =[1]
for i in range(N):
    b = A[B[i]-1]
    B.append(b)
#print(B)
for j in range(N):
    for k in range(j+1,N):
        if B[j] == B[k] :
            #print(j,k)
            C=B[j:k]
            #print(C)
            c = (K - j)%(k-j)
            print(C[c])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(lambda x:int(x)-1,input().split()))
town=[0]
i=0
while True:
  idx=town[-1]
  if a[idx] in town:
    s=a[idx]
    i+=1
    break
  else:
    i+=1
    town.append(a[idx])
if i!=n:
  idp=town.index(s)
  chain=len(town[:idp])
  cycle=len(town[idp:])
  if k<=chain:
    print(town[k]+1)
  else:
    p=(k-chain)%cycle + chain
    print(town[p]+1)
else:
  print(town[k%n]+1)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(lambda x:int(x)-1,input().split()))
town=[0]
s=0
while True:
  idx=town[-1]
  if a[idx] in town:
    s=a[idx]
    break
  else:
    town.append(a[idx])

idp=town.index(s)
chain=len(town[:idp])
cycle=len(town[idp:])
if k<=chain:
  print(town[k]+1)
else:
  p=(k-chain)%cycle + chain
  print(town[p]+1)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
d = {}
p = 0
A = list(map(int, input().split()))

for i in range(1, N+1):
    d[i] = A[i-1]
i = 1
for j in range(K):
    position = d[i]
    p = position
    i = d[i]

print(p)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
l1=[a[0]]
l2=[]
def al(num):
    l1.append(num)
def n1(num):
    for j in range(num):
        if l1[j]==num1:
            break
    return j
def n2(num5):
    return num5 in l1
for i in range(n):
    num1=a[l1[-1]-1]
    str=n2(num1)
    if str==True:
        break
    else:
        al(num1)
num=n1(len(l1))
l2=l1[num:]
l1=l1[:num]
num1=len(l1)
num2=len(l2)
if k<=num1:
    print(l1[k-1])
else:
    num3=(k-num1)%num2
    print(l2[num3-1])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
l1=[a[0]]
l2=[]
def al(num):
    l1.append(num)
for i in range(n):
    num1=a[l1[-1]-1]
    str=num1 in l1
    if str==True:
        for j in range(len(l1)):
            if l1[j]==num1:
                break
        l2=l1[j:]
        l1=l1[:j]
        break
    else:
        al(num1)
num1=len(l1)
num2=len(l2)
if k<=num1:
    print(l1[k-1])
else:
    num3=(k-num1)%num2
    print(l2[num3-1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
W = []
for _ in range(n):
  W.append([0 for _ in range(n)])

root_list = list(map(int, input().split()))
for i, terminal in enumerate(root_list):
  W[i][terminal-1] = 1
  
#print(W)
place = 0
visited_list = []

while True:
  visited_list.append(place)
  place = W[place].index(1)
  #print(place)
  if place in visited_list:
    break
#print(visited_list)

roop_start = visited_list.index(place)
roop_list = visited_list[roop_start:]
roops = k - roop_start
print(roop_list[roops%len(roop_list)]+1)

Submission status: Time Limit Exceeded

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

while place not in was:
  if cnt < K:
    was.append(place)
    place = A[place-1]
    cnt += 1
  else:
    print(place)
    break;
else:
  loop = cnt - was.index(place)
  num = (K-cnt) % loop + was.index(place)
  print(was[num])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
 
town_list = [1]
last_town = 1
to_town = a[last_town-1]
while to_town not in town_list:
    last_town = a[last_town-1]
    town_list.append(last_town)
    to_town = a[last_town-1]
    
for i in range(N):
    if town_list[i] == to_town:
        roop_start = i
        break
 
if K <= len(town_list)-1:
    print(town_list[K])
else:
    K = K - len(town_list[:roop_start])
    K = K % len(town_list[roop_start:])
    print(town_list[roop_start:][K])

Submission status: Time Limit Exceeded

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

town_list = [1]
last_town = 1
to_town = a[last_town-1]
while to_town not in town_list:
    last_town = a[last_town-1]
    town_list.append(last_town)
    to_town = a[last_town-1]
    
for i in range(N):
    if town_list[i] == to_town:
        roop_start = i
        break

if K <= len(town_list)-1:
    print(town_list[K])
else:
    K = K - len(town_list[:roop_start])
    K = K % len(town_list[roop_start:])
    print(town_list[roop_start:][K])

Submission status: Time Limit Exceeded

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

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

num = 0

ans = 0

for x in range(k):
    ans = A[num]
    num = A.index(A[ans-1])

print (ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
d={i+1:A[i] for i in range(N)}
next_key=1
S=[1]
for i in range(1,N+1):
    next_key=d[next_key]
    if next_key in S:
        r_start=S.index(next_key)#繰り返し開始点のインデックス
        r=S[r_start:]
        r_before=S[:r_start]#繰り返し区間前までのS
        break
    else:
        S.append(next_key)
if K<len(r_before)-1:#繰り返し区間前で終わる場合
    print(r_before[K])
else:
    print(r[(K-len(r_before))%len(r)])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
def teleport(a,i):
    return a[i-1]
j = 0
position = 1
while j < k:
    position = teleport(a,position)
    j += 1
print(position)

Submission status: Time Limit Exceeded

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

now = 0
l[now] = 1
count = 0

while count < K:
    count += 1
    now = A[now]-1
    if l[now] == 0:
        l[now] = 1
    else:
        break

if count == K:
    print(now + 1)
else:
    for i in range(K - count):
        now = A[now] - 1
    print(now + 1)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
B=[0]
start = -1
for i in range(n):
  B+=[A[B[i]]-1]
  for j in range(i+1):
    if B[j] == B[i+1]:
      start=j
      loop=(i+1)-j
      break
  if(start!=-1):
    break
if(k<=start):
  print(B[k]+1)
else:
  print(B[(k-start)%loop + start]+1)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
B=[0]
for i in range(n):
  B+=[A[B[i]]-1]
  for j in range(i+1):
    if B[j] == B[i+1]:
      start=j
      loop=(i+1)-j
      break
if(k<=start):
  print(B[k]+1)
else:
  print(B[(k-start)%loop + start]+1)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split())) 
b = 0
c = [0]
for i in range(k):
  b = a[b]-1
  if b in c:
    d = c.index(b)
    e = i-d+1
    k = k - len(c)+e
    c = c[-e:]
    print(c[k%e]+1)
    exit(0)
  else:
    c.append(b)
print(b+1)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
visited=[]
x=0
now=1
next_point=a[now-1]
for cnt in range(min(n,k)):
    now=next_point
    next_point=a[now-1]
    if now in visited:
        x=visited.index(now)
        break
    else:
        visited.append(now)
new_visited=visited[x:]
k-=len(visited)-len(new_visited)

#print(visited)
#print(new_visited)

print(new_visited[k%len(new_visited)-1])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
visited=[]
x=0
now=1
next_point=a[now-1]
for cnt in range(k):
    now=next_point
    next_point=a[now-1]
    if now in visited:
        x=visited.index(now)
        break
    else:
        visited.append(now)
new_visited=visited[x:]
k-=len(visited)-len(new_visited)

#print(visited)
#print(new_visited)
print(new_visited[k%len(new_visited)-1])

Submission status: Time Limit Exceeded

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

move=[]
for i in range(0,N):
    move.append([])
    A[i]-=1
    move[i].append(A[i])


for j in range(1,64):
    for i in range(0,N):
        move[i].append(move[move[i][j-1]][j-1])
town=0
for i in range(0,64):
    if K%2==1:
        town=move[town][i]
    K//=2

print(town+1)

Submission status: Time Limit Exceeded

Solution code:
import math
def fact(n):
    ans = 1
    for i in range(2, n+1):
        ans*= i
    return ans
def comb(n, c):
    return fact(n)//(fact(n-c)*c)

n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt=  0
i = 1
cycle = ['1']

for c in range(n):
    i = a[i-1]
    if(i in cycle):
        break
    else:
        cycle.append(i)

ind = cycle.index(i)
k-= ind
rcycle = cycle[ind:]
if(k <= 0):
    print(cycle[k+ind])
else:
    now = (k+1)%len(rcycle)
    print(rcycle[now-1])

Submission status: Time Limit Exceeded

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

now=1
flg = 0
path=[1]
for i in range(k):
    now = a[now-1]
    if now in path:
        flg = -1
        path.append(now)
        break
    path.append(now)

if flg == 0:
    print(now)
    exit()

x1 = path.index(now)
x2 = len(path)-1
x3 = (k-x1)%(x2-x1)
print(path[x1+x3])

Submission status: Time Limit Exceeded

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

flg = 0
now=1
path=[1]
while flg < k:
    flg = flg+1
    now = a[now-1]
    if now in path:
        flg=k+1
    path.append(now)

if flg == k:
    print(now)
    exit()

x1 = path.index(now)
x2 = len(path)-1
x3 = (k-x1)%(x2-x1)
print(path[x1+x3])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    to = [[None]*n for _ in range(60)]
    double = 1
    i = 0
    to[0] = a[:]
    for i in range(1, 60):
        for j in range(n):
            to[i][j] = to[i-1][to[i-1][j]-1]
    num = 2**59
    p = 1
    for i in range(59, -1, -1):
        if k >= num:
            k -= num
            p = to[i][p-1]
        num //= 2
    print(p)
        
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

root = [1]
pos, loop_start = 0, 0
for i in range(n):
    pos = A[root[i] - 1]
    if i + 1 == k:
        break
    if pos not in root:
        root.append(pos)
    else:
        loop_start = pos
        break

if loop_start == 0:
    print(pos)
else:
    idx = root.index(loop_start)
    one_way, loop = root[: idx], root[idx: ]
    print(loop[(k - len(one_way)) % len(loop)])

Submission status: Time Limit Exceeded

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

root = [1]
pos, loop_start = 0, 0
for i in range(n):
    pos = A[root[i] - 1]
    if i + 1 == k:
        break
    if pos not in root:
        root.append(pos)
    else:
        loop_start = pos
        break

if loop_start == 0:
    print(pos)
else:
    idx = root.index(loop_start)
    one_way, loop = root[: idx], root[idx: ]
    print(loop[(k - len(one_way)) % len(loop)])

Submission status: Time Limit Exceeded

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

root = [1]
loop_start = 0
for i in range(n):
    pos = A[root[i] - 1]
    if pos not in root:
        root.append(pos)
    else:
        loop_start = pos
        break

idx = root.index(loop_start)
one_way, loop = root[: idx], root[idx: ]

print(one_way[k] if k < len(one_way) else loop[(k - len(one_way)) % len(loop)])

Submission status: Time Limit Exceeded

Solution code:
N,K = list(map(int,input().split()))
a = list(map(int,input().split()))
c = 1
s="1"
mod = 0
d = 0
for i in range(K):
	c =a[c-1]

print(c)

Submission status: Time Limit Exceeded

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

i = 0
telp = [1]
while True:
    if A[i] not in telp:
        telp.append(A[i])
        i = A[i] - 1
    else:
        telp.append(A[i])
        break

for i in range(len(telp)):
    if telp[i] != telp[-1]:
        K -= 1
        if K == 0:
            print(telp[i + 1])
            break
    else:
        roop = telp[i + 1:]
        ans = (K % len(roop)) - 1
        print(roop[ans])
        break

Submission status: Time Limit Exceeded

Solution code:
[n, k], [*a] = [[*map(int, t.split())] for t in open(0)]
ans = 1
for _ in range(k):
    ans = a[ans - 1]
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#Doubling O(log k)
def main():
  ## IMPORT MODULE
  #import sys

  #sys.setrecursionlimit(100000)
  #input=lambda :sys.stdin.readline().rstrip()

  #f_inf=float("inf")
  #MOD=10**9+7
  
  if 'get_ipython' in globals(): 
    ## SAMPLE INPUT
    n, k = 4, 5
    A = [3, 2, 4, 1]

  else:
    ##INPUT 
    #n = input()
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

  ## SUBMITION CODES HERE
  D = 60 # 10^18 is 60 digits, so we'll see to the 59th power of 2.
  MAX_N = 200005 #Namber of nodes
  to = [[0 for _ in range(MAX_N)] for _ in range(D)]

  # to[i][j]:nodes to 2^i away from j  
  for i in range(n):
    to[0][i] = A[i]
    to[0][i] -= 1

  # Doubling matrix
  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 # Look go to 2^i
    if l <= k:
        v = to[i][v]
        k -= l

  print(v+1)
    
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

route =[1]
cur = 1
for i in range(k):
    goto = a[cur - 1]
    if goto in route:
        pre_goto = route.index(goto)
        dif = len(route) - pre_goto
        rest_step = (k - pre_goto) % dif
        print(route[pre_goto + rest_step])
        break
    route.append(goto)
    cur = goto
else:
    print(route[k])

Submission status: Time Limit Exceeded

Solution code:

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

town_loop = [1]

for i in range(k):
    next_town = alist[town_loop[i]-1]

    try:
        loop_start = town_loop.index(next_town)
        break
    except ValueError:
        town_loop.append(next_town)

if len(town_loop) == k+1:
    print(town_loop[k])
else:
    o = len(town_loop) - loop_start
    print(town_loop[((k-loop_start) % o) + loop_start])

Submission status: Time Limit Exceeded

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

a = [int(x)-1 for x in input().split()]

v = []
b = 0

for i in range(n):
    if b not in v:
        v.append(b)
        b = a[b]
    else:
        stop = v.index(b)
        j = i
        break


if k>j:
    r = (k-stop)%(j-stop)
    print(v[stop+r]+1)
else:
    print(v[k]+1)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [1]
c = a[1]
d = 0
e=1
length = 0
first = 0
ans = 0


while c not in b:
    b += [c]
    c = a[c]
    d = c
    e+=1

if d != 0:
    length = e - b.index(d)
    first = b.index(d)
if k <= first:
    ans = b[k]
elif d == 0:
    ans = 1
else:
    ans = b[(k - first) % length + first]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [1]
c = a[1]
d = 0
length = 0
first = 0
ans = 0

while c not in b:
    b += [c]
    c = a[c]
    d = c
    
if d != 0:
    length = len(b) - b.index(d)
    first = b.index(d)
if k <= first:
    ans = b[k]
elif d == 0:
    ans = 1
else:
    ans = b[(k - first) % length + first]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def Destination(N, K, DestinationList, TravelHistory = [1] ):
    """
    for Num in range(N):
        Destination = DestinationList[ TravelHistory[-1]-1]
        TravelHistory.append(Destination)
        if(Destination in TravelHistory[:-1]):
            Pos = TravelHistory[:-1].index(Destination)
            Period = len(TravelHistory)-Pos-1
            break;
    """
    Pos_First = 0
    Pos_Second = 0
    Min = min(N, K)
    for Num in range(Min):
        Destination = DestinationList[ TravelHistory[-1]-1]
        """
        if(Destination in TravelHistory):
            Pos_First = TravelHistory.index(Destination)
            Pos_Second = len(TravelHistory)
            break
        """
        TravelHistory.append(Destination)
    if(K <= N ):
        return TravelHistory[K]
    for Num in range(N):
        if(TravelHistory[Num] in TravelHistory[Num+1:]):
            Pos_First = Num
            Pos_Second = TravelHistory[Num+1:].index( TravelHistory[Num] ) + Num+1

            break
    Period = Pos_Second-Pos_First
    #print(Pos_First, Pos_Second, Period)



    Times_K = (K-Pos_First)%Period
    Pos_K = TravelHistory[Pos_First+Times_K]
    return Pos_K


if(__name__ == '__main__'):
    In = input().split()

    N= int(In[0].strip())
    K= int(In[1].strip())

    DestinationList = []
    In = input().split()
    for Str in In:
        DestinationList.append( int(Str.strip()) ) # [M] -> value
    print(Destination(N, K, DestinationList) )

Submission status: Time Limit Exceeded

Solution code:
import sys

def Destination(N, K, DestinationList, TravelHistory = [1] ):
    """
    for Num in range(N):
        Destination = DestinationList[ TravelHistory[-1]-1]
        TravelHistory.append(Destination)
        if(Destination in TravelHistory[:-1]):
            Pos = TravelHistory[:-1].index(Destination)
            Period = len(TravelHistory)-Pos-1
            break;
    """
    Pos_First = 0
    Pos_Second = 0
    for Num in range(N+1):
        Destination = DestinationList[ TravelHistory[-1]-1]
        if(Destination in TravelHistory):
            Pos_First = TravelHistory.index(Destination)
            Pos_Second = len(TravelHistory)
            break
        TravelHistory.append(Destination)

    Period = Pos_Second-Pos_First

    if(K <= Pos_First ):
        return TravelHistory[K]

    Times_K = (K-Pos_First)%Period
    Pos_K = TravelHistory[Pos_First+Times_K]
    return Pos_K


if(__name__ == '__main__'):
    In = input().split()

    N= int(In[0].strip())
    K= int(In[1].strip())

    DestinationList = []
    In = input().split()
    for Str in In:
        DestinationList.append( int(Str.strip()) ) # [M] -> value
    print(Destination(N, K, DestinationList) )

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

#【ループ回数】200000
for i in range(1,len(A)):
    now_city=A[now_city]
    #【ループ回数】B 内で 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())
A=list(map(int,input().split()))
now=1
count=0
a=0
l=[1]
b=0
c=0
while a==0and count<K:
    now=A[now-1]
    count+=1
    if now in l:
        a=1
    else:
        l.append(now)
        
b=l.index(now)
c=count-b
if count==K:
    print(now)
else:
    n= ((K-b)%c)
    print(l[b+n])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
now=1
count=0
a=0
l=[1]
b=0
c=0
while a==0and count<K:
    now=A[now-1]
    count+=1
    if now in l:
        a=1
    else:
        l.append(now)
        
b=l.index(now)
c=count-b
if count==K:
    print(now)
else:
    n= ((K-b)%c)
    ncount=0
    while ncount <n:
        now=A[now-1]
        ncount+=1
    print(now)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
now=1
count=0
a=0
l=[1]
b=0
c=0
while a==0and count<K:
    now=A[now-1]
    count+=1
    if now in l:
        b=l.index(now)
        c=count-b
        a=1
    else:
        l.append(now)
if count==K:
    print(now)
else:
    n=int((K-2)/c)
    ncount=0
    while ncount <n:
        now=A[now-1]
        count+=1
    print(now)

Submission status: Time Limit Exceeded

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

l = [[0]*N for _ in range(60)]

for i in range(60):
    for j in range(N):
        if i == 0:
            l[i][j] = A[j] - 1
        else:
            tmp = l[i-1][j]
            l[i][j] =l[i-1][tmp]
ans = -1
for i in range(59, -1, -1):
    if K >> i & 1:
        if ans == -1:
            ans = l[i][0]
        else:
            ans = l[i][ans]
print(ans+1)

Submission status: Time Limit Exceeded

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

l = [[0]*N for _ in range(100)]

for i in range(100):
    for j in range(N):
        if i == 0:
            l[i][j] = A[j] - 1
        else:
            tmp = l[i-1][j]
            l[i][j] =l[i-1][tmp]
ans = -1
for i in range(99, -1, -1):
    if K >> i & 1:
        if ans == -1:
            ans = l[i][0]
        else:
            ans = l[i][ans]
print(ans+1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
kiseki=[]
u=1
kiseki.append(1)
for i in l:
  u=l[u-1]
  if kiseki.count(u)==0:
    kiseki.append(u)
  else:
    kiseki.append(u)
    break
kuri=kiseki[kiseki.index(u):len(kiseki)-1]
if k<=len(kiseki)-(len(kuri)+1):
  print(kiseki[k])
else:
  K=k-(len(kiseki)-(len(kuri)+1))
  amari=K%len(kuri)
  print(kuri[amari])

Submission status: Time Limit Exceeded

Solution code:
N, K = (int(x) for x in input().split())
trip = input().split()

now = 1

for k in range(K):
  now = int(trip[now-1])
   
print(now)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
ls_pass = [0]+list(map(int,input().split()))
a=1
b=0
c=0
d=0
ls_past=[1]
ls_cicle=[]
for i in range(1,N*3):
  b=a
  a=ls_pass[a]
  if b==a:
    print(a)
    break
  elif a in ls_past:
    if c==0:
      c=i
      d=a
      ls_cicle.append(d)
      continue
    elif a==d:
      print(ls_cicle[(K-c)%(i-c)])
      break
    else:
      ls_cicle.append(a)
  elif i==K:
    print(a)
    break  
  else:
    ls_past.append(a)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
ls_pass = list(map(int,input().split()))
ls_pass.insert(0,0)
a=1
b=0
ls_past=[1]
for i in range(1,N+1):
  b=a
  a=ls_pass[a]
  if b==a:
    print(a)
    break
  elif a in ls_past:
    c=ls_past.index(a)
    ls_cicle=ls_past[c:i]
    print(ls_cicle[(K-i)%(i-c)])
    break
  elif i==K:
    print(a)
    break
  else:
    ls_past.append(a)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
port = list(map(int, input().split()))
visited = [1]
current = 1

t = k

while port[current-1] not in visited and t > 0:
    visited.append(port[current-1])
    current = port[current-1]
    t -= 1

if t > 0:
    s = visited.index(port[current-1])
    bubun = visited[s:]
    g = (k-s) % len(bubun)
    print(bubun[g])
else:
    print(current)

Submission status: Time Limit Exceeded

Solution code:
#D
N,K = map(int,input().split())
A = tuple(map(int,input().split()))
genzai = 1
kiseki = []
for i in range(K):
    kiseki.append(genzai)
    genzai = A[genzai-1]
    if genzai in kiseki:
        s = kiseki.index(genzai)
        loop = len(kiseki)-s
        amari = (K-s)%loop
        genzai = kiseki[s+amari] 
        break
    else:
        pass
print(genzai)

Submission status: Time Limit Exceeded

Solution code:
#D
N,K = map(int,input().split())
A = list(map(int,input().split()))
genzai = 1
kiseki = []
for i in range(K):
    kiseki.append(genzai)
    genzai = A[genzai-1]
    if genzai in kiseki:
        s = kiseki.index(genzai)
        loop = len(kiseki)-s
        amari = (K-s)%loop
        genzai = kiseki[s+amari] 
        break
    else:
        pass
print(genzai)

Submission status: Time Limit Exceeded

Solution code:
#D
N,K = map(int,input().split())
A = list(map(int,input().split()))
genzai = 1
kiseki = []
for i in range(K):
    kiseki.append(genzai)
    genzai = A[genzai-1]
    try:
        s = kiseki.index(genzai)
        loop = len(kiseki)-s
        amari = (K-s)%loop
        genzai = kiseki[s+amari] 
        break
    except:
        pass
print(genzai)

Submission status: Time Limit Exceeded

Solution code:
#abc167c
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))

root = [1]
for i in range(10**100):
    next_num = a[root[-1]]
    root.append(next_num)

if k < n+1:
    print(root[k])
    exit()

loop_end = n 
loop_start = n-1
while(root[loop_start]!=root[loop_end]):
    loop_start -= 1
period = loop_end - loop_start
k%=period
while k < n:
    k += period
print(root[k])