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 = list(map(int, input().split()))
A = list(map(int, input().split()))
r = 0
if K <= N:
    current = 1
    for i in range(K):
        current = A[current-1]
    print(current)
else:
    isReturn = [0 for i in range(N)]
    step = 1
    current = 1
    isReturn[current-1] = step
    for i in range(N):
        current = A[current-1]
        step += 1
        if isReturn[current-1] == 0:
            isReturn[current-1] = step
        else:
            r = step - isReturn[current-1]
            break
    
    t = ((K-step) % r) + 1
    for i in range(t):
        current = A[current-1]
        
    print(current)

Submission status: Accepted

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

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

visited = [1]
is_visited = [0] * n
now = 1
step = 0
for i in range(k):
    now = a[now-1]
    step += 1
    if is_visited[now-1] == 0:
        is_visited[now-1] = 1
        visited.append(now)
    else:
        ind = visited.index(now)
        loop = visited[ind:]
        tmp = (k-step) % len(loop)
        now = loop[tmp]
        break

print(now)

Submission status: Accepted

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

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

l=[1]
di={}
di[1]=1

for i in a:
    b=a[l[-1]-1]
    if b in di:
        x=b
        break
    l.append(b)
    di[b]=1
t1=0
for j in l:
    if j==x:
        break
    else:
        t1+=1

t2=len(l)-t1
if k<=t1:
    print(l[k])

else:
    aa=(k-t1)%t2
    print(l[t1+aa])

Submission status: Accepted

Solution code:
from math import *
from collections import *
from itertools import *
from bisect import *
from operator import *
import sys
sys.setrecursionlimit(1000000)
def io():
    return map(int,input().split())
def op():
    return list(map(int,input().split()))
def o():
    return int(input())
def kl(con,x=0):
    if x==0:print('Yes') if con else print('No')
    elif x==1:print('yes') if con else print('no')
    elif x==2:print('YES') if con else print('NO')

MOD =    1000000007
MAX=2147483647
MIN=-2147483648
p=input
l,l1,l2,l3=[],[],[],[]
# for _ in range(o()):
n,k=io()
l=op()
x=y=0
i=0
fr=[0]*(200002)
while 1:
    if fr[l[i]]==0:
        l1.append(l[i])
        fr[l[i]]=1
        i=l[i]-1
    else:
        y=l1.index(l[i])
        x=len(l1)-y
        break
if k<=len(l1):
    print(l1[k-1])
else:
    k-=y
    k%=x
    if k==0:
        k=x
    print(l1[y+k-1])

Submission status: Accepted

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

n, k = (int(x) for x in input().split())
seq = [int(x) for x in input().split()]
visited = [[False,0] for _ in xrange(n)]

t = 1
cnt = 0
if n < k:
    while not visited[t-1][0]:
        visited[t-1][0] = True
        visited[t-1][1] = cnt
        t = seq[t-1]
        cnt += 1

    cycle_len = cnt - visited[t-1][1]
else:
    cycle_len = n
for _ in xrange((k-visited[t-1][1]) % cycle_len):
    t = seq[t-1]
print(t)

Submission status: Accepted

Solution code:
n,k = list(map(int,input().split()))
A = list(map(int,input().split()))
tour=[0]
visited=[0]*n
visited[0]=1
next_town = 0
flag=False
for i in range(n):
    next_town=A[next_town]-1
    if i+1==k:
        flag = True
        ans = next_town
        break
    if next_town==0:
        first_roop_idx = 0
        break
    if visited[next_town]>0:
        first_roop_idx = visited[next_town]
        break
    tour.append(next_town)
    visited[next_town]=i+1
#print(tour)
#print(visited)
#print(first_roop_idx)
if not flag:
    if k<=len(tour):
        ans = tour[k]
    else:
        k-=first_roop_idx
        #print("k=",k)
        if len(tour)-first_roop_idx==0:
            k=0
        else:k=k%(len(tour)-first_roop_idx)
        #print("k=",k)
        ans = tour[first_roop_idx+k]
print(ans+1)
#print(flag)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
# 扱いやすいので1-indexedにする
A = [0] + A
# dp[k][i] はiから2^k回移動したときの移動先を表す
dp = [A]
for k in range(1, 100):
    dp.append([0])  # 先頭はダミー（1-indexedにするため）
    for i in range(1, N + 1):
        # jはiから2^{i - 1}回移動した先
        j = dp[k - 1][i]
        # iから2^k回移動した先 = jから2^{i - 1}回移動した先
        dp[k].append(dp[k - 1][j])
ans = 1
for k in range(100):
    if K & 2 ** k > 0:
        ans = dp[k][ans]
        K -= 2 ** k
print(ans)

Submission status: Accepted

Solution code:
from queue import Queue

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

    visited = [False] * N
    visited[0] = True
    p = [1]
    l = []
    r = []

    while(len(p) < N):
        v = p[-1] - 1
        n = A[v] - 1

        if(visited[n]):
            d = p.index(n+1)
            l = p[0:d]
            r = p[d:]
            break

        p.append(A[v])
        visited[n] = True

    if(len(l) == 0 and len(r) == 0):
        print(p[K%len(p)])
    else:
        if(K < len(p)):
            print(p[K])
        else:
            k = K - len(l)
            k %= len(r)
            print(r[k])
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# A_1からスタートして、同じA_iに戻ってくるまでの[移動回数][到着場所]をリスト化

import sys
readline = sys.stdin.readline

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

route = [0]
visited = {0}
while True:
  nex = A[route[-1]] - 1
#  print(route[-1]," -> ",nex)
  if nex in visited:
#    print(nex,"is already visited")
    loopstart = route.index(nex)
#    print("loopstart =",loopstart)
    break
  else:
    visited.add(nex)
    route += [nex]
    
#print("route",route)

before_loop,one_loop = route[:loopstart],route[loopstart:]
#print("before_loop",before_loop)
#print("one_loop",one_loop)

if K <= len(before_loop) - 1:
  print(before_loop[K] + 1)
else:
  K -= len(before_loop)
  K %= len(one_loop)
  print(one_loop[K] + 1)

Submission status: Accepted

Solution code:
import sys

n, k = map(int, input().split(" "))
a = [-1] + list(map(int, input().split(" ")))

i = 1
head = []
used = {}
roop = []

index = 0
for _ in range(k):
    index += 1
    i = a[i]
    if i in used:
        head = [ k for k, v in sorted(used.items(), key=lambda x:x[1]) if v < used[i]]
        roop = [ k for k, v in sorted(used.items(), key=lambda x:x[1]) if v >= used[i]]
        if len(head) >= k:
            print(head[k-1])
        else:
            x = (k - 1 - len(head)) % len(roop)
            print(roop[x])
            sys.exit()
    else:
        used[i] = index

print([ k for k, v in sorted(used.items(), key=lambda x:x[1])][k-1])

Submission status: Accepted

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

s = {0}
loop = [0]

while a[loop[-1]] not in s:
    loop.append(a[loop[-1]])
    s.add(loop[-1])

    
idx = loop.index(a[loop[-1]])

if k < len(loop):
    print(loop[k]+1)
else:
    print(loop[(k - idx)% (len(loop) - idx) + idx] + 1)

Submission status: Accepted

Solution code:
n,k=map(int, input().split())
a=[int(x)-1 for x in list(input().split())]
way=[0]
seen=[0 for i in range(n)]
while True:
        now=way[-1]
        way.append(a[now])
        
        if seen[a[now]]==1:
                break
        seen[a[now]]=1


last=way[-1]
st=way.index(last)
en=len(way)-1
step=en-st
rest=(k-st+1)%step
if k>=st:
        if rest==0:
                ans=way[st-1+step]+1
        else:
                ans=way[st-1+rest]+1

else:
        ans=way[k]+1
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
memo = [-1] * (N+1)
checked_num = {1:None}
memo[0] = 1

teleporter = A[0]
memo[1] = teleporter
checked_num[memo[1]] = None
repeat_point = -1
flag = False

for i in range(2, N+1):
    # print(i, checked_num)
    memo[i] = A[teleporter-1]
    teleporter = A[teleporter-1]
    if memo[i] in checked_num and flag == False:
        repeat_point = i
        flag = True
    checked_num[memo[i]] = None

# print(memo)

start_point = memo.index(memo[repeat_point])
repeat = repeat_point - start_point
# print(memo, start_point, repeat_point)

if K <= N:
    print(memo[K])
else:
    mod = (K-start_point) % repeat
    # print(memo, start_point, repeat_point, mod)
    print(memo[mod+start_point])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
data = list(map(int, input().split()))
visited = [False for _ in range(n)]
nex = 0
visited[0] = True
t_l = 0
while True:
    nex = data[nex]-1
    if visited[nex] is True:
        break
    else:
        visited[nex] = True
        t_l += 1
start = nex
cycle = 1
c = [start]
while True:
    nex = data[nex]-1
    if nex == start:
        break
    else:
        cycle += 1
        c.append(nex)
before = t_l - cycle + 1
if k < before:
    nex = 0
    n = 0
    while n < k:
        nex = data[nex]-1
        n += 1
    print(nex+1)
elif start != 0:
    print(c[(k-before)%cycle]+1)
else:
    print(c[k%cycle]+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
B = []
Vector = [0]*N
j = 0
 
for i in range (0,K):
	if Vector[A[j]-1] == 1:
		Value = B.index(A[j])
		C = B[B.index(A[j])::]
		break
	else:
		B.append(A[j])
		Vector[A[j]-1] = 1
		j = A[j]-1

if A[0] ==1:
	print(1)
elif len(B) == K:
	print(B[-1])
else:
	print(C[(K-Value-1)%len(C)])

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
a = [i-1 for i in a]
num = [0] * (n)
num[0] = 1
now = 0
looped = 0
for i in range(2,k+2):
  nex = a[now]
  if num[nex]:
    start = num[nex]
    cycle = i - num[nex]
    v = (k+1-i) % cycle + start
    ans = num.index(v) + 1
    looped = 1
    break
  else:
    num[nex] = i
    now = nex
if looped:
  print(ans)
else:
  print(now+1)

Submission status: Accepted

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

keys = range(1,n+1)
values = [-1]*n
dic = dict(zip(keys,values))
dic[1] = 0
t = 1
i = 1

def inverse_lookup(d, x):
    for k,v in d.items():
        if x == v:
            return k

while i <= k:
    t = l[t-1]
    if dic[t] != -1:
        m  = dic[t]
        d = i-m
        r = (k-i+1)%d
        if r == 0:
            r = d
        ans = inverse_lookup(dic, (m+r-1))
        print(ans)
        break
    dic[t] = i
    i += 1
if i == k+1:
    print(t)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
 
check=[-1 for i in range(N)]
  
temp=1
circle=[]
for i in range(K):
  temp=A[temp-1]
  if check[temp-1]==-1:
    check[temp-1]=i
  else:
    circle.append(i-check[temp-1])
    #print(circle)
    break
  #print("temp",temp)
#print((K-i)%len(circle)-1)
if len(circle)!=0:
  amari=(K-i)%circle[0]
  temp=1
  for j in range(i+amari):
    temp=A[temp-1] 

print(temp)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(i) - 1 for i in input().split()]
visit = {0}
tmp = 0
a_list = [0]
ans = True
for i in range(k):
    tmp = a[tmp]
    if tmp in visit:
        left = a_list.index(tmp)
        ans = False
        print(a_list[left + (k - left) % (i + 1 - left)] + 1)
        break
    else:
        visit.add(tmp)
        a_list.append(tmp)
if ans:
    print(tmp + 1)

Submission status: Accepted

Solution code:
def detectCycle(a):
    start, length = 0, 1
    p1, p2 = a[1], a[a[1]]
    while p1 != p2:
        p1, p2 = a[p1], a[a[p2]]
    
    p2 = 1
    while p1 != p2:
        p1, p2 = a[p1], a[p2]
        start += 1
    
    p2 = a[p1]
    while p1 != p2:
        p2 = a[p2]
        length += 1
    
    return start, length

n, k = (int(x) for x in input().split())
a = [-1] + [int(x) for x in input().split()]
start, length = detectCycle(a)

loc = 1
for i in range(min(start,k)):
    loc = a[loc]
k = max(k-start,0)

k %= length
for i in range(k):
    loc = a[loc]
print(loc)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
d = {0:1}
b = {1:0}
p = 0
for i in range(k):
    d[i + 1] = a[p]
    b[a[p]] = i + 1
    p = a[p] - 1
    if a[p] in b:
        k = (k - b[a[p]]) % (i + 2 - b[a[p]]) + b[a[p]]
        break
print(d[k])

Submission status: Accepted

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

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

memo = [0] * n

index = 0
memo_index = 0
cnt_k = 1
while 1:
    tmp_move_to = a[index]
    if not memo[tmp_move_to]:
        memo[tmp_move_to] = 1
        index = tmp_move_to
        if cnt_k == k:
            print(tmp_move_to + 1)
            exit()
        cnt_k += 1
    else:
        break
k -= cnt_k

kaburi = tmp_move_to
circle = [kaburi]

index = kaburi
while 1:
    if kaburi == a[index]:
        break
    else:
        circle.append(a[index])
        index = a[index]
# print(circle)
print(circle[k % len(circle)] + 1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = [-1]*n
c = []
ans = 0
for i in range(k):
    s[ans] = i
    c.append(ans)
    ans = a[ans] - 1
    if s[ans] >= 0:
        t = i - s[ans] + 1
        ans = c[(k-i-1) % t + s[ans]]
        break
print(ans+1)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

s = 1
w = [1]
y = defaultdict(lambda: 0)
y[1] = 1

flag = 0
zen = 0
for i in range(k):
#	print(s,a[s-1])
	if(y[a[s-1]] == 1):
#		print("w",w,a[s-1])
		flag = 1
		if(a[s-1] == 1):
			break
		else:
			for j in range(len(w)):
#				print("aa",w[j],a[s-1])
				if(w[j] == a[s-1]):
					zen = j
					w = w[j:]
					
					break
		break
	s = a[s-1]
	y[s] = 1
	w.append(s)

#print(s,w)

if(flag==0):
	print(s)
else:
	print(w[((k - zen) % (len(w)))])
#	print(w,zen,((k - zen) % (len(w))))

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
tele = [0] + list(map(int, input().split()))
move = [-1]*(n+1)
move[1] = 0
now = 1
cnt = 0

while True:
    cnt += 1#移動回数
    now = tele[now] #移動した先

    if move[now] != -1:#探索済みなら周期を計算しbreak
        cycle = cnt - move[now]
        break
    else:
        move[now] = cnt#未探索ならこれまでの移動回数を記録
#この時cntに格納されている数は周期が起こった直後    
notCycle = move[now]
#ループが発生する前の場合
if notCycle > k:
    now = 1
    for i in range(k):
        now = tele[now]
#ループが発生する場合
else:
    loop = (k-notCycle)%cycle#ループが起こった余り
    for i in range(loop):
        now = tele[now]
print(now)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = [int(i) for i in input().split()]

Visit = [False for i in range(n+1)]

loop_st,loop_end,loop_len = 0,0,0
st = 1
releki = []
loop_list = []
for i in range(10000000000000):
    if Visit[st] == True:
        loop_key = st
        loop_st = releki.index(loop_key)
        loop_end = len(releki)-loop_st
        loop_list = releki[loop_st:]
        loop_len = len(loop_list)
        break
    releki.append(st)
    Visit[st] = True
    st = A[st-1]
if k <loop_st:
    print(releki[k])
    exit()
k -= loop_st

print(loop_list[k%loop_len])

Submission status: Accepted

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

count = 0
loc = 0
locs = {0: 0}
ini = 0

while True:
    count += 1
    loc = a[loc] - 1
    
    if count == k:
        break
    if loc in locs:
        ini = locs.get(loc)
        break
    locs[loc] = count

if count != k:
    rest = int((k - ini) % (count - ini))
    if rest <= 0:
        print(loc + 1)
    else:
        d = 0
        while True:
            d += 1
            loc = a[loc] - 1
            if d == rest:
                print(loc + 1)
                break
else:
    print(loc + 1)

Submission status: Accepted

Solution code:
b0=input().split()
towns=int(b0[0])
k=int(b0[1])
 
al=[int(i)-1 for i in input().split()]
 
rt=[-1 for x in range(towns)]
rt[0]=0
now=0
for x in range(1,300000000):
  now=al[now]
  if rt[now]!=-1:
    stp=x
    break
  else:
    rt[now]=x

ll=stp-rt[now]
k2=k-rt[now]
 
if k<rt[now]:
  print(rt.index(k)+1)
else:
  print(rt.index(k2%ll+rt[now])+1)

Submission status: Accepted

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

point=[0]*N
count_X=0
count_Y=0
i=0
while point[i]!=3:
    if point[i]<2:
        count_X+=1
    point[i]+=1
    i=A[i]-1
    if point[i]>1:
        count_Y+=1
count_Y-=1

if K>=count_X:
    Z=count_X+(K-count_X)%count_Y
else:
    Z=K

i=0
ans=1
while i<Z:
    ans=A[ans-1]
    i+=1

print(ans)

Submission status: Accepted

Solution code:
N,K=(int(x) for x in input().split())
A=list(map(int, input().split()))
if K<=N:
    s=1
    for i in range(K):
        s=A[s-1]
    print(s)
else:
    s=1
    S={1}
    iloop=1
    while A[s-1] not in S:
        S.add(A[s-1])
        s=A[s-1]
        iloop=iloop+1
    p=s
    loop=1
    while A[s-1] != p:
        loop=loop+1
        s=A[s-1]
    g=(K-iloop)%loop+iloop
    s=1
    for i in range(g):
        s=A[s-1]
    print(s)

Submission status: Accepted

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

s = [-1] * N
i = 0
cur = 0
m = 0
while True:
    if s[cur] != -1 and m != 1:
        m = i - s[cur]
        K = i + (K - i) % m
    else:
        s[cur] = i
    if i == K:
        print(cur+1)
        exit()
    i += 1
    cur = A[cur] - 1

Submission status: Accepted

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

index = 1
route = [index]
node = {index}

for i in range(1, K + 1):
    index = A[index - 1]
    if index in node:
        pre = route.index(index)
        loop = len(route)
        route_idx = (K - pre) % (loop - pre) + pre
        print(route[route_idx])
        break
    else:
        route.append(index)
        node.add(index)
else:
    print(index)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = [0] + list(map(int,input().split()))
t = 1
u = 1
ans = 1
L = [0] * (N + 1)
loop = [0]
l1 = 0
l2 = 0
count = 0

while True:
  t = A[t]
  if L[t] == 1:
    l2 += 1
    L[t] += 1
    loop.append(t)
  elif L[t] == 0:
    L[t] += 1
    l1 += 1
    l2 += 1
  elif L[t] == 2:
    break
l = l2 - l1
loop[0] = loop[-1]

if K <= l1:
  while count < K:
    u = A[u]
    count += 1
  print(u)
else:
  print(loop[(K - l1) % l])

#print(l1)
#print(l2)
#print(loop)

Submission status: Accepted

Solution code:
import collections


def main():
    N, K = list(map(int, input().split(' ')))
    A  = list(map(int, input().split(' ')))
    
    where_li = []
    pre = 0
    for i in range(N):
        where_li.append(A[pre])
        pre = A[pre]-1
    
    len_w = len(where_li)
    a = where_li.index(A[pre])
    # print(a)
    mod_s = len_w-a # ループにかかる歩数
    # print(where_li)
    if K<=len_w:
        print(where_li[K-1])
    else:
        nokori = K - len_w
        if nokori % mod_s==0:
            d = mod_s
        else:
            d = nokori % mod_s
        print(where_li[d-1+a])

main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [0]*N #各場所に最初に到着するまでの移動回数
cnt = 0 #現在の移動回数
pos = 0 #現在の場所
flag = False
while K > 0:
    cnt += 1
    K -= 1
    if visited[pos] == 0:
        visited[pos] = cnt
    elif not flag:
        K %= cnt-visited[pos]
        flag = True
    pos = A[pos]-1
print(pos+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=0
s=a[0]
q=1
f=[1,a[0]]
d=set(f)
for _ in range(n):
  s=a[s-1]
  if s in d:
    break
  else:
    f.append(s)
    d.add(s)
g=f.index(s)
t=len(f[g:])
if k<(len(f)-t):
  print(f[k])
else:
  u=(k+t-len(f))%t
  print(f[g:][u])

Submission status: Accepted

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

c = [0]*N
cc = [0]
c[0] = 1
i = 0
while True:
  c[A[i]-1] += 1  # 来た場所に1を足す
  cc.append(A[i]-1)
  if c[A[i]-1] > 1:
    memo = A[i]-1
    break
  i = A[i] - 1  # 次の場所
    
used = [i for i in range(N) if c[i] > 0]

pos = [i for i in range(len(cc)) if cc[i] == memo]

res = pos[1] - pos[0]
loop = [i for i in cc[pos[0]:pos[1]]]

if K < N:
  ans = cc[K]+1
else:
  i = (K - (pos[0])) % res
  ans = loop[i]+1
  
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
s = []
d = [-1] * (N + 1)
v = 1
c, l = 1, 0
while d[v] == -1:
    d[v] = len(s)
    s.append(v)
    v = A[v - 1]
c = len(s) - d[v]
l = d[v]
if K < l:
    print(s[K])
else:
    K -= l
    K %= c
    print(s[l + K])

Submission status: Accepted

Solution code:
N , K = map(int,input().split())
 
A = list(map(int,input().split()))
 
reach = [-1 for i in range(N)]
reach[0] = 0 #最初の町は0回でいく
now = 0
#loop = 1
dic ={}
dic[0] = 0
for i in range(N):
  to = A[now]-1
  if reach[to] != -1:
    ini = i+1
    #print(i,to,reach[to])
    loop = i+1 - reach[to]
    break
  if i+1 not in dic:
    dic[i+1] = to
  reach[to] = i+1
  #loop += 1
  now = to
 
 
#print(dic,reach,loop,ini)
if K < ini:
  print(dic[K]+1)
else:
  t = (ini-loop) + (K-ini)%loop
  print(dic[t]+1)

Submission status: Accepted

Solution code:
from collections import deque
n,k=map(int, input().split())
a=list(map(int, input().split()))
arr=[-1]*n
arr[0]=0
que=deque([a[0]])
i=1
loop=0

while loop==0:
    x=que.popleft()
    if arr[x-1]==-1:
        arr[x-1]=i
        i+=1
        que.append(a[x-1])
    else:
        loop=i-arr[x-1]
        break
b_loop=i-loop

if k<i:
    print(arr.index(k)+1)
else:
    print(arr.index(b_loop+(k-b_loop)%loop)+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
v = []
w = {}
now = 0
for i in range(K):
  p = A[now]
  now = p-1
  if p in w:
    j = v.index(p)
    df = i-j
    Kn = (K-i-1) % df
    p = v[j+Kn]
    break
  else:
    v.append(p)
    w[p] = p
print(p)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
t=[[0]*n for i in range(60)]
for i in range(n):
    t[0][i]=a[i]-1
for i in range(1,60):
    for j in range(n):
        t[i][j]=t[i-1][t[i-1][j]]
now=0
for i in range(60):
    if k>>i&1:
        now=t[i][now]
print(now+1)

Submission status: Accepted

Solution code:
#problems3
n,s=map(int,input().split())
a=1
lists=list(map(int,input().split()))
visited=[False for i in range(n+1)]
data=[]
now=a
flag=True
while flag:
    now=lists[now-1]
    if visited[now]==False:
        visited[now]=True
        data.append(now)
    else:
        data.append(now)
        flag=False


#data=[...(loop)...]
looping=0
for i in range(len(data)):
    if data[i]==data[-1]:
        mod=i
        index=i
        looping=data[i:-1]
        loop=len(data)-1-index
        break

U=(s-mod)%loop
if s<=mod:
    print(data[s-1])
elif s>mod:
    print(looping[U-1])

Submission status: Accepted

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main(n, k, a):
    ck=[-1]*n
    tak=0
    c=0
    ck[0]=c
    for i in range(n):
        c+=1
        tak=a[tak]-1
        if ck[tak]!=-1:
            loop=c-ck[tak]
            lps=ck[tak]
            break
        ck[tak]=c

    tak=0
    for i in range(min(k, (k-lps)%(loop)+lps)):
        tak=a[tak]-1

    print(tak+1)


if __name__ == '__main__':
    n,k=map(int, input().split())
    a=list(map(int, input().split()))
    main(n, k, a)

Submission status: Accepted

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

c = 0
loc = 0
locs = {0: 0}
ini = 0

while True:
    c += 1
    loc = a[loc] - 1
    
    if c == k:
        print(loc + 1)
        break
    if loc in locs:
        ini = locs.get(loc)
        break
    locs[loc] = c

if c != k:
    rest = int((k - ini) % (c - ini))
    if rest <= 0:
        print(loc + 1)
    else:
        d = 0
        while True:
            d += 1
            loc = a[loc] - 1
            if d == rest:
                print(loc + 1)
                break

Submission status: Accepted

Solution code:
def resolve():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    path = [1]
    for i in range(2*N):
        cur = A[path[-1]-1]
        path.append(cur)

    if K < N:
        print(path[K])
        exit()

    end = N
    si = N-1
    while path[si] != path[end]:
        si -= 1
    dist = end - si
    K = K % dist
    while K < N:
        K += dist

    print(path[K])

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left

import sys
# sys.setrecursionlimit(1000000)
# list(map(int, input().split()))
n, k = getList()
# dist
nums = [0] + getList()
cnt = 1
if k == 1:
    print(1)
    exit()
cur = 1
visited = [-1 for i in range(n + 1)]
visited[1] = 1
rooped = False
while True:
    # cur 行き先
    cur = nums[cur]
    cnt += 1

    # １回目に訪れていたら
    if visited[cur] != -1:
        # ループの周期
        roop = cnt - visited[cur]
        # 途中を飛ばす
        k -= ((k-cnt) // roop) * roop
        rooped = True
    if not rooped:
        # １回目に訪れたのであれば
        visited[cur] = cnt

    if cnt == k:
        print(nums[cur])
        break

Submission status: Accepted

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

zumi_hash = {}
zumi = [-1]*(2*(10**5))
ima = 1
for i in range(K):
    # 行ったことある町を通る＝ループする
    if ima in zumi_hash:
        zumi[i] = ima
        break
    # 同じ町へテレポートしている
    if ima == A[ima-1]:
        print(ima)
        exit(0)
    zumi_hash[ima] = True
    zumi[i] = ima
    ima = A[ima-1]
else:
    print(ima)
    exit(0)

loop_e = zumi.index(-1)
loop_s = zumi.index(zumi[loop_e-1])
zan_loop = K-loop_s
loop = zumi[loop_s:loop_e-1]
amari = zan_loop % (len(loop))
print(loop[amari])

Submission status: Accepted

Solution code:
n,k= list(map(int, input().split()))
li= list(map(int, input().split()))
d = [0 for i in range(n)]
c=[1]
nex=1
first=0
flag=0
for i in range(k):
    nex=li[nex-1]
    if d[nex-1]:
        first=c.index(nex)
        flag=1
        break
    d[nex-1]=1
    c.append(nex)
if flag:
    k-=first
    k%=len(c)-first
    print(c[first+k])
else:
    print(c[-1])

Submission status: Accepted

Solution code:
# D
N, K = map(int, input().split())
A = list(map(int, input().split()))
dct = {i+1:a for i,a in enumerate(A)}
visited = [0] * N
visited[0] = 1
if (K <= 2 * 10**5):
    nex = 1
    for _ in range(K):
        nex = dct[nex]
    print(nex)
else:
    cnt = 0
    nex = 1
    for _ in range(N):
        cnt += 1
        nex = dct[nex]
        visited[nex-1] += 1
        if visited[nex-1] > 1:
            break
    cnt1 = 0
    nex1 = 1
    for _ in range(N):
        cnt1 += 1
        nex1 = dct[nex1]
        if nex1 == nex:
            break
    if (cnt - cnt1) == 0:
        print(1)
    else:
        l = (K - cnt1) % (cnt - cnt1)
        for i in range(l):
            nex = dct[nex]
        print(nex)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
b = list(map(int, input().split()))
a = [0]
a.extend(b)
#print(a)
count = 1
idou = [0]*(n+1)
idousaki = a[1]
while idou[idousaki] == 0:
  idou[idousaki] = count
  idousaki = a[idousaki]
  count += 1

if k >= idou[idousaki]:
  amari = (k - idou[idousaki]) % (count -idou[idousaki])
  print(idou.index((idou[idousaki]+amari)))
else:
  print(idou.index(k))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
current = 0
visited = {0:0} # key => town, value => index
route = [0]
for i in range(1, k+1):
    n = a[current]
    if n in visited.keys():
        index = visited[n]
        remain = k - i
        circle = route[index:i]
        finish = remain % len(circle)
        current = circle[finish]
        break
    else:
        visited[n] = i
        route.append(n)

    current = n

print(current+1)

Submission status: Accepted

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

already = [0]*n
already[0] = 0
now = 0
count = 1
while True:
  count += 1
  now = a[now]-1
  if already[now]:
    k1 = already[now]
    k2 = count-already[now]
    break
  else:
    already[now] = count

if k > k2+k1:
  k -= k2+k1
  k %= k2
  ans = 1
  for i in range(k1):
    ans = a[ans-1]
  for i in range(k):
    ans = a[ans-1]
else:
  ans = 1
  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()))
lity=[[0,0] for i in range(N)]
if N<K:
  hata=True
  i=0
  a=0
  j=0
  while hata:
    if lity[i][0]==1:
      a=j-lity[i][1]
      break
    lity[i][0]+=1
    lity[i][1]=j
    i=A[i]-1
    j+=1
  K-=j
  p=K%a
  while p>=1:
    i=A[i]-1
    p-=1
  print(i+1)
else:
  i=0
  for j in range(K):
    i=A[i]-1
  print(i+1)

Submission status: Accepted

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

count = 0
i = 1
position = 1
position_list = [1]
position_history = [0] * N
start_loop = 0
def last():
  k = (K - start_loop) % (count - start_loop)
  print(position_list[start_loop+k])

while i > 0:
  position = A[position-1]
  position_history[position-1] += 1
  count += 1
  if count == K:
    print(position)
    break
  elif position_history[position-1] > 1:
    start_loop = position_list.index(position)
    position_list.append(position)
    last()
    break
  else:
    position_list.append(position)

Submission status: Accepted

Solution code:
n, k = [int(x) for x in input().split()]
a = [int(x)-1 for x in input().split()]
assert len(a) == n
current = 0
visited = [-1] * n
visited[0] = 0
for i in range(1, k):
  current = a[current]
  if visited[current] == -1:
    visited[current] = i
  else:
    pre = visited[current]
    count = (k - pre) % (i - pre) + pre
    print(visited.index(count)+1)
    break
else:
  print(a[current]+1)