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 math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=qb
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1


n,k = readInts()
a = readInts()

now = [1]
l = 1

while now.count(l)<2:
	l = a[l-1]
	now.append(l)

zen = now.index(now[-1])
kou = len(now)-zen

if k<zen:
	print(now[k])
else:
	x = (k-zen)%(kou-1)
	print(now[zen:][x])

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

init=0
loop=N
C=0
Done=[0 for _ in range(N)]
Done[0]=1
Order=[0]

while max(Done)<2 and len(Order)<N:
    C=A[C]-1
    Done[C]+=1
    if Done[C]==2:
        init=Order.index(C)
        loop=len(Order)-init
        break
    Order.append(C)

if K<=init:
    print(Order[K]+1)
else:
    print(1+Order[(K-init)%loop+init])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
D = K.bit_length()
to = [[0] * D for _ in range(N)]

for i, a in enumerate(map(int, input().split())):
    to[i][0] = a - 1

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

v = 0
for i in reversed(range(D)):
    x = 1 << i
    if x <= K:
        v = to[v][i]
        K -= x

print(v + 1)

Submission status: Time Limit Exceeded

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


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


p=1
h=[]
go=0


for i in range(1,k+1):
    
    
    
    

    h.append(p)
    p=a[p-1]
    
    if p in h:
        j=h.index(p)
        amari=(k-i-1)%(i-j)
        p=h[j+amari]
        go=1
        break

if go==1:
    p=a[p-1]

print(p)

Submission status: Time Limit Exceeded

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

pos = 1
seen = [1]
while True:
	if A[pos] in seen:
		seen.append(A[pos])
		break
	seen.append(A[pos])
	pos = A[pos]

length = len(seen)

initial, loop = 0, 0
for i in range(length):
	if seen[i] == seen[-1]:
		initial = i
		loop = length - 1 - initial
		break

if k < length:
	print(seen[k])
	exit()

kk = (k - initial) % loop
print(seen[initial + kk])

Submission status: Time Limit Exceeded

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

visited = [0]
flag = False
loopStart = 0
loopCycle = 0
currentTown = 0

for i in range(n):
    currentTown = a[visited[-1]]-1
    if currentTown in visited:
        flag = True
        loopStart = visited.index(currentTown)
        loopCycle = i + 1 - loopStart
        break
    if i == k - 1:
        print(currentTown+1)
        break

    visited.append(currentTown)

if flag:
    print(visited[loopStart + (k - loopStart) % loopCycle]+1)

Submission status: Time Limit Exceeded

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

def has_duplicates(seq):
    return len(seq) != len(set(seq))

visited = [0]
flag = False
loopStart = 0
loopCycle = 0

for i in range(n):
    visited.append(a[visited[-1]]-1)
    if has_duplicates(visited):
        flag = True
        loopStart = visited.index(visited[-1])
        loopCycle = len(visited) - 1 - loopStart
        break
    if i == k - 1:
        print(visited[i+1]+1)
        break

if flag:
    print(visited[loopStart + (k - loopStart) % loopCycle]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()
A = [x-1 for x in A]
D = 60
to = [[0]*N for _ in range(D)]
to[0] = A.copy()

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

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

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = [0] + list(map(int,input().split())) #1_indexed
tele = [1]
appear = []
while True:
    next_number = a[tele[len(tele)-1]]
    if not next_number in appear:
        tele.append(next_number)
        appear.append(next_number)
    else:
        repeat = tele.index(next_number)
        tele_1 = tele[:repeat]
        tele_2 = tele[repeat:]
        break

if k < len(tele_1):
    print(tele_1[k])
else:
    k_new = (k-len(tele_1)+1) % len(tele_2)
    print(tele_2[k_new-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, k = map(int, input().split())
A = [0] + list(map(int, input().split()))
def f(i):
  if i == 1:
    return A
  L = [-1]*(n+1)
  if i & 1:
    F = f(i-1)
    for j in range(n+1):
      L[j] = A[F[j]]
  else:
    F = f(i//2)
    for j in range(n+1):
      L[j] = F[F[j]]
  return L
F = f(k)
ans = F[1]
print(ans)

Submission status: Time Limit Exceeded

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

    # ループしているところを見つける
    path = [1]
    current = 0
    looping = False
    loop_st = -1
    loop_ed = -1
    for i in range(n):
        _next = a[current]

        if _next in path:
            loop_st = path.index(_next)
            loop_ed = len(path)
            looping = True
            break
        path.append(_next)
        current = _next-1

    if looping:
        if loop_ed - 1 >= k:
            print(path[k])
        else:
            len_loop = loop_ed - loop_st
            z = (k - loop_st) % len_loop
            print(path[loop_st + z])
    else:
        print(path[k])


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

loop = deque([])
visited = set()
stack = deque([1])
loop_creating = False
last = 1

while True:
  if loop_creating and len(visited) == 0:
    break

  nex = a[last - 1]

  if nex in visited:
    visited.remove(nex)
    loop.append(nex)
    loop_creating = True
  elif nex in stack:
    visited.add(nex)
  else:
    stack.append(nex)

  last = nex

if k <= len(stack):
  print(stack[k])
elif k > len(stack):
  rem = k - len(stack)
  print(loop[rem % len(loop)])

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]*n for _ in range(bit)]
table[0] = A

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

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

Submission status: Time Limit Exceeded

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

# check
now_town = 1
next_town = A[now_town - 1]
cnt = 0

while cnt < K:
    now_town = next_town
    next_town = A[now_town - 1]
    cnt += 1

print(now_town)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math


def main():
    n, k = list(map(int, input().split()))
    A = list(map(int, stdin.readline().split()))
    roots = []
    roots.append(A)
    maxLoop = math.ceil(math.log(k)/math.log(2))
    for _ in range(1, maxLoop+1):
        roots_tmp = [None] * n
        for j in range(n):
            roots_tmp[j] = roots[-1][roots[-1][j]-1]
        roots.append(roots_tmp)

    position = 1
    for i in range(maxLoop+1):
        if k & (1 << (maxLoop-i)):
            position = roots[-1-i][position-1]
    print(position)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))

def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,K = MI()
A = [0]+LI()
ans_l = [1]
next = A[1]
while next not in ans_l:
    ans_l.append(next)
    next = A[next]
idx = ans_l.index(next)
repeat = ans_l[idx:]
if K<idx:
    print(ans_l[K])
else:
    print(repeat[(K-idx)%len(repeat)])

Submission status: Time Limit Exceeded

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

def main():
  N, K = map(int, readline().split())
  A = list(map(int, readline().split()))
 
  rs = 0
  p = -1
  r = []
  d = 1
  if N > K:
    for i in range(K+1):
      r.append(d)
      d = A[d - 1]
  else:
    for i in range(N+1):
      r.append(d)
      d = A[d - 1]
      for j in range(len(r)):
        if r[j] == d:
          rs = j
          p = i - j + 1
          break
  if p == -1:
    print(r[-1])
  else:
    print(r[rs+(K-rs)%p])

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
dp = [[None]*(n+1) for i in range(64)]
for i in range(1, n+1):
    dp[0][i] = a[i]
for i in range(63):
    for j in range(1, n+1):
        dp[i+1][j] = dp[i][dp[i][j]]

k = format(k, "064b")
now = 1
for i in range(64):
    if k[i] == "1":
        now = dp[~i][now]

print(now)

Submission status: Time Limit Exceeded

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

B = [1]
i = 0
count = 0

while True:
  if A[i] in B:
    x = B.index(A[i])
    a = (K-x) % (len(B)-x)
    break
  else:
    B.append(A[i])
    i = A[i]-1
    count += 1
    
if count >= K:
  print(B[K])
  
else:
  print(B[a+x])

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


N, K = map(int, input().split())
k_bitlen = K.bit_length()
dp = [[0] * N for _ in range(k_bitlen + 1)]
dp[0] = list(map(lambda x: int(x) - 1, input().split()))

for k in range(k_bitlen):
    for i in range(N):
        dp[k + 1][i] = dp[k][dp[k][i]]
pos = 0
for k in range(k_bitlen):
    if K >> k & 1:
        pos = dp[k][pos]
print(pos + 1)

Submission status: Time Limit Exceeded

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

B = [1]
i = 0
count = 0

while True:
  if count == K:
    print(i+1)
    break
  elif A[i] in B:
    x = B.index(A[i])
    a = (K-x) % (len(B)-x)
    print(B[a+x])
    break
  else:
    B.append(A[i])
    i = A[i]-1
    count += 1

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
k_bitlen = K.bit_length()
dp = [[0] * N for _ in range(k_bitlen + 1)]
dp[0] = list(map(lambda x: int(x) - 1, input().split()))

for k in range(k_bitlen):
    for i in range(N):
        dp[k + 1][i] = dp[k][dp[k][i]]
pos = 0
for k in range(k_bitlen):
    if K >> k & 1:
        pos = dp[k][pos]
print(pos + 1)

Submission status: Time Limit Exceeded

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

def teleport(n):
    return a[n-1]

place = a[0]
for _ in range(k-1):
    place = teleport(place)
print(place)

Submission status: Time Limit Exceeded

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

MyList = [int(n) for n in MyList]

ANS = 0
visted = []
i = 0

def Myfunc(A):
    return MyList[A] - 1

while True:
    ANS = Myfunc(ANS)
    if ANS in visted:
        beANS = (K-visted.index(ANS)) % (len(visted) - visted.index(ANS))
        del visted[:visted.index(ANS)]
        ANS = visted[beANS-1]
        print(ANS+1)
        break
    visted.append(ANS)
    i += 1
    if i == K:
        print(ANS+1)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():  
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = [a - 1 for a in A]
    X = K.bit_length()
    to = [[-1] * X for _ in range(N)]
    for i,a in enumerate(A):
        to[i][0] = a
    for i in range(X - 1):
        for j in range(N):
            to[j][i + 1] = to[to[j][i]][i]
    now = 0
    i = 0
    while K > 0:
        if K&1:
            now = to[now][i]
        i += 1
        K >>= 1
    print(now + 1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

to = [[0] * (n + 1) for _ in range(MAX)]

to[0] = a

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

v = 1
for i in range(MAX - 1, -1, -1):
    num = 1 << i
    if k >= num:
        v = to[i][v]
        k -= num

print(v)

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]
data_len = len(data)

for _ in range(data_len):
    d = data[d-1]
    if d in route:
        loop = route[route.index(d):]
        break
    else:
        route.append(d)
loop_len = len(loop)
if loop_len > 0:
    a = len(route) - 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:
n,k = [int(i) for i in input().split()]
data = [int(i) for i in input().split()]

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

while count < data_len:
    d = data[d-1]
    if d in route:
        loop = route[route.index(d):]
        break
    else:
        route.append(d)
    count += 1
if len(loop) > 0:
    loop_len = len(loop)
    a = len(route) - 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:
N,K = map(int, input().split())
A = list(map(int, input().split()))
p = 1
p_hist = []
p_hist_index = [-1] * (N+1)
while p not in p_hist:
    p_hist_index[p] = len(p_hist)
    p_hist.append(p)
    p = A[p-1]
end_loop = p_hist[-1]
end_loop_idx = p_hist_index[end_loop]
start_loop = A[end_loop - 1]
start_loop_idx = p_hist_index[start_loop]
if K < start_loop_idx:
    print(p_hist[K])
else:
    print(p_hist[(K-start_loop_idx)%(end_loop_idx-start_loop_idx+1)+start_loop_idx])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import functools
import math
import collections
import scipy
import fractions
import itertools
 
def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    now = 0
    hoge= []
    bit = 0
    piyo = 0
    huga = []
    for i in range(k):
        hoge.append(now)
        now = a[now]-1
        if now in hoge:
            huga = hoge[hoge.index(now):len(hoge)]
            piyo = hoge.index(now)
            bit = 1
            break
    if bit == 1:
        ans = huga[(k-piyo)%len(huga)]
        print(ans+1)
    else:
        now = 0
        for i in range(k):
            now = a[now]-1
        print(now+1)
    return 0
 
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

genzaichi=1
rireki=[]
houmon=[0]*(N+1)
flag=0

for i in range(1,K+1):
    genzaichi=A[genzaichi-1]
    if genzaichi not in rireki:
        houmon[genzaichi]=i
        rireki.append(genzaichi)
    else:
        roop_from=genzaichi
        x=houmon[roop_from]
        roop=i-x
        flag=1
        break

if flag==0:
    print(genzaichi)
else:
    genzaichi=roop_from
    K=(K-x)-((K-x)//roop)*roop
    for i in range(K):
        genzaichi=A[genzaichi-1]
    print(genzaichi)

Submission status: Time Limit Exceeded

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

genzaichi=1
rireki=[]
houmon=[0]*(N+1)
flag=0

for i in range(1,K+1):
    genzaichi=A[genzaichi-1]
    if genzaichi not in rireki:
        houmon[genzaichi]=i
        rireki.append(genzaichi)
    else:
        roop_from=genzaichi
        x=houmon[roop_from]
        roop=i-x
        flag=1
        break

genzaichi=1
if flag==1:
    genzaichi=roop_from
    K=(K-x)-((K-x)//roop)*roop

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

print(genzaichi)

Submission status: Time Limit Exceeded

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

genzaichi=1
rireki=[]
houmon=[0]*(N+1)
flag=0

for i in range(1,K+1):
    genzaichi=A[genzaichi-1]
    if genzaichi not in rireki:
        houmon[genzaichi]=i
        rireki.append(genzaichi)
    else:
        roop_from=genzaichi
        x=houmon[roop_from]
        roop=i-x
        flag=1
        break

genzaichi=1
if flag==1:
    K=K-(((K-x)//roop)-1)*roop

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

print(genzaichi)

Submission status: Time Limit Exceeded

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

"""
1からのループだけを考えれば良い
"""

i = A[0]
ok = True
R = [1]
seen = [0] * N
seen[0] = 1


while ok:
    seen[i-1] += 1
    R.append(i)
    i = A[i-1]
    if seen[i-1] == 1:
        ind = R.index(i)
        loop = R[ind:]
        remain = R[:ind]
        ok = False

L = len(loop)

if K < len(remain):
    print(remain[K])
else:
    print(loop[(K - len(remain)) % L])

Submission status: Time Limit Exceeded

Solution code:
# 4 5 (4 cities and 5 steps)
# 3 2 4 1

# 1 => 3
# 2 => 2
# 3 => 4
# 4 => 1

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

paths = {}

for i in range(N):
    paths[i+1] = A_i[i]

# print('paths:', paths)

# 6 5 2 5 3 2

state = 1
steps = 0
flag = False
known_states = {}

while steps < K:
    known_states[state] = steps

    state = paths[state]
    steps += 1

    # print(f'steps: {steps}, state: {state}')

    # if state in known_states and not flag:
    #     loop_steps = (steps - known_states[state])
    #     steps = K -  (K % loop_steps) - 1
    #     flag = True
        # print('loop detected')


print(state)

Submission status: Time Limit Exceeded

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

for i in range(k):
    once = a[foot[-1]]
 
    if once in set(foot):
        monu = foot.index(once)
        break
    foot.append(once)
 
if k < n+1:
    print(foot[k])
    exit()
 
 
foot = foot[monu:]
ros = len(foot)
ans = (k -monu)% ros
 
print(foot[ans])

Submission status: Time Limit Exceeded

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


x = deque([1])
point = 1
count = 0
while True:
  next_point = A[point-1]
  if next_point in x :
    x.append(next_point)
    break
  x.append(next_point)
  point = next_point
  
f = x.index(next_point)

if K <=f:
    print(x[K])
else :
    num = len(x) - f -1
    x = list(x)[f+1:]
    dic = {(n+1+f) %(num): i for n, i in enumerate(x)}
    print(dic[K%num])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, K= map(int, input().split())
A = { n+1:int(i) for n,i in enumerate(input().split())} 

x = deque([1])
point = 1
while True:
  next_point = A[point]
  if next_point in x :
    x.append(next_point)
    break
  x.append(next_point)
  point = next_point
f = x.index(x[-1])
if K <=f:
    print(x[K])
else :
    num = len(x) - f -1
    x = list(x)
    dic = {(n+1+f) %(num): i for n, i in enumerate(x[ f+1:])}
    print(dic[K%num])

Submission status: Time Limit Exceeded

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

order = []
ans = A[0] - 1
start = 0
stop = 0


for i in range(K):
    order.append(ans)
    if len(set(order)) != i+1:
        stop = i - 1
        start = order.index(ans)
        new = order[start:stop+1]
        break
    else:
        if i == K - 1:
            print(ans+1)
            exit()
        else:
            ans = A[ans] - 1


print(new[(K-start) % (stop-start+1)-1]+1)

Submission status: Time Limit Exceeded

Solution code:

[n,k] = [int(x) for x in input().split()]
data = [int(x) for x in input().split()]

# テレポート表を作る
te_list = [1,]
rep_start = None
rep_period = None
current_town = 1
while data[current_town - 1] not in te_list:
    te_list.append(data[current_town - 1])
    current_town = data[current_town - 1]

rep_start = te_list.index(data[current_town - 1])
rep_period = len(te_list) - rep_start

if k < rep_start :
    ans = te_list[k]
else:
    ans = te_list[(k - rep_start) % rep_period + rep_start]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
*A, = map(int, input().split())
A = [0] + A
DP = [[None for j in range(60)] for i in range(n + 1)]
for i in range(n + 1):
    DP[i][0] = A[i]
for j in range(1, 60):
    for i in range(n + 1):
        DP[i][j] = DP[DP[i][j - 1]][j - 1]
K = list(bin(k)[2:][::-1])
i = 1
for j, b in enumerate(K):
    if b == '1':
        i = DP[i][j]
print(i)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
*A, = map(int, input().split())
A = [0] + A
DP = [[None for j in range(100)] for i in range(n + 1)]
for i in range(n + 1):
    DP[i][0] = A[i]
for j in range(1, 100):
    for i in range(n + 1):
        DP[i][j] = DP[DP[i][j - 1]][j - 1]
K = list(bin(k)[2:][::-1])
i = 1
for j, b in enumerate(K):
    if b == '1':
        i = DP[i][j]
print(i)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
list1 = list(map(int,input().split()))
temp = list1[0]
for i in range(1,k):
    temp = list1[temp-1]

print(temp)

Submission status: Time Limit Exceeded

Solution code:
def zero_index(i: str) -> int:
  return int(i) - 1

n, k = map(int, input().split())
transition = list(map(zero_index, input().split()))
places = [0]
next_place = transition[0]
while next_place not in places:
  places.append(next_place)
  next_place = transition[next_place]
start = places.index(next_place)
period = len(places) - start
if k < start:
  t = k
else:
  t = (k - start) % period + start
print(places[t] + 1)

Submission status: Time Limit Exceeded

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

cnt = 1
i = a[0] - 1
memo = {1:i}
memo_value = [i]
i = a[i] - 1
while i not in memo_value:
    memo_value.append(i)
    cnt += 1
    memo[cnt] = i
    i = a[i] - 1

for value in memo_value:
    if value == i: # ループが始まった時のキーを取得　ここ
        ky = memo_value.index(value) + 1
        break

if k < ky:
    ans = memo[k]
else:
    kkk = (k-ky+1) % (cnt-ky+1) # 全数からループ構成数を割った余り
    if kkk == 0:
        ans = memo[cnt]
    else:
        ans = memo[ky-1+kkk]
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
N, K= map(int, input().split())
A = { n+1:int(i) for n,i in enumerate(input().split())}

x = [1]
point = 1
while True:
  next_point = A[point]
  if next_point in x :
    x.append(next_point)
    break
  x.append(next_point)
  point = next_point

#print(x)
f = x.index(x[-1])
if K <=f:
    print(x[K])
else :
    num = len(x) - f -1
    dic = {(n+1+f) %(num): i for n, i in enumerate(x[ f+1:])}
    print(dic[K%num])

Submission status: Time Limit Exceeded

Solution code:
import sys
s = sys.stdin.readlines()
N, K = map(int, s[0].split())
A = list(map(int, s[1].split()))
A.insert(0,0)
tmp = 1
for i in range(K):
    now = tmp
    next_town = A[tmp]
#    print(str(now) + "→" + str(next_town))
    tmp = next_town
print(next_town)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
D = 60
to = [None] * D
to[0] = [None] * N
for i, a in enumerate(map(int, input().split())):
    to[0][i] = a - 1
for t in range(1, D):
    to[t] = [None] * N
    for i in range(N):
        to[t][i] = to[t-1][to[t-1][i]]
v = 0
for i in reversed(range(D)):
    l = 1<<i
    if l <= K:
        v = to[i][v]
        K -= l
        if K <= 0:
            print(v + 1)
            exit()

Submission status: Time Limit Exceeded

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

for i in range(1, N+1):
	DP[0][i]=A[i]
for k in range(1, 61):
    for i in range(1, N+1):
        DP[k][i] = DP[k-1][DP[k-1][i]]

now = 1
for k in range(61):
	if (K>>k) & 1:
		now = DP[k][now]

print(now)

Submission status: Time Limit Exceeded

Solution code:
a,b=map(int, input().split())
c=list(map(int, input().split())) 
 
l = [1]
tmp = 1
s = 0
for i in range(b):
    l.append(c[tmp-1])
    tmp = c[tmp-1]
    if c[tmp-1] in l:
        s = c[tmp-1]
        t = len(l)+1
        break
    

#print(l)
if a > b:
    print(l[b])
    exit()

h = l.index(s) + 1

#print(s,h,t)
l2 = l[h-1:t-1]
#print(l2)
if s == 1:
    id = b % (t - 1)
    print(l2[id])
else:
    id = (b - h + 1) % (t - h)
    print(l2[id])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
list=[1]
for i in range(N):
    if A[list[i]-1] in list :
        num2=list.index(A[list[i]-1])
        break
    list.append(A[list[i]-1])

if num2==0:
    print(list[K%len(list)])
else:
    if  K<num2:
        print(list[K])
    else:
        num=((K-num2)%(len(list)-num2))
        print(list[num+num2])

Submission status: Time Limit Exceeded

Solution code:
import math

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

doubling_table = [list(map(lambda n: n - 1, list(map(int, input().split(" ")))))]
for i in range(0,int(math.log2(K))):
    doubling_table.append([doubling_table[i][doubling_table[i][j]] for j in range(0,N)])
#     next_table = [doubling_table[i][doubling_table[i][j]] for j in range(0,N)]
#     doubling_table.append(next_table)
# print(doubling_table)

city = 0
for i in range(int(math.log2(K)), -1, -1):
    if K >= 2 ** i:
        K, city = K - 2 ** i, doubling_table[i][city] 
#         city = doubling_table[i][city]
        
print(city + 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 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(int, input().split()))
 
t = 0
now = 1
footprint = [1]
 

while t < K:
  if A[now-1] not in footprint:
    footprint.append(A[now-1])
    now = A[now-1]
    t += 1
  else:
    s = footprint.index(A[now-1])
    l = t - s + 1
    e = (K-s) % l
    now = footprint[s+e]
    break
    
print(now)