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: Accepted

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

s = []
ord = [-1] * (n+1)

v = 1
while ord[v] == -1:
    ord[v] = len(s)
    s.append(v)
    v = a[v-1]

c = len(s) - ord[v]
l = ord[v]

ans = 0
if k < l:
    ans = s[k]
else:
    k -= l
    k %= c
    ans = s[l+k]
print(ans)

Submission status: Accepted

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

city = []
city.append(1)
cnt = [0] * (n + 1)
cnt[1] = 1

for i in range(1,n):
    next = a[city[i-1]-1]
    cnt[next] += 1
    if cnt[next] > 1:
        base = next
        break

    city.append(next)

start = city.index(base)
loop = len(city) - start

ans = (k - start) % loop

if k <= start:
    print(city[k])
else:
    city = city[start:]
    print(city[ans])

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = [0] + [int(i) for i in input().split()]

route = [1]
route_set = set()
start = 1
cnt = 0
while True:
  if cnt == K:
    print(route[-1])
    exit()
  elif A[start] in route_set:
    index = route.index(A[start])
    loop = len(route) - index
    break
  else:
    route.append(A[start])
    route_set.add(A[start])
    start = A[start]
    cnt += 1

K -= index
K = K % loop
print(route[index:][K])

Submission status: Accepted

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

index_map = {}

step = 0
next_index = 0
while 0 < k:
  k -= 1  
  next_index = dest[next_index] - 1

  if next_index in index_map:
    period = step - index_map[next_index]
    skip = k % period
    for j in range(0, skip):
      next_index = dest[next_index] - 1
    break

  index_map[next_index] = step
  step += 1

print(next_index + 1)

Submission status: Accepted

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
l = [0]
s = {0}

for i in range(K):
    nex = A[l[-1]]-1
    
    if nex in s:
        for i in range(len(l)):
            if l[i]==nex:
                mark = i
                break
        
        t = len(l)-mark
        print(l[mark+(K-mark)%t]+1)
        exit()
    
    l.append(nex)
    s.add(nex)

print(nex+1)

Submission status: Accepted

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

def go(i, step):
  prevI=i
  m=[0]*N
  cnt=0
  for s in range(step):
    if m[i]:
      period=m[prevI] - m[i] + 1
      return go(i, (step-s) % period)
    cnt+=1
    m[i]=cnt
    prevI=i
    i=A[i]-1
  return i

print(go(0,K)+1)

Submission status: Accepted

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

next=1
visited = [0]*n
visited2 = [0]*n
flg=0

for i in range(k):
    #print(visited)
    if i==k-1:
        result = next
    if visited[next-1]==0:
        visited[next-1]=1
        next = a[next-1]
    elif visited2[next-1]==1:
        # (k-i-1) : 残り回数
        remain = (k-i-1)%sum(visited2)
        next = a[next-1]
        flg=1
        break
    elif visited[next-1]==1:
        visited2[next-1]=1
        next = a[next-1]

        
if flg:
    for i in range(remain):
        next = a[next-1]
    result  = next


print(next)

Submission status: Accepted

Solution code:
N, K, *A = map(int, open(0).read().split()) 

f = [0]*N

l = 1
ff = 0
f[l-1] = K
while K > 0:
  l = A[l-1]
  K -= 1
  if f[l-1] != 0:
    K = K % (f[l-1]-K)
    break
  f[l-1] = K
#
while K > 0:
  l = A[l-1]
  K -= 1
#
print(l)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
 
visited = []
tf_visited = [0] * n
pos = 0
count = 0
 
while tf_visited[pos] == 0:
	visited.append(pos)
	tf_visited[pos] = 1
	pos = a[pos]-1
	count += 1
	if count >= k:
		print(pos+1)
		exit()
 
loop_start = visited.index(pos)
loop_length = len(visited)-loop_start
pos_t = (k-loop_start) % loop_length + loop_start
print(visited[pos_t]+1)

Submission status: Accepted

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

s = 1
place = [s]
first = set(place)

for i in range(1, k+1):
    s = a[s-1]
    if s in first:
        loops = place.index(s)
        loope = len(place)
        ans = loops + (k-loope) % (loope-loops)
        print(place[ans])
        exit()
    else:
        place.append(s)
        first.add(s)

print(s)

Submission status: Accepted

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

checker = [None for i in range(n)]
checker[0] = 0
num = 0
count = 0
flag = 0

# 同じ地点に2度目に到着する or k回移動するまで移動する
while flag==0 and count!=k:
    if checker[lst[num]-1]==None:
        checker[lst[num]-1]=count+1
        count+=1
        num = lst[num]-1
    else:
        flag = 1
        count+=1

# 同じ地点に2度目に到着した場合、残移動回数をループ1回の移動回数で割った余りのみを再度移動すれば良い
if flag==1:
    remaining = (k-checker[lst[num]-1])%(count-checker[lst[num]-1])
    num = lst[num]-1
    for i in range(remaining):
        num = lst[num]-1

print(num+1)

Submission status: Accepted

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

checker = [None for i in range(n)]
checker[0] = 0
num = 0
count = 0

flag = 0
while flag==0 and count!=k:
    if checker[lst[num]-1]==None:
        checker[lst[num]-1]=count+1
        count+=1
        num = lst[num]-1
    else:
        flag = 1
        count+=1

if flag==1:
    remaining = (k-checker[lst[num]-1])%(count-checker[lst[num]-1])
    num = lst[num]-1
    # print("~~~")
    # print("rem",remaining)
    # print("checker",checker)
    # print("num",num)
    # print("count",count)
    for i in range(remaining):
        num = lst[num]-1

print(num+1)

Submission status: Accepted

Solution code:
N, K= (int(v) for v in input().split())
A = [0] + [int(v) for v in input().split()] 
first_visit = [0 for i in range(N+1)]

visited = []
current = 1
step = 0
loop_length = 1
loop_start = 0 
while True: 
    if step == K:
        print(current) 
        exit()

    if first_visit[current] != 0: 
        loop_length = step - first_visit[current]
        loop_start = first_visit[current]
        break

    
    first_visit[current] = step
    visited.append(current)
    current = A[current]
    step = step + 1

loop_index = loop_start + (K - loop_start) % loop_length

print(visited[loop_index])

Submission status: Accepted

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

town_num_tmp = 1  # 今いる町
seen = [-1]*(n+1) # indexの街に訪れたことがあるか（訪れたことがない: -1）
town_hist_list = []

while seen[town_num_tmp] == -1:
    seen[town_num_tmp] = 1
    town_hist_list.append(town_num_tmp)
    # 更新
    town_num_tmp = a_list[town_num_tmp]

roop_end_index = len(town_hist_list) - 1
roop_start_index = town_hist_list.index(town_num_tmp)
roop_range = roop_end_index - roop_start_index + 1

if k < roop_end_index:
    print(town_hist_list[k])
else:
    print(town_hist_list[(k-roop_start_index)%roop_range+roop_start_index])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
l=[1]           
seen={}
k=1
for i in range (K):
  if not k in seen.keys():
      seen[k]=i
      k=A[k-1]
      l.append(k)
  else:
    r_start=seen[k]
    roop=i-r_start
    K=(K-r_start)%roop+r_start
    break
ans=l[K]
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
*l, = map(int,input().split())
seenl = [1]
seen = {1}
temp=1
for i in range(k):
  temp=l[temp-1]
  if temp in seen:
    lenloop = len(seenl)-seenl.index(temp)
    r = (k-i-1)%lenloop
    temp = seenl[seenl.index(temp):][r]
    break
  seenl.append(temp)
  seen.add(temp)
print(temp)

Submission status: Accepted

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

visited = []
tf_visited = [0] * n
pos = 0
count = 0

while tf_visited[pos] == 0:
	visited.append(pos)
	tf_visited[pos] = 1
	pos = a[pos]-1
	count += 1
	if count >= k:
		print(pos+1)
		exit()

loop_start = visited.index(pos)
loop_length = len(visited)-loop_start
pos_t = (k-loop_start) % loop_length + loop_start
print(visited[pos_t]+1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
*l, = map(int,input().split())
seenl = [1]
seen = {1}
d={}
for index,i in enumerate(l):
  d[index+1]=i
#print(d)
temp=1
for i in range(k):
  temp=d[temp]
  if temp in seen:
    #print('i=',i)
    #print('temp=',temp)
    lenloop = len(seenl)-seenl.index(temp)
    #print('lenloop=',lenloop)
    r = (k-i-1)%lenloop
    temp = seenl[seenl.index(temp):][r]
    break
  seenl.append(temp)
  seen.add(temp)
print(temp)

Submission status: Accepted

Solution code:
def main():
    import sys
    n, k, *a = map(int, sys.stdin.read().split())
    a = [0] + a
    check = [0] * (n + 1)
    check[1] = 1

    i = 0
    nw = 1
    path = [1]
    while True:
        nx = a[nw]
        i += 1
        if i == k:
            print(nx)
            break
        if check[nx]:
            j = path.index(nx)
            d = j + (k - i) % (i - j)
            print(path[d])
            break
        path.append(nx)
        check[nx] = True
        nw = nx


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    n, k, *a = map(int, sys.stdin.read().split())
    a = [0] + a
    check = [0] * (n + 1)
    check[1] = 1

    i = 0
    nw = 1
    path = [1]
    while 1:
        nx = a[nw]
        i += 1
        if i == k:
            print(nx)
            break
        if check[nx]:
            j = path.index(nx)
            d = j + (k - i) % (i - j)
            print(path[d])
            break
        path.append(nx)
        check[nx] = 1
        nw = nx


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    n, k, *a = map(int, sys.stdin.read().split())
    a = [0] + a
    check = [0] * (n + 1)
    check[1] = 1

    nw = 1
    path = [1]
    for i in range(1, n + 1):
        nx = a[nw]
        if i == k:
            print(nx)
            break
        if check[nx]:
            j = path.index(nx)
            d = j + (k - i) % (i - j)
            print(path[d])
            break
        path.append(nx)
        check[nx] = 1
        nw = nx


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, k, *a = map(int, open(0).read().split())
    a = [0] + a
    check = [0] * (n + 1)
    check[1] = 1

    i = 0
    nw = 1
    path = [1]
    while 1:
        nx = a[nw]
        i += 1
        if i == k:
            print(nx)
            break
        if check[nx]:
            j = path.index(nx)
            d = j + (k - i) % (i - j)
            print(path[d])
            break
        path.append(nx)
        check[nx] = 1
        nw = nx


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
now = 1
chk = [0] * n
flg = True
count = 0
if k < 10 ** 7:
    for i in range(k):
        now = a[now - 1]
else:
    while flg:
        count += 1
        now = a[now - 1]
        if chk[now - 1] == 0 and now != 1:
            chk[now - 1] = count
        else:
            flg = False
            if (k - count) != 0 and (count - chk[now - 1]) != 0:
                rem = (k - count) % (count - chk[now - 1])
            else:
                rem = 0
    else:
        for i in range(rem):
            now = a[now - 1]
            count += 1
print(now)

Submission status: Accepted

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

pos = 1

if k <= n:
    for _ in range(k):
        pos = arr[pos]
    print(pos)
    exit()

res = []
visited = dict()
for i in range(n + 1):
    if pos in visited:
        start = visited[pos]
        length = i - visited[pos]
        print(res[start + (k - start) % length])
        exit()
    res.append(pos)
    visited[pos] = i
    pos = arr[pos]

Submission status: Accepted

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

zero = [-1]*N

t = 0 # テレポート回数をカウント
a = 1
while zero[a-1] == -1: # テレポートがループした場合に処理を抜ける
  if t == K: # テレポート上限回数に達した場合は処理を抜ける
    break
  zero[a-1] = t # 何番目にレポートしたかを記録
  t += 1
  a = A[a-1] # テレポート先を設定
else:
  k = (K-zero[a-1]) % (t - zero[a-1]) # テレポートの剰余を求める
  a = zero.index(zero[a-1] + k) + 1 # 
print(a)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [int(i) - 1 for i in input().split()]
r = []
nx = 0
sr = set([])
for i in range(n):
    r.append(nx)
    sr.add(nx)
    if k < i:
        print(r[k] + 1)
        break
    tnx = a[nx]
    if tnx in sr:
        m = r.index(a[nx])
        d = i - m + 1
        k = k - m
        k = k % d
        print(r[k + m] + 1)
        break  
    nx = tnx

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
visited=[]
o=(n+1)*[-1]
cycle,l=1,0
v=1
while o[v]==-1:
  o[v]=len(visited)
  visited.append(v)
  v=a[v-1]
cycle=len(visited)-o[v]
l=o[v]
if k<l:
  print(visited[k])
else:
  k-=l
  k%=cycle
  print(visited[l+k])

Submission status: Accepted

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

i = 0
m = [-1] * n
p = 0

while m[i] == -1:
    if p == k:
        break
    m[i] = p
    p += 1
    i = l[i]
else:
    z = (k - m[i]) % (p - m[i])
    i = m.index(m[i] + z)
print(i + 1)

Submission status: Accepted

Solution code:
n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
steps =[-1 for _ in range(n)]
loop = 0
step = 0
idx = 0
while True:
    if steps[idx]>=0:
        loop = steps[idx] #閉路の始まりの場所までの距離
        step -= 1
        break
    steps[idx] = step
    step += 1
    idx = a[idx] -1
    # print(steps)
p=0
if loop <= k:
    k-=loop
    p = loop
    x = step-loop + 1
    k = k%x
ans = 0
# print(k,p)
for i in range(n):
    if steps[i] == k+p:
        ans = i

print(ans+1)
# print(steps)
# print(loop,step,k,ans,a[ans])

Submission status: Accepted

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

reach = [False] * N
order = [0]
now_v = 0
cnt = 1
while 1:
    reach[now_v] = True
    next_v = A[now_v] - 1
    if reach[next_v]:
        goal = next_v
        break
    now_v = next_v
    order.append(now_v)
    cnt += 1
if cnt > K:
    print(order[K]+1)
    exit()

now_v = 0
cnt_tmp = 1

while 1:
    next_v = A[now_v] - 1
    if next_v == goal:
        break
    cnt_tmp += 1
    now_v = next_v
if cnt == cnt_tmp:
    cnt_tmp = 0

check = (K - cnt_tmp) % (cnt - cnt_tmp)
print(order[cnt_tmp+check]+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
visited = [0]*n
n_city = 1
while visited[n_city-1] == 0:
    visited[n_city-1] = 1
    n_city = A[n_city-1]
cnt = 1
root = n_city
n_city = A[n_city-1]
while n_city != root:
    n_city = A[n_city-1]
    cnt += 1
to_root = 0
n_city = 1
while n_city != root:
    n_city = A[n_city-1]
    to_root += 1
loop_num = k if k < to_root else (k-to_root)%cnt + to_root
cnt = 0
n_city = 1
while cnt < loop_num:
    n_city = A[n_city-1]
    cnt += 1
print(n_city)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    # visited[i]:町iにvisited[i]回目の遷移で到達
    visited = [0]*(n+1)
    step = 0
    i = 1

    while k:
        i = a[i]
        step += 1
        k -= 1
        if visited[i] != 0:
            k = k % (step - visited[i])
            for _ in range(k):
                i = a[i]
            print(i)
            break
        visited[i] = step
    else:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
now = 1
 
for i in range(len(bin(k))-2):
    if (k>>i)&1:
        now = A[now-1]
    A = [A[a-1] for a in A]
print(now)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    db = [a]
    cnt = k.bit_length()
    for c in range(1, cnt):
        temp = [0]*n
        for i in range(n):
            temp[i] = db[c-1][db[c-1][i]-1]
        db.append(temp)

    res = 1
    for i in range(cnt):
        if (k>>i) & 1:
            res = db[i][res-1]
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import copy

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

a = tuple(map(lambda x: int(x) - 1, input().split()))

ct = 0
tt = {}
tl = []

tt[ct] = 0
tl = [ ct ]

rs = 0
rc = 0

for i in range(1, k + 1):
    ct = a[ct]

    if ct in tt:
        rs = tt[ct]
        rc = i - rs
        break
    else:
        tt[ct] = i
        tl.append(ct)
    
else:
    #print(tl)
    print(tl[-1] + 1)
    exit()


k = k - rs
km = k % rc
#print(tl, rs, rc)
print(tl[rs + km] + 1)

Submission status: Accepted

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

counter = 0
place_list = []
place_set = set()
next = 1
while True:
    
    if  next in place_set:
        break
        
    else:
        place_list.append(next)
        place_set.add(next)
        next = A[next-1]
        
    counter += 1

duration_cycle = len(place_list)- place_list.index(next)
if K <len(place_list):
    print(place_list[K])
else:
    print(place_list[(K-place_list.index(next))%duration_cycle+place_list.index(next)])

Submission status: Accepted

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

num=[-1]*N
rep=[]

now=0
for i in range(N):
    if i==K:
        print(now+1)
        exit()
    aft=A[now]-1
    rep.append(now)
    if num[now]==-1:
        num[now]=i
    else:
        break
    now=aft

end=i
start=num[aft]
loop=end-start+1
print(rep[start+(K-start)%loop]+1)

Submission status: Accepted

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

l = [1]
for i in range(n):
    l.append(a[l[i] - 1])

p = l.index(l[n])

if k <= n:
    print(l[k])
else:
    x = (k - n + 1) % (n - p)
    if x == 0:
        print(l[n - 1])
    else:
        print(l[x + p - 1])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
T=str(bin(K))
S=len(T)-2
A = list(map(int,input().split()))
lst=[[0 for e in range(N+1)] for f in range(S)]
for i in range(1,N+1):
 lst[0][i]=A[i-1]
for j in range(1,S):
 for i in range(1,N+1):
  lst[j][i]=lst[j-1][lst[j-1][i]]
ans=[[e for e in range(N+1)] for f in range(S+1)]
for k in range(S):
 if int(T[k+2])==1:
  for l in range(1,N+1):
   ans[k+1][l]=lst[S-1-k][ans[k][l]]
 else:
  for l in range(1,N+1):
   ans[k+1][l]=ans[k][l]
print(ans[S][1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
*A, = map(int, input().split())
A = [a-1 for a in A]

path = []
visited = {}


def dfs(v, k):
    if v in visited:
        return v

    visited[v] = k
    path.append(v)
    return dfs(A[v], k+1)


origin = dfs(0, 0)
i = visited[origin]
loop = path[i:]


if K <= i:
    print(path[K] + 1)
else:
    j = (K - i) % len(loop)
    print(loop[j] + 1)

Submission status: Accepted

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

townOrder = [-1 for _ in range(N+1)]
townOrder[1] = 1
nextTown = 1
cicleStart = 0
cicleEnd = 0

for order in range(1, N+1):
  nextTown = trans[nextTown-1]
  if townOrder[nextTown] == -1:
    townOrder[nextTown] = order +1
  else:
    cicleStart = townOrder[nextTown]
    cicleEnd = order + 1
    break

exc = cicleStart -1
cicle = cicleEnd - cicleStart

if K > exc:
  K -= exc
  rest = K % cicle
  for _ in range(rest):
    nextTown = trans[nextTown-1]
  print(nextTown)
else:
  nextTown = 1
  for _ in range(K):
    nextTown = trans[nextTown-1]
  print(nextTown)

Submission status: Accepted

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

now = 0
visited = [0]
visited_set = set([0])

for i in range(K):
    now = A[now] - 1
    if now in visited_set:
        break
    visited.append(now)
    visited_set.add(now)
if len(visited) == N:
    print(visited[K-1]+1)
else:    
    ind = visited.index(now)
    roop = visited[ind:]
    print(roop[(K-ind)%len(roop)]+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
teleporter = list(map(lambda x: int(x) - 1, input().split()))

before_loop_idx = 0
curr_city = 0
des_set = {0}
while before_loop_idx < k:
    curr_city = teleporter[curr_city]
    if curr_city in des_set:
        break
    des_set.add(curr_city)
    before_loop_idx += 1

if before_loop_idx == k:
    print(curr_city + 1)
else:
    cycle_cities = [curr_city]
    while True:
        curr_city = teleporter[cycle_cities[-1]]
        if curr_city == cycle_cities[0]:
            break
        cycle_cities.append(curr_city)

    print(cycle_cities[(k - before_loop_idx - 1) % len(cycle_cities)] + 1)

Submission status: Accepted

Solution code:
# coding: utf-8
import copy
N, K = map(int,input().split())
A = list(map(int,input().split()))

L = [False] * (N+1)
L2 = copy.deepcopy(L)
c = 1
cnt = 0
for i in range(N):
    if L[c]:
        break
    else:
        L[c] = True
        cnt += 1
        c = A[c-1]


cnt2 = 0
for i in range(N):
    if L2[c]:
        break
    else:
        L2[c] = True
        cnt2 += 1
        c = A[c-1]

if K <= cnt:
    ans = 1
    for i in range(K):
        ans = A[ans-1]
else:
    K -= cnt
    K %= cnt2
    ans = c
    for i in range(K):
        ans = A[ans-1]

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A=[a-1 for a in A]
Arrived=[-1 for i in range(N)]
Appeared=[]
k=0
location=0
T=0
T_List=[]
while k<=K:
    k+=1
    Arrived[location]=k-1
    Appeared.append(location)
    location=A[location]
    if Arrived[location]!=-1:
        T=k-Arrived[location]
        T_List=Appeared[k-T:k]
        break
if len(T_List)==0:
    print(Arrived.index(k-1)+1)
else:
    Destination=(K-(k-T-1))%T
    print(T_List[Destination-1]+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(i) - 1 for i in input().split()]
ans = 0
while k:
    if k & 1:
        ans = a[ans]
    a = [a[ai] for ai in a]
    k >>= 1
print(ans + 1)

Submission status: Accepted

Solution code:
def resolve2():
    # ダブリング
    n, k = map(int, input().split())
    to = [[-1] * n for _ in range(60)]
    to[0] = list(map(lambda x: int(x) - 1, input().split()))

    # 2^i回テレポートした後何処にいるのか？
    for i in range(59):
        for j in range(n):
            to[i + 1][j] = to[i][to[i][j]]

    v = 0
    for i in reversed(range(60)):
        l = 1 << i
        if l <= k:
            v = to[i][v]
            k -= l

    print(v + 1)


if __name__ == '__main__':
    resolve2()

Submission status: Accepted

Solution code:
l=list(map(int,input().split()))
N=l[0]
K=l[1]
L=list(map(int,input().split()))
a=L[0]
v=0
X=[]
Y=[]
for i in range(N):
    X.append(0)
    Y.append(0)
X[0]=1
Y[0]=0
for i in range(K):
    b=a
    if X[b-1]==1:
        k1=Y[b-1]
        k2=i+1-k1
        v=1
        a=L[a-1]
        break
    X[a-1]+=1
    Y[a-1]=i+1
    a=L[a-1]
    
if v==1:
    K=(K-k1)%k2
    for i in range(K):
        b=a
        a=L[a-1]


print(b)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
tele = list(map(int, input().split()))
reached = [-1 for _ in range(n + 1)]
now = 1
count = 0
reached[1] = 0
cycle = False
while cycle == False:
    now = tele[now - 1] #current town
    count += 1
    if count == k:
        print(now)
        exit()
    elif reached[now] == -1:
        reached[now] = count
    else:
        cycle = True
roop_long = count - reached[now]
from_roop_in_town = (k - reached[now]) % roop_long

#print(reached, now, roop_long, from_roop_in_town)

for i in range(from_roop_in_town):
    now = tele[now - 1]
print(now)

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
a=list(map(lambda x:int(x)-1,input().split()))

x=[-1]*n
x[0]=0
now=0

if k<=n:
    for _ in range(k):
        now=a[now]
    print(now+1)
    sys.exit()

for i in range(1,n+1):
    now=a[now]
    if x[now]==-1:
        x[now]=i
    else:
        k=(k-x[now])%(i-x[now])
        break
for i in range(k):
    now=a[now]
print(now+1)

Submission status: Accepted

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

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = [-1]*n
    now = 0
    order = 0
    l[0] = 0
    s = {}
    ans = -100

    for i in range(n):
        a[i] -= 1

    while k > 0:
        k -= 1
        now = a[now]
        order += 1
        if l[now] != -1: #既に訪問済の場合
            loop = order - l[now]
            k %= loop
        if k == 0:
            ans = now + 1
            break
        l[now] = order #転送順で何番目の町かを記録

    print(max(ans, -1))

main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + a
visited = [False] * (n + 1)
i = 1
visited[i] = True
path = [i]
while True:
    i = a[i]
    path.append(i)
    if visited[i]:
        break
    else:
        visited[i] = True


start = path.index(i)
pattern = path[start:-1]
m = len(pattern)

if m == 0:
    print(1)
elif k < start:
    print(path[k])
else:
    print(pattern[(k - start) % m])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split())) #どこに行くかのリスト
now = 0 #どこにいるか
LOG = {}
roop = 0
count = 0

while now not in LOG and count < K:
    LOG.setdefault(now, count)
    now = A[now] -  1
    count += 1

if count < K:
    roop = len(LOG) - LOG[now]
    K = (K - count) % roop
    count = 0
    while count < K:
        now = A[now] -  1
        count += 1

print(now+1) #行った場所を保存

Submission status: Accepted

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

ans=-1
l=[-1]*n
now=0
i=1
result=[0]
while i<=k:
    now=a[now]
    if l[now]!=-1:
        
        length=i-l[now]
        d=(k-i)%length+l[now]
        ans=l.index(d)
        break
    l[now]=i
    i+=1
    
if ans!=-1:
    print(ans+1)
else:
    print(now+1)

Submission status: Accepted

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

v, p, s = [-1] * N, 1, K
while s > 0:
    if v[p - 1] == -1:
        v[p - 1] = s
    else:
        p = v.index(v[p - 1] - s % (v[p - 1] - s)) + 1
        break
    p, s = A[p - 1], s - 1
print(p)

Submission status: Accepted

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

s = 1
g = 0
i = 1
history = [s]
flag = [False] * n
flag[0] = True

while True:
    g = a[s-1]
    if flag[g-1] == True:
        break
    else:
        flag[g-1] = True
        history.append(g)
        s = g
        i += 1


x = history.index(g)

if k < i:
    ans = history[k]
else:
    d = (k-x) % (i - x)

    ans = history[x + d]

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
town = 0 #index
count=[0]*N #index
all=[1] #not index
roop=[] #not index
for _ in range(K):
  if count[town] == 2:
    break
  elif count[town]==1:
    roop.append(town+1)
  count[town]+=1
  all.append(A[town])
  town = A[town] -1
if K < len(all):
  print(all[K])
else:
  all.pop(-1)
  print(roop[(K-(len(all)-len(roop)*2))%len(roop)])

Submission status: Accepted

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

v = [A[:]]
now = 0
for i in range(60):
    tmp = v[-1]
    v.append([tmp[x] for x in tmp])
    if K>>i & 1:
        now = v[i][now]
print(now + 1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(i - 1 for i in map(int, input().split()))
now = 0
loop_start = 0
load_list = [-1] * N
Y = - 1
while loop_start < K:
    if load_list[now] == -1:
        load_list[now] = loop_start
        now = A[now]
        loop_start += 1
    else:
        start = load_list[now]
        end = loop_start - load_list[now]
        Y = start + (K - loop_start) % end
        break

if Y == -1:
    print(now + 1)
else:
    print(load_list.index(Y) + 1)

Submission status: Accepted

Solution code:
'''
参考
https://note.com/sdestiny/n/nbd01567e6f7a
テレポート回数=Kは制約で
1<=K<=10**18
とされているため、愚直にシミュレーションしていると実行時間制限を超過してしまう
ただし、町の数=Nは
2<=N<=2*10**5
となっており実行時間制限に影響はないと思われる
---
テレポータが示す転送先=dstと、各町の訪問回数を参照しながら、
・訪問した町=Aのインデックスの記録=visit
・各町の訪問回数をカウントアップ（0→1）=cnt
をすると、どこかで必ず2回目に訪問する町が出現する⇒ループ発生
---
ループ発生したら記録先を切り替え、
・ループ発生以降に訪問した町=Aのインデックスの記録=loop
・各町の訪問回数をカウントアップ（1→2）=cnt
を同様に行う
---
カウントが「2」となっている町が次の訪問箇所となったら、記録とカウントを中止する（ループ終端）
---
1.Kから、ループ終端前までの回数=len(visit)+len(loop)を減算
2.上記「1.」の数値を、ループしている町の数=len(loop)で割った余り=ans
が示すインデックスに該当する、ループ発生以降に訪問する町=loop[ans]+1が解となる
（Kは考慮せずとも、ループはどこかで必ず発生するため記録処理が無限ループになることはない）
※ループ発生前にテレポートが終了する場合：len(visit)>Kは、そのままvisit[K]+1が解となる
'''

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

dst= 0          # テレポータが示す訪問先（インデックスにするため-1する）
visit = []      # ループ発生前に訪問した町のインデックスを記録
loop = []       # ループ発生以降に訪問した町のインデックスを記録
cnt = [0] * N   # 各町の訪問回数

while cnt[dst] < 2:         # 訪問先が3回目となったら終了
    if cnt[dst] == 0:       # 未訪問（1回目の訪問）
        visit.append(dst)
    else:                   # 1度訪問済（2回目の訪問=ループ発生以降）
        loop.append(dst)
    cnt[dst] += 1
    dst = A[dst] - 1        # その町にあるテレポータが指定する訪問先（インデックスなので-1する）

if len(visit) > K:
    print(visit[K]+1)
else:
    tmp = K - len(visit) - len(loop)
    ans = tmp % len(loop)
    print(loop[ans]+1)

Submission status: Accepted

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

for i in range(1, k.bit_length()):
    ith = [a[-1][a[-1][i]] for i in range(n)]
    a.append(ith)

ans = 0

for i in range(k.bit_length()):
    if (k >> i) & 1:
        ans = a[i][ans]

print(ans+1)