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()))
visited = [-1]*(N+1)
path = []
at = 1
count = 0
while True:
    if visited[at] != -1:
        loop = count-visited[at]
        if K < count: # (K-visited[at])//loopが1以上であることを保証
            print(path[K]) # 条件 K < visited[at]なら、(K-visited[at])//loopが0以上であることを保証。どっちでもよさそう。
        else:
            print(path[(K-visited[at])%loop+visited[at]])
        break
    visited[at] = count
    count += 1
    path.append(at)
    at = A[at-1]

Submission status: Accepted

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

t_zero = [-1] * N

t = 0
a = 1

while t_zero[a-1] == -1:
  if t == K:
    break
  t_zero[a-1] = t
  t += 1
  a = A[a-1]
else:
  k = (K - t_zero[a-1]) % (t - t_zero[a-1])
  a = t_zero.index(t_zero[a-1] + k) + 1
print(a)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [False]*N
path = [0]
at = 0
loop = 0
visited[0]=True
for i in range(N):
    at = A[at]-1
    if visited[at]:
        loop = i+1-path.index(at)
        break
    else:
        visited[at]=True
        path.append(at)
if K < path.index(at):
    print(path[K]+1)
else:
    print(path[(K-path.index(at))%loop+path.index(at)]+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [False]*N
path = [0]
at = 0
loop = 0
visited[0]=True
for i in range(N):
    at = A[at]-1
    if visited[at]:
        loop = i+1-path.index(at)
        break
    else:
        visited[at]=True
        path.append(at)
if K < len(path):
    print(path[K]+1)
else:
    print(path[(K-path.index(at))%loop+path.index(at)]+1)

Submission status: Accepted

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]
    x = len(route)
    route.add(goto)
    y = len(route)
    if x == y:
        route = list(route)
        pre_goto = route.index(goto)
        dif = len(route) - pre_goto
        rest_step = (k - pre_goto) % dif
        print(route[pre_goto + rest_step])
        break
    cur = goto
else:
    route = list(route)
    print(route[k])

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n,k=reads()
ls=[]
a=list(reads())#インデックスと場所のさ１ インデックス版の場所のテレポ先
dic={1:0}#keyの場所を何回めに訪れたか
ls=[1]#index回移動した時の場所
loopcount=loopstart=0
for i in range(1,k+1):
  hoge=ls[-1]
  hoge-=1
  if a[hoge] in dic:
    loopcount=i-dic[a[hoge]]
    loopstart=dic[a[hoge]]
    break
  ls.append(a[hoge])
  dic[a[hoge]]=i
else:
  print(ls[-1])
  exit()
k=(k-loopstart)%loopcount
print(ls[k+loopstart])

Submission status: Accepted

Solution code:

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

town_loop = [1]
used = [-1] * n

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

    if used[next_town-1] == -1:
        town_loop.append(next_town)
        used[next_town-1] = 1
    else:
        break

loop_start = town_loop.index(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: Accepted

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

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

v = []
vc = [0]*n
b = 0
c = 0

while True:
    if vc[b]>0:
        stop = v.index(b)
        break
    v.append(b)
    vc[b] += 1
    b = a[b]
    c += 1



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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
l = [0]
s = set()
s.add(0)
cur = a[0] - 1
while True:
    if cur in s:
        break
    else:
        s.add(cur)
        l.append(cur)
        cur = a[cur] - 1
i = l.index(cur)
if k <= i:
    print(l[k] + 1)
else:
    print(l[(k - i) % (len(l) - i) + i] + 1)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
B=[0]
S=set()
S.add(0)
cur=A[0]-1
while True:
  if cur in S:
    break
  else:
    S.add(cur)
    B.append(cur)
    cur=A[cur]-1
d=len(B)
ind=B.index(cur)
if k<=ind:
  print(B[k]+1)
else:
  print(B[(k-ind)%(d-ind)+ind]+1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,k = map(int,input().split())

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

b = [1 for i in range(n)]


now = 0
next = a[now] - 1
c = []
for i in range(n):
    if b[next] == 0:
        d = c[:c.index(next)]
        e = c[c.index(next):]
        #print(d,e)
        break
    #print(now)
    b[now] = 0
    c.append(now)
    next = a[now] - 1
    #print(" ",next)
    now = next

if k >= len(d):
    k = k - len(d)
    k = k % len(e)
    print(e[k]+1)

else:
    print(d[k]+1)

Submission status: Accepted

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

n_buf = [0 for i in range(n)]
path_buf = []

now = 1
while True:
    n_buf[now - 1] = 1
    _next = a[now - 1]
    path_buf.append(now)
    if n_buf[_next - 1] == 1:
        path_buf.append(_next)
        break

    now = _next

index = path_buf.index(path_buf[-1])
sa = len(path_buf) - index - 1


if k >= len(path_buf):
    ans = (k - len(path_buf) + 1) % sa
    ans = path_buf[-sa-1:-1][ans]

    print(ans)
else:
    ans = path_buf[k]
    print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
#import cython
def get_keys(d, val):
    return [k for k, v in d.items() if v == val]
    
def main():
    read = lambda: sys.stdin.readline().rstrip()
    
    N, K  = map(int,read().split())
    A = list(map(int,read().split()))
    
    g = collections.defaultdict(int)
    for i, val in enumerate(A):
        g[i + 1] = val
        
    v = collections.defaultdict(int)
    cnt = 0
    cur = 1
    p = 0
    mp = 0
    while True:
        if v[cur] > 0 or cnt > 2*10**5:
            p = cnt - v[cur]
            mp = v[cur]
            break
        v[cur] = cnt
        cnt += 1
        cur = g[cur]
    
    print(get_keys(v, (K-mp)%p + mp)[0] if K >= mp else get_keys(v, K)[0])


 
if __name__ == "__main__":
    main()

Submission status: Accepted

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


while t[d] < 1:
    t[d]=e
    b += [c]
    c = a[c]
    d = c
    e+=1

if d != 0:
    length = e - t[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: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(lambda x: int(x) -1,input().split()))
gone = [-1]*N
tele = [0]*N
to = 0
cnt = 0
if  N < K:
    while(1):
        tele[cnt] = to
        gone[to] = cnt
        cnt += 1
        to = A[to]
        if gone[to] > 0:
            break

    print(tele[(K-(gone[to]))%(cnt-gone[to]) + gone[to]] + 1) 
else:
    for i in range(K):
        to = A[to]
    print(to + 1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
first_visit = [-1] * n
first_visit[0] = 0
idx = 0
turn = 1
base = n
while True:
    # 今idx にいる。次の場所をidx にいれる。
    if first_visit[a[idx] - 1] == -1:
        first_visit[a[idx] - 1] = turn
        if turn == k:
            print(a[idx])
            exit()
    else:
        base = a[idx] - 1
        # 基準になるループの開始点
        break
    idx = a[idx] - 1
    turn += 1
#print(first_visit, turn, base)
mod = (k - first_visit[base]) % (turn - first_visit[base])
ans = first_visit.index(first_visit[base] + mod)
print(ans + 1)

Submission status: Accepted

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

visited=[1]

for i in range(n):
  next=a[visited[-1]]
  visited.append(next)
  
loop_end=n
loop_start=n-1
while visited[loop_start]!=visited[loop_end]:
  loop_start-=1
period=loop_end-loop_start
#print(visited) 
#print("p:",period)
#print("(k-n)%period:",(k-n)%period)

if k<n+1:
  print(visited[k])
  exit()
else:
  print(visited[n-period+(k-n)%period])

Submission status: Accepted

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

if K <= N:
    position = 0
    for k in range(K):
        position = a[position] - 1
    print(position + 1)
    exit()
else:
    flag = 0
    position = 0
    visit = [False] * N
    visit[position] = True

    time = 0
    while flag == 0:
        position = a[position] - 1
        time += 1
        if visit[position]:
            flag = 1
        else:
            visit[position] = True

    time_second = time
    position_loop_start = position
    position = 0
    for t in range(time):
        if position == position_loop_start:
            time_first = t
        position = a[position] - 1
    #print(time_first,time_second)
    time_loop = time_second - time_first

    K_nokori = (K - time_first)%time_loop
    position = position_loop_start

    for k in range(K_nokori):
        position = a[position] - 1
    print(position + 1)

Submission status: Accepted

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

n,k = map(int,input().split())
L=list(map(int,input().split()))
town=[]
visit=[False]*(n+1)
next=1
while 1:
    next = L[next-1]
    if not visit[next]:
        visit[next] = True
        town.append(next)
    else:
        town.append(next)
        break
for i in range(n):
    if town[i]==town[-1]:
        mod = i
        loop = len(town)-i-1
        loop_array = town[i:-1]
        break
fin_len = (k-mod)%loop
if k<=mod:
    print(town[k-1])
else:
    print(loop_array[fin_len-1])

Submission status: Accepted

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

s = []
# 訪れていない
visited = [-1] * (N+1)
v = 1
while visited[v] == -1: 
  visited[v] = len(s)
  s.append(v)
  # ワープさせる
  v = A[v-1]

# サイクルの長さ
c = len(s) - visited[v]
# はみ出す分の長さ
l = visited[v]

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

Submission status: Accepted

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

p = 1
route = [p]
route_set = set([p])
for i in range(1, K+1):
    p = A[p-1]
    if p in route_set:
        li = route.index(p)
        ri = len(route)
        idx = li + (K-li) % (ri-li)
        print(route[idx])
        break
    else:
        route.append(p)
        route_set.add(p)
else:
    print(p)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = list(map(int,input().split()))
# print(s)
now_city = 1
s_l_city = 1
t = [0] #何回そこを通ったか
f = [0] #何回目にそこを通ったか
a=0
b = 0#サイクルありなし
f_l=0#ループの最初

#【ループ回数】200000
for i in range(n):
    t.append(0)
    f.append(-1)
# print(s)
sycle = 0
#【ループ回数】200000
for i in range(1,n+10):
    now_city = s[now_city-1]

    if t[now_city-1]==1:
        #  print(i,f[j])
         sycle=i-f[now_city-1]
         f_l=f[now_city-1]
        #  f_l=i
        #  a = 1
         b = i
        #  s_l_city=now_city
        #  print("ループの最初の数字",now_city,"最初は"+str(f_l)+"回目","周期は",sycle)
         break
    t[now_city-1]+=1
    f[now_city-1]=i
# print(t)
# print(f_l)
# print(f_l,sycle,s_l_city)

if k>b:
    # now_city=s_l_city
    for _ in range((k-f_l)%sycle):

        now_city = s[now_city-1]
    # print((k-f_l)%sycle)
    print(now_city)
else:
    # print("ループなし")
    now_city=1
    for _ in range(k):
        now_city=s[now_city-1]
    print(now_city)

Submission status: Accepted

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

# mp = dict()
# for ix in range(N):
#     mp[ix+1] = A[ix]

hist = []
exists = [0] * (N+1)
cur = 1
cnt = 0

# ここがおかしい?
# while True:
#     cur = mp[cur]
#     cnt += 1
#     # K -= 1

#     if exists[cur] != 0:
#         break
#     else:
#         exists[cur] = 1
#         hist.append(cur)

A = [0] + A
# print(A)
while exists[cur] == 0:
    hist.append(cur)
    exists[cur] = 1
    cur = A[cur]

cycle_sp = cur
# cycle_l = 0
cycle_sp_ix = hist.index(cycle_sp)

import sys
if K < cycle_sp_ix:
    print(hist[K])
    sys.exit()

cycle_l = len(hist) - cycle_sp_ix
# while True:
#     cur = mp[cur]
#     cycle_l += 1

#     if cur == cycle_sp:
#         break

rest = (K-cycle_sp_ix) % cycle_l
# print("cnt:", cnt)

# print("K:", K)
# print("cycle_l:", cycle_l)
# print("rest:", rest)

print(hist[rest + cycle_sp_ix])
# while rest != 0:
#     cur = mp[cur]
#     rest -= 1

# print(cur)




"""
# hist = [1]
hist = {1: 0}
while True:

    hk = hist.keys()[-1]

    if not mp[hk] in hist.keys():
        # hist.append(mp[hist[-1]])
        hist[mp[hk]] = 0

    else:
        # found
        cstart = hist.index(mp[hk])
        cend = len(hist)
        cycle_l = cend - cstart
        # print("hist:", hist)
        # print("cstart:", cstart)
        # print("cend:", cend)
        # print("cycle_l:", cycle_l)

        ans_i = (K - cstart) % cycle_l
        # print("ans_i:", ans_i)
        ans = hist[cstart + ans_i]

        print(ans)
        break
"""

Submission status: Accepted

Solution code:
import sys

n, k = map(int, input().split())
ara = [0]
ara += list(map(int, input().split()))

now = 1
vis = []
taken = [0]*(n+1)

while taken[now] == 0:
    vis.append(now)
    taken[now] = 1
    now = ara[now]

cycleLen = len(vis) - vis.index(now)

if k < vis.index(now):
    print(vis[k])
    sys.exit()

k -= vis.index(now)
k %= cycleLen

print(vis[k + vis.index(now)])

Submission status: Accepted

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

used = [-1]*N
cnt = 0
town = 0
used[0] = 0
while True:
    town = A[town]
    cnt += 1
    if used[town] >= 0:
        cnt = cnt-used[town]
        break
    used[town] = cnt

if K > used[town]:
    K -= used[town]
    K %= cnt
    K += used[town]
ans = used.index(K)+1
print(ans)

Submission status: Accepted

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
q=[False]*N
while a==0and count<K:
    now=A[now-1]
    count+=1
    if q[now-1]:
        a=1
    else:
        l.append(now)
        q[now-1]=True
        
b=l.index(now)
c=count-b
if count==K:
    print(now)
else:
    n= ((K-b)%c)
    print(l[b+n])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
ANS=[-1 for i in range(N)]
a=0
count=1
for i in range(N):
  a=A[a]-1
  if ANS[a]==-1:
    ANS[a]=count
    count+=1
  else:
    roop=count-ANS[a]
    break
if K<count:
  ans=ANS.index(K)+1
else:
  b=(K-ANS[a])%roop+ANS[a]
  ans=ANS.index(b)+1
print(ans)

Submission status: Accepted

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

s = [True] * n #訪れているかを判定するlist
c = [1] #訪ずれた順番を記録するlist
now = 0 #現在地
while s[now]:
    s[now] = False #訪ずれた地点を記録
    now = a[now] - 1
    c.append(now+1)

start_cycle = c.index(c[-1]) #ループに入る点
loop = c[start_cycle:-1] #ループのlist
cycle = len(loop)

if k < start_cycle: #ループまで到達できないK
    print(c[k])
else:
    k -= start_cycle
    k %= cycle
    print(loop[k])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=K%N
ANS=[-1 for i in range(N)]
a=0
count=1
for i in range(N):
  a=A[a]-1
  if ANS[a]==-1:
    ANS[a]=count
    count+=1
  else:
    roop=count-ANS[a]
    break
if K<count:
  ans=ANS.index(K)+1
else:
  b=(K-ANS[a])%roop+ANS[a]
  ans=ANS.index(b)+1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, K = (int(i) for i in input().split())  
A = [int(i) - 1 for i in input().split()] 
N = len(A)

def get_keys_from_value(d, val):
    return [k for k, v in d.items() if v == val][0]

now = 0
lis = []
p = {}
for i in range(N):
  now = A[now]
  if now in p:
    break
  
  p[now] = i
  lis.append(now)

if K < i:
  print(lis[K-1] + 1)
else:
  print(lis[(K-i-1) % (i - p[now]) + p[now]] + 1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
kiseki=[-1]*n
i=0
v=1
while kiseki[v-1]==-1:
  kiseki[v-1]=i
  v=l[v-1]
  i+=1
saisyo=kiseki[v-1]
kuri=i-saisyo

if saisyo>k:
  print(kiseki.index(k)+1)
else:
  amari=(k-saisyo)%kuri
  print(kiseki.index(amari+saisyo)+1)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
v=[-1]*n
t=c=0
while v[t]<0: v[t]=c; c+=1; t=a[t]-1
l=v[t]
c-=l
print(v.index(min(k,l+(k-l)%c))+1)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
v=[-1]*n
t=c=0
while v[t]<0:
  v[t]=c
  c+=1
  t=a[t]-1
l=v[t]
c-=l
print(v.index(min(k,l+(k-l)%c))+1)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
v=[0]+[-1]*n
t=a[0]-1
c=1
while v[t]<0:
  v[t]=c
  t=a[t]-1
  c+=1
l=v[t]
c-=l
print(v.index(min(k,l+(k-l)%c))+1)

Submission status: Accepted

Solution code:
def main():
    nums = list(map(int, input().split()))
    n, k = nums[0], nums[1]
    graph = {}
    out = list(map(int, input().split()))
    for i in range(n):
        graph[i + 1] = out[i]
    
    cycle_length = None
    visited = {}
    ans = None

    def go(x, rem):
        while rem:
            x = graph[x]
            rem -= 1
        
        nonlocal ans
        ans = x
        return x

    def dfs(i, rem):
        j = i
        while rem:
            if j in visited:
                nonlocal cycle_length
                cycle_length = visited[j] - rem
                steps = rem % cycle_length
                go(j, steps)
                return
            visited[j] = rem
            rem -= 1
            j = graph[j]

        nonlocal ans
        if not ans:
            ans = j
        return j

    dfs(1, k)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
v=[0]+[-1]*n
p=0
for i in range(n):
  t=a[p]-1
  if v[t]>=0: l,r=v[t],i+1; break
  v[t]=i+1; p=t
print(v.index(min(k,l+(k-l)%(r-l)))+1)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
v=[0]+[-1]*~-n
p=0
for i in range(n):
  t=a[p]-1
  if v[t]>=0: l,r=v[t],i+1; break
  v[t]=i+1; p=t
print(v.index([k,l+(k-l)%(r-l)][k>l])+1)

Submission status: Accepted

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

place = 1
road = [0 for i in range(N)]
cycle = 0

road[0] = 1

while K != 0:
    place = A_i[place - 1]
    K -= 1
    if road[place - 1] == 1:
        loop_place = place
        break
    road[place - 1] = 1

while K != 0:
    loop_place = A_i[loop_place - 1]
    cycle += 1

    if place == loop_place:
        break

if cycle != 0:
    K = K % cycle

while K != 0:
    place = A_i[place - 1]
    K -= 1

print(place)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,k=f()
a=list(f())
lv=[-1]*n
lv[0]=0
p=0
for i in range(n):
  t=a[p]-1
  if lv[t]>=0:
    l,r=lv[t],i+1
    break
  lv[t]=i+1
  p=t
print(lv.index(l+(k-l)%(r-l) if k>l else k)+1)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    a = LI_()

    m = [-1] * n
    m[0] = k
    c = 0
    while k > 0:
        k -= 1
        c = a[c]
        if m[c] >= 0:
            s = m[c] - k
            k %= s
            m = [-1] * n
        m[c] = k

    return c + 1

print(main())

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [0] + [int(i) for i in input().split(" ")]
b = [0,1] + [0]*(n-1)
c = [1]
nex = 1
for i in range(1,n+1):
    nex = a[nex]
    if b[nex] == 1:
        whe = c.index(nex)
        lo = len(c)-whe
        break
    b[nex] = 1
    c.append(nex)
if whe+1 >= k:
    print(c[k])
else:
    k_ = k - whe
    print(c[whe:][k_%lo])

Submission status: Accepted

Solution code:
import sys

n, k = map(int, input().split())
ara = [0]
ara += list( map(int, input().split()) )

now = 1
vis = []
taken = [0]*(n+1)

while taken[now] == 0:
	vis.append(now)
	taken[now] = 1
	now = ara[now]

cycleLen = len(vis) - vis.index(now)

if k < vis.index(now):
	print(vis[k])
	sys.exit()

k -= vis.index(now)

k %= cycleLen

print(vis[k + vis.index(now) ])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
L = [0] * n
L[0] = 1
i = A[0] - 1
j = 1
while j < k:
    if L[i] < 2:
        L[i] += 1
    else:
        break
    i = A[i] - 1
    j += 1
if j == k:
    print(i + 1)
else:
    loop = L.count(2)
    k = (k - L.count(1)) % loop
    while k > 0:
        i = A[i] - 1
        k -= 1
    print(i + 1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
graph = [set() for i in range(N)]
for i, a in enumerate(A):
    graph[i].add(a - 1)

stack = [0]
seen = {0}
path = []
dist = [-1] * N
while stack:
    cur = stack.pop()
    if dist[cur] != -1:
        break
    dist[cur] = len(path)
    path.append(cur)
    for nei in graph[cur]:
        if nei not in seen:
            stack.append(nei)
            seen.add(nei)

not_loop = dist[graph[cur].pop()]
loop = len(path) - not_loop
if K < not_loop:
    print(path[K] + 1)
else:
    K -= not_loop
    K %= loop
    print(path[not_loop + K] + 1)

Submission status: Accepted

Solution code:
# 必ずN回以下でループする
N, K = map(int, input().split())
towns = [int(i) for i in input().split()]
arrivedList = [1]
for i in range(N * 2):
    arrivedList.append(towns[arrivedList[-1] - 1])
if K <= N:
    print(arrivedList[K])
    exit()

loop_end = N
loop_start = N - 1
while (arrivedList[loop_end] != arrivedList[loop_start]):
    loop_start -= 1

loop_len = loop_end - loop_start

# Kの値をloop_lenを使って調整する
K = K % loop_len
while K < N:
    K += loop_len

print(arrivedList[K])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

cur = 0     # 現在地
period = 0  # 繰り返し周期
rest = 0    # 繰り返し周期に入らない最初のテレポート回数
counter = defaultdict(int)   # 2回目を通るときの検出用
first_index = defaultdict(int)  # 1回目に通ったテレポート回数

counter[0] = 1
first_index[0] = 0
for i in range(1, N):
    cur = A[cur] - 1
    counter[cur] += 1
    if counter[cur] == 2:
        period = i - first_index[cur]
        rest = first_index[cur]
        break
    else:
        first_index[cur] = i
if K <= rest:
    cur = 0
    for i in range(K):
        cur = A[cur] - 1
    print(cur+1)
else:
    for i in range((K - rest) % period):
        cur = A[cur] - 1
    print(cur+1)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
ls_pass = [0]+list(map(int,input().split()))
a=1
b=0

ls=["ンゴ"]+[0]+["ンゴ"]*(N-1)
ls_past=[1]
for i in range(1,N*3):
  b=a
  a=ls_pass[a]
  if ls[a]!="ンゴ":
    ls_cicle=ls_past[ls[a]:i]
    print(ls_cicle[(K-i)%len(ls_cicle)])
    break
  elif i==K:
    print(a)
    break  
  else:
    ls_past.append(a)
    ls[a]=i

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
port = list(map(int, input().split()))
visited = [1]
flag = [False for i in range(n)]
current = 1

t = k

while flag[port[current-1]-1] == False and t > 0:
    visited.append(port[current-1])
    flag[port[current-1]-1] = True
    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: Accepted

Solution code:
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
root = [1]
for i in range(2*n+1000):
    next_num = a[root[-1]]
    root.append(next_num)

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

else: 
    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])

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    graph = []
    for i in range(N):
        graph.append(int(A[i] - 1))

    
    new = [True] * N
    num = 0
    visited = []
    while True:
        new[num] = False
        visited.append(num)
        num = graph[num]
        if not new[num]: #bool型なので
            visited.append(num)
            break
    v = visited.index(visited[-1])
    l = len(visited)
    kurikaeshi = l - v - 1
    if K + 1 <= l:
        print(visited[K] + 1)
    else:
        amari = (K + 1 - v) % kurikaeshi
        if amari == 0:
            amari = kurikaeshi
        print(visited[v + amari - 1] + 1)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
machi_dict = [0] * n
machi_dict[0] = 1
while True:
    if machi_dict[next_machi] == 1:
        break
    count += 1
    machi_dict[next_machi] = 1
    machi_list.append(next_machi)
    machi = next_machi
    next_machi = x[machi] - 1
z = 0
for i in range(0, count):
    if machi_list[i] == next_machi:
        z = i
        break
loop_machi_list = machi_list[z:]
if k < z:
    machi = machi_list[k] + 1
    print(machi)
else:
    k = k - z
    machi = loop_machi_list[k % len(loop_machi_list)] + 1
    print(machi)

Submission status: Accepted

Solution code:
nk = list(map(int,input().split()))
n = nk[0]
k = nk[1]
a = list(map(int,input().split()))
counter = k
town = 1
seen = {
    1:0
}
cycle_p = 1
while True:
    town = a[town-1]
    counter-=1
    if counter == 0:
        break
    if town not in seen:
        seen[town]=cycle_p
        cycle_p+=1
    else:
        cycle_length = cycle_p-seen[town]
        remainder = (counter) % cycle_length
        while True:
            if remainder == 0:
                break
            town = a[town-1]
            remainder-=1
        break
print(town)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    round = int(math.log2(K)) + 1

    dv = []
    for _ in range(round):
        l = [0] * N
        dv.append(l)
    
    for n in range(N):
        dv[0][n] = A[n] - 1
    
    for k in range(1, round):
        for n in range(N):
            dv[k][n] = dv[k - 1][dv[k - 1][n]]
    
    a = []
    for i in range(round):
        if K>>i & 1:
            a.append(i)

    now = 0
    for i in a:
        now = dv[i][now]
    print(now + 1)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]

    dv = []
    for _ in range(60):
        l = [0] * N
        dv.append(l)
    
    for n in range(N):
        dv[0][n] = A[n] - 1
    
    for k in range(1, 60):
        for n in range(N):
            dv[k][n] = dv[k - 1][dv[k - 1][n]]
    
    a = []
    for i in range(60):
        if K>>i & 1:
            a.append(i)

    now = 0
    for i in a:
        now = dv[i][now]
    print(now + 1)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

listb = [1]
listc = [0]*N
C = 1
A = list(map(int, input().split()))
                 
for i in range(N):
    C = A[C-1]
    if listc[C-1] == 0:
        listb.append(C)
        listc[C-1] = 1
    else:
        D = listb.index(C)
        listb.append(C)
        break

L = len(listb) -1

if K <= N:
    print(listb[K])
else:
    if L-D == 1 or L-D == 0:
        print(C)
    else:
        M = (K-D) % (L-D)
        print(listb[(D+M)%L])

Submission status: Accepted

Solution code:
_,k,*a=map(int,open(0).read().split());a=[0]+a;p=1
while k:p=~-k%2*p or a[p];a=[a[b]for b in a];k//=2
print(p)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split());a=[0]+a;p=1
while k:p=k%2and a[p]or p;a=[a[b]for b in a];k//=2
print(p)

Submission status: Accepted

Solution code:
n, k, *a = map(int, open(0).read().split())
a = [0] + a
p = 1
while k:
    if k % 2:
        p = a[p]
    a = [a[b] for b in a]
    k //= 2
print(p)

Submission status: Accepted

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

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

now = 1
while K > 0:
  if K & 1:
    now = A[now]
  A = [A[A[i]] for i in range(len(A))]
  K >>= 1

print(now)