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

N, K = MAP()
A = LIST()

a = [1]
r = -1
loc = 1
b = [0]*(N+1)
b[1] = 1


for i in range(N):
	loc = A[loc-1]
	#print(loc)
	if b[loc] == 0:
		a.append(loc)
		b[loc] = 1
		#print(a)
	else:
		r = i+1
		loop_start = loc
		break

#print(a)
#print(r)
#print(loop_start)

for i in range(N):
	if a[i] == loop_start:
		l = i
		break

first = a[:l]
loop = a[l:]

#print(l, r)
#print(first)
#print(loop)


K += 1

if K <= len(first):
	print(a[K-1])
else:
	K -= len(first)
	K %= len(loop)
	print(loop[K-1])

Submission status: Accepted

Solution code:
from collections import deque
N,K=map(int,input().split())
A= [0]+list(map(int,input().split()))
t=1
r=set()
q=deque([])
loop_flag=False

if K<=N:
  for i in range(1,K+1):
    t = A[t]
  print(t)
else:
  for i in range(K):
    #print(i,r)
    q.append(t)
    if t not in r:
      r.add(t)
      t=A[t]
    else:
      break
  start=0
  while q:
    a=q.popleft()
    if a==q[-1]:         
      loop_leng=i-start
      break
    start +=1
  
  K -=start
  K = K%loop_leng
  #print(start,loop_leng)
  
  t=1
  for i in range(1,start+1):
    #print(t,A[t])
    t = A[t]
  for i in range(1,K+1):
    t = A[t]  
  print(t)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
mp = list(map(int,input().split()))
save = []
isSaved = [False]*(n+1)
s_queue = [[1,0]]
while(len(s_queue)>0):
    i,cnt = s_queue.pop()
    if(cnt==k):
        break
    if(isSaved[i]):
        last=mp[i-1]
        break
    nexti = mp[i-1]
    isSaved[i] = True
    save.append(nexti)
    s_queue.append([nexti,cnt+1])


ls = len(save)

if(k<=ls):
    print(save[k-1])
else:
    for i in range(ls):
        if(save[i]==last):
            si = i
    k -= si
    save = save[si:]
    ls = len(save)
    amari = k%ls
    print(save[amari-1])

Submission status: Accepted

Solution code:
def all_search(k, a):
    point = 1
    while k > 0:
        point = a[point - 1]
        k -= 1
    return point

def find_loop(n, a):
    before_step = 0
    start_point = 1
    visited = [False] * n
    while True:
        visited[start_point - 1] = True
        start_point = a[start_point - 1]
        before_step += 1
        if visited[start_point - 1]:
            break

    loop_step = 0
    point = start_point
    visited = [False] * n
    while True:
        visited[point - 1] = True
        point = a[point - 1]
        loop_step += 1
        if visited[point - 1]:
            break
    before_step -= loop_step

    return before_step, start_point, loop_step


def solve(n, k, a):
    if n >= k:
        return all_search(k, a)
    else:
        before_step, start_point, loop_step = find_loop(n, a)
        k -= before_step
        k = k % loop_step
        point = start_point
        while k > 0:
            point = a[point - 1]
            k -= 1
        return point


n, k = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]

print(solve(n, k, a))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
ischecked=[0]*N
move=[]
move1=[]
now=0
count=0
count1=0
while 1:
    move.append(now+1)
    nex=A[now]-1
    ischecked[now]=1
    if ischecked[nex]==1:
        roop=nex+1
        break
    now=nex
for i in range(len(move))[::-1]:
    move1.append(move[i])
    if move[i]==roop:
        b=len(move)-i
        break
if K>=len(move):
    n=K-len(move)
    n=n%len(move1)
    print(move1[len(move1)-1-n])
else:
    print(move[K])

Submission status: Accepted

Solution code:
# N = int(input())

import numpy as np

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

visited = set()
from2to = {}
for i,a in enumerate(As):
    from2to[i+1] = a

id2n_warp = {}
current = 1
loop_anchor = -1
n_warp = 0
visited.add(1)
id2n_warp[1] = 0
while True:
    n_warp += 1
    next_ = from2to[current]
    if n_warp == K:
        print(next_)
        exit()
    if next_ in visited:
        loop_anchor = next_
        break
    else:
        id2n_warp[next_] = n_warp
        visited.add(next_)
    current = next_

K -= id2n_warp[loop_anchor]
# print(n_warp)
# print(K)
# print(id2n_warp[loop_anchor])
K = K % (n_warp - id2n_warp[loop_anchor])
# K = K % (n_warp - id2n_warp[loop_anchor]) if n_warp - id2n_warp[loop_anchor] > 0 else K

current = loop_anchor
for i in range(K):
    next_ = from2to[current]
    current = next_

print(next_)

Submission status: Accepted

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

paths = [0] * N
paths[0] = 1

first_length = 0
loops_length = 0

present_place = 0
for i in range(N):
    present_place = A[present_place]-1
    if paths[present_place] != 0:
        loops_length = (i+2) - paths[present_place]
        first_length = paths[present_place]-1
        break
    paths[present_place] = i+2

if K <= first_length:
    print(A[paths.index(K)])
else:
    K = K - first_length
    print(paths.index(first_length+1 + K % loops_length) + 1)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
visited = {'1': 0}
route = [1]
next_id = 0
count = 0
while count < K:
    count += 1
    if A[next_id] in visited.keys():
        route = route[visited[A[next_id]]:]
        K -= count
        break
    visited[A[next_id]] = count
    route.append(A[next_id])
    next_id = A[next_id] - 1
print(route[K % len(route)])

Submission status: Accepted

Solution code:
from collections import defaultdict

N,K=list(map(int,input().split()))
a_list=list(map(int,input().split()))
alr = defaultdict(int)
alr[1] = 1
counter = 2
next = a_list[0]
base_roop = 0
last_index = 1
while True:
    if alr[next] != 0:
        base_roop = counter-1
        break
    else:
        alr[next] = counter
        last_index = next
        next = a_list[next-1]
        counter += 1

# nextから何回でlastに帰ってくるか
alr_next = defaultdict(int)
next_roop = 0
while True:
    if a_list[next-1]==last_index:
        next_roop += 1
        alr_next[next] = next_roop
        break
    else:
        next_roop+=1
        alr_next[next] = next_roop
        next = a_list[next-1]
next_roop+=1

if K<base_roop:
    ans = K%base_roop+1
    for k,v in alr.items():
        if v==ans:
            print(k)
            exit()
else:
    K-=base_roop
    ans = K%next_roop+1
    for k,v in alr_next.items():
        if v==ans:
            print(k)
            exit()
    print(last_index)

Submission status: Accepted

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

seen = set([0])
cur = 0
visited = [0]
for _ in range(n):
    next_ = A[cur] - 1
    if next_ in seen:
        i = visited.index(next_)
        visited = visited[i:]
        break
    else:
        seen.add(next_)
        visited.append(next_)
    if len(visited) - 1 == original_k:
        print(visited[-1]+1)
        exit()
    cur = next_
    k -= 1
   


index = k % len(visited)
print(visited[k%len(visited)-1]+1)

Submission status: Accepted

Solution code:
import sys 
try:
	sys.stdin = open('Input.txt', 'r') 
	sys.stdout = open('Output.txt', 'w')
except:
	pass

input = sys.stdin.readline

n,k = map(int,input().split())
l = list(map(int,input().split()))
l.insert(0,0)
# print(l)
d = {}
city = 1
turn = 0
ini = []
cnt = 0
while True:
	if d.get(city) == None:
		d[city] = turn
		turn += 1
		ini.append(city)
		city = l[city]
		# print(city,d)

	else:
		cnt = d[city] - 1
		# print(cnt)
		rep = turn - d[city]
		# print(rep)
		break

if k<=cnt:
	print(ini[k])
else:
	# print(ini)
	# print(((k-cnt-1)%rep))
	print(ini[cnt+1+((k-cnt-1)%rep)])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
dic={}
goto=A[0]
for i in range(K):
    tmp=goto
    goto=A[tmp-1]
    if not tmp in dic:
        dic[tmp]=i
    else:
        bef=dic[tmp]
        loop=i-bef
        rem=K-1-i
        rem=rem%loop
        for j in range(rem):
            tmp=goto
            goto=A[tmp-1]
        break

print(tmp)

Submission status: Accepted

Solution code:
import sys
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[A[0]]
for i in range (N-1): #何回やるとどこに行くかのリストを作る
  B.append(A[B[-1]-1])
#print(B)
if N>=K:
  print(B[K-1])
else:
  #最後と同じやつを探す
  id=B.index(B[-1]) #最後と同じ数字
  #print('id:',id) 
  T = N-id-1 #周期
  new_L=B[id+1:N]#周期のみのリスト
  #print(new_L)
  mod = (K-N) % T
  #print(mod)
  print(new_L[mod-1])

#for i in range (K-1):
#  B = A[B-1]
#print(B)

#L=[]
#for id, x in enumerate(A):
#  L.append([id+1,x])
#print(L)
#B=L[0][1]
#for i in range (N):
#  B = L[B-1][1]

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
N, K = map(int, input().split())
A = list(map(int, input().split()))

dst = defaultdict(int)

for i, a in enumerate(A, 1):
    dst[i] = a

done = [0 for _ in range(N + 1)]
done[1] = 1
hist = [1]

now = 1
cnt = 0

while cnt < K:
    now = dst[now]
    cnt += 1
    if done[now] == 0:
        done[now] = 1
        hist.append(now)
    else:
        syuki = cnt - hist.index(now)
        print(hist[hist.index(now) + (K - cnt) % syuki])
        exit()
print(hist[-1])

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
ed=[]
d=set()
now=0
x=-1
while True:
    ed.append(now)
    d.add(now)
    ne=A[now]
    if ne in d:
        now=ne
        x=ne
        break
    else:
        now=ne
loop=[x]
now=x
while True:
    now=A[now]
    if now==x:
        break
    else:
        loop.append(now)
def ind(l,a):
    for i in range(len(l)):
        if a==l[i]:
            return i
dn=ind(ed,ne)
T=len(loop)
if K>=dn:
    ans=loop[(K-dn)%T]
    print(ans+1)
else:
    print(ed[K]+1)

Submission status: Accepted

Solution code:
import numpy as np
import sys
if __name__ == "__main__":
    N, K = map(int, input().split())
    A = list(map(int, input().rstrip().split(' ')))
    visit = [False]*N
    a_now = 1
    visit[a_now - 1] = True
    step = 0
    for i in range(N):
        a_now = A[a_now - 1]
        step += 1
        #print(a_now)
        if visit[a_now - 1]:
            break
        else:
            visit[a_now - 1] = True
        if step == K:
            #print("K:")
            print(a_now)
            sys.exit()
    
    self_loop = []
    start = a_now
    for i in range(N):
        a_now = A[a_now - 1]
        step += 1
        self_loop.append(a_now)
        if a_now == start:
            break
        if step == K:
            #print("K:")
            print(a_now)
            sys.exit()
    
    ## self_loop が見つかった場合
    #print("a_now:{}".format(a_now))
    #print("step:{}".format(step))
    #print(self_loop)
    n = len(self_loop)
    left = K-step
    left -= (left // n) * n
    #print(step)
    print(self_loop[left - 1])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [-1] + A

visit = {}
n = 1
cnt = 0
remain = K
# print("remain:", remain)
while(n not in visit.keys()):
    visit[n] = cnt
    cnt+=1
    n = A[n]
    remain -= 1
    if (remain==0):
        print(n)
        exit()
# remain -=1

# print(n, visit[n], cnt)
d = cnt - visit[n]
# print(d)
# print("d: ", d)
# print("remain:", remain)
remain = remain%d
# print("remain:", remain)
# print("current: ", n)
while(remain > 0):
    remain -= 1
    n = A[n]
    # print("new n:", n)
print(n)

Submission status: Accepted

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

seen = dict()
goal = dict()

seen[1] = 0
goal[0] = 1

prev = targets[0]
startFlag = False
for i in range(1, k):
    seen[prev] = i
    goal[i] = prev
    current = targets[prev - 1]
    if current in seen:
        before = seen[current]

        finalGoal = (k - (i+1)) % (i + 1 - before)
        print(goal[finalGoal + before])
        exit()
    prev = current


print(prev)

Submission status: Accepted

Solution code:
from decimal import *

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

A = list(map(int,input().split()))
visit = [0]*N
fi = [1]
st = 0
visit[0] = 1
p = A[0]
for i in range(N):
  fi.append(p)
  if visit[p-1] == 0:
    visit[p-1] = i+2
    p = A[p-1]
  else:
    
    st = i
    break
    
loop = []
loop.append(p)
q = p
while 1:
  if q == A[p-1]:
    break
  loop.append(A[p-1])
  p = A[p-1]
st-=len(loop)
fi = fi[:len(fi)-len(loop)-1]
if K - st> 0:
  k = (K - st) % len(loop)
  print(loop[k-1])
else:
  print(fi[K])

Submission status: Accepted

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

visit = [0] * N
turn = [-1] * N

visit[0] = 1
turn[0] = 0

cursor = 0
turn_count = 0
while True:
    cursor = A[cursor]
    turn_count += 1

    if turn_count == K:
        print(cursor+1)
        exit()

    visit[cursor] += 1

    if visit[cursor] > 1:
        loop_length = turn_count - turn[cursor]
        break

    turn[cursor] = turn_count

K -= turn[cursor]
K %= loop_length

for _ in range(K):
    cursor = A[cursor]

print(cursor + 1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
ex = [0]*n
now = 1
for i in range(k) :
    if i == k-1 :
        now = A[now-1]
        print(now)
        exit()
    elif ex[now-1] == 0 :
        ex[now-1] = i+1
        now = A[now-1]
    else :
        J = (k-i)%(i-ex[now-1]+1)
        for j in range(J) :
            now = A[now-1]
        print(now)
        exit()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
checked=[False]*(1+n)
checked_num=[0]*(1+n)
checked[1]=True
tree = [1]
ind = 1
count = 0
judge = 0
for _ in range(k):
    count += 1
    ind_ = a[ind-1]
    if checked[ind_]:
        cycle = count-checked_num[ind_]
        tree = tree[checked_num[ind_]:]
        print(tree[(k-count)%cycle])
        judge = 1
        break
    checked_num[ind_]=count
    checked[ind_]=True
    tree += [ind_]
    ind = ind_

if judge == 0:
    print(ind)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

(N, K) = (int(i) for i in input().split())

A = [int(i) for i in input().split()]

# 一周する数を求める
have_been = set()
have_been_list = []
have_been.add(1)
have_been_list.append(1)
now_place = 1
while True:
    next_place = A[now_place - 1]
    if next_place not in have_been:
        have_been.add(next_place)
        have_been_list.append(next_place)
        now_place = next_place
    else:
        break

#print('have_been = {}'.format(have_been))
loop_start_index = have_been_list.index(next_place)

loop_length = len(have_been_list) - loop_start_index
#print('loop = {}'.format(loop))

left_K = K - loop_start_index
if left_K <= 0:
    print(have_been_list[K])
    sys.exit()

mod = left_K % loop_length
print(have_been_list[mod + loop_start_index])

Submission status: Accepted

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

route = [0]
routeset = {0}
now_i = 0
loop_len = 0
for i in range(1, N):
    next_i = A[now_i]-1
    if next_i in routeset:
        loop_len = i - route.index(next_i)
        break
    routeset.add(next_i)
    route.append(next_i)
    now_i = next_i


base = len(route) - loop_len

if K < len(route):
    print(route[K]+1)
else:
    K -= base
    m = K % loop_len
    idx = route[base:][m]
    print(idx+1)

Submission status: Accepted

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

l = [-1] * N
loopcnt = 0
inicnt = 0
place = 1
i = 0
l[place - 1] = 0

while i < K:
    i += 1
    next_place = A_list[place - 1]
    place = next_place
    if l[next_place - 1] != -1:
        loopcnt = i - l[next_place - 1]
        inicnt = l[next_place - 1]
        break
    else:
        l[next_place - 1] = i
if i >= K:
    print(place)

else:
    last_move_cnt = (K - inicnt) % loopcnt

    j = 1
    while j <= last_move_cnt:
        j += 1
        next_place = A_list[place - 1]
        place = next_place
    print(place)

Submission status: Accepted

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

def main():
    N,K = map(int, readline().split())
    A = [int(i) for i in readline().split()]

    d = [0] * (N+1)
    d[1] = 1
    now = 1
    next_ = A[0]
    c = [0] * (N+1)
    cnt = 0
    while d[next_] == 0:
        d[next_] = d[now] + 1
        now = next_
        next_ = A[next_-1]
        cnt += 1
        c[now] = cnt

    s = c[next_]
    loop = cnt - s

    if K <= s:
        ans = c[1:].index(K) + 1
    else:
        n = (K - s) % (loop + 1)
        ans = c[1:].index(s + n) + 1
    
    print(ans)


if __name__ == "__main__":
    main()

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
d = {0}
p = 0
while not a[p] in d:
    d.add(a[p])
    p = a[p]
#print(d)
val = [0]
p = 0
for i in range(len(d)):
    val.append(a[p])
    p = a[p]
#print(val)
cnt = 0
p = 0
while val[p] != val[-1]:
    cnt += 1
    p += 1
del val[-1]
if cnt > k:
    print(val[k]+1)
    exit()
k -= cnt
k2 = k % (len(d)-cnt)
#print(k2)
#print(cnt)
print(val[cnt + k2]+1)

Submission status: Accepted

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

START = 1
# 訪れたタイミング
town_with_i = {START: 0}
# 現在地
current = START
# 既に訪れたことある街(巡回の判定に使う)
known_towns = set([START])
i = 0
for _ in range(k):
    i += 1
    # 現在地
    current = a_list[current - 1]

    # 既に来たことがあるということは巡回している
    if current in known_towns:
        break

    # メモ
    town_with_i[current] = i
    known_towns.add(current)

# 巡回までのステップ数
first_step = town_with_i[current]
# 1周するのに必要なステップ数
r = i - town_with_i[current]

# print(town_with_i)
# print(current)
# print(i)
# print(r)

loop_num = (k - first_step) % r if r > 0 else (k - first_step)

for i in range(loop_num):
    current = a_list[current - 1]

print(current)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

if K <= N:
    pos = 0
    for _ in range(K):
        pos = A[pos] - 1
    print(pos+1)
    quit()

reached = [-1] * N
pos = 0
step = 0
while True:
    if reached[pos] != -1:
        loop_start = reached[pos]
        loop_end = step
        break
    reached[pos] = step
    pos = A[pos] - 1
    step += 1

K -= step
K = K % (loop_end - loop_start)

# print("loop_start: {}".format(loop_start))
# print("loop_end: {}".format(loop_end))
# print("K: {}".format(K))
# print("pos: {}".format(pos))
for _ in range(K):
    pos = A[pos] - 1

print(pos+1)

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = list(map(int, args[1].split()))

    dist = [-1]*n
    dist[0] = 0
    routes = [1]

    joint = -1

    i = A[0]
    for j in range(1, n+1):
        if 0 <= dist[i-1]:
            joint = dist[i-1]
            break

        routes.append(i)
        dist[i-1] = j
        i = A[i-1]

    loop = routes[joint:]
    return str(loop[(k-joint) % len(loop)] if joint < k else routes[k])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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

visited = [-1] * (N)
ans = [0] * (N + 1)
ans[0] = 1

for i in range(N):
    if visited[A[ans[i] - 1] - 1] == -1:
        visited[A[ans[i] - 1] -1 ] = 1
        ans[i+1] = A[ans[i] - 1]
    else:
        break

ans.pop(0)

for i in range(len(ans)):
    if ans[i] == 0:
        ans = ans[:i]
        break
    


check = [0] * (len(ans) + 1)
check[0] = ans[-1]

visited = [-1] * (N)
for i in range(N):
    if visited[A[check[i] - 1] - 1] == -1:
        visited[A[check[i] - 1] -1 ] = 1
        check[i+1] = A[check[i] - 1]
    else:
        break
check.pop(0)
for i in range(len(check)):
    if check[i] == 0:
        check = check[:i]
        break



if K <= len(ans):
    print(ans[K - 1])
else:
    print(check[(K - len(ans)) % len(check) - 1])

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
n,k =map(int,input().split())
A = [int(x)-1  for x in input().split()]
arrive_time = [0]*n
time = 1
done = [0]*n
done[A[0]] = 1
arrive_time[A[0]] = time
last = 0
next = A[0]
while True:
    v = next
    if done[A[v]] == 0:
        done[A[v]] = 1 
        time += 1
        arrive_time[A[v]] = time
        next = A[v]
    else:
        last = A[v]
        break  

if time >= k:
    for i,a in enumerate(arrive_time):
        if a == k:
            print(i+1)
else:
    roop = time - arrive_time[last] + 1
    nokori = (k-arrive_time[last])%roop
    ans = nokori+arrive_time[last]
    for i,a in enumerate(arrive_time):
        if a == ans:
            print(i+1)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return x if y == 0 else gcd(y, x%y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, K = LI()
A = LI()

tel = [-1] * N
flag = True
i = 0
time = 1
while True:
    # print(i, end=" ")
    if time == K:
        print(A[i])
        flag = False
        break
    
    if tel[i] == -1:
        tel[i] = [time, A[i]-1]
        i = A[i]-1
    else:
        # i = A[i]-1
        break
        # pass
    
    time += 1
    # print(time, tel)
# print()
# print(time-1)
# print(time - tel[i][0])
# print((K - (time-1)) % (time - tel[i][0]))

if flag:
    for _ in range((K - (time-1)) % (time - tel[i][0])):
        i = A[i]-1

    print(i+1)

Submission status: Accepted

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,k = readInts()
    A = readInts()
    root = []
    ok = True
    l = 0
    start = [1]
    dic = defaultdict(int)
    while True:
        if ok:
            a = 1
            ok = False
        else:
            a = root[-1]
        if not dic[A[a-1]]:
            dic[A[a-1]] = a
            root.append(A[a-1])
        else:
            j = 0
            for i in range(len(root)):
                if A[a-1] == root[i]:
                    j = i
                    break
                start.append(root[i])
            root = root[j:]
            l = j
            break
    if k < len(start):
        print(start[k])
    else:
        k = k - (l+1) if k - (l+1) >= 0 else k
        print(root[k%len(root)])
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [int(i)-1 for i in input().split()]
counter = 0
cur = 0
mem = [0]
fiv = [False]*n
fiv[0] = True
while True:
   if counter == k:
      ans = cur +1
      break
   cur = a[cur]
   
   #print(cur)
   
   mem.append(cur)
   counter += 1
   if fiv[cur]:
      if fiv[0] == True:
         fiv[0] = 0
      roop = counter -fiv[cur]
      k -= fiv[cur]
      k %= roop
      #print(k)
      ans = mem[k+fiv[cur]] +1
      break
   fiv[cur] = counter
   #print(counter,fiv,mem)
print(ans)

Submission status: Accepted

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

mem = [0]*N
mem[0] = 1
pos = 0
cic = 0
j = 0

for k in range(1,K+1):
  pos = As[pos] - 1
  if mem[pos] == 0:
    mem[pos] = 1
  else:
    j = k
    cic = pos
    break
  if k == K:
    print(pos+1)
    exit()

pos = 0
if cic == pos:
  i = 0
else:
  for l in range(1,j+1):
    pos = As[pos] - 1
    if pos == cic:
      i = l
      break

m = j - i

rlt = (K-i)%m
if rlt == 0:
  print(cic+1)
else:
  pos = cic
  for n in range(1,rlt+1):
    pos = As[pos] - 1
  print(pos+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	A = inputList()

	if N == 1:
		print(1)
		sys.exit()

	mati = [0 for i in range(N)]
	for i,val in enumerate(A):
		mati[i] = val-1

	aaaaa = 0
	if K <= 200000:
		for i in range(K):
			#print(aaaaa)
			aaaaa = mati[aaaaa]

		print(aaaaa+1)
		sys.exit()


	tugi = 0
	gizi = {}
	gizi2 = {}
	saigo = inf
	ans = []
	cnts = 0
	flg = False
	for i in range(K):
		tugi = mati[tugi]
		if flg == False:
			cnts += 1
			if tugi in gizi:
				flg = True
				ans.append(saigo)
				ans.append(tugi)
				gizi2[saigo] = 1
				gizi2[tugi] = 1
			else:
				gizi[tugi] = 1
				saigo = tugi
		else:
			if tugi in gizi2:
				break
			else:
				ans.append(tugi)
				gizi2[tugi] = 1

	if len(ans) == 0:
		print(tugi)
		sys.exit()

	tmp = len(ans)
	cnts = cnts - len(ans)
	kotae = (K-cnts+1) % (tmp)

	#print(cnts)
	#print(kotae)
	#print(ans)
	print(ans[kotae]+1)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()