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:

def main():
    n,k = map(int,input().split())
    dests =[0 for _ in range(n)]
    telepos = list(map(int,input().split()))
    for i,t in enumerate(telepos):
        dests[i] = t-1
    print(solve(dests,k))




def solve(dests,k,here = 0):
    here = 0
    telepo_times = 0
    cycle_start = -1
    cycle_end = -1
    cycle_length = -1
    visited = dict()
    visited2 = []


    #循環検出！同じ町にいつ戻ってくるのか
    while telepo_times < k:
        #print("現在地は",here)
        if here in visited:
            cycle_start = visited[here]
            #print(cycle_start,"でループが始まった")
            cycle_end = telepo_times - 1
            #print(cycle_end,"でループが終わった")
            cycle_length = cycle_end - cycle_start + 1
            #print("サイクルの長さは",cycle_length,"だ")
            break
        #ids[here] = telepo_times

        visited[here] = telepo_times
        visited2.append(here)
        telepo_times += 1
        here = dests[here]
    if cycle_length == -1:
        return here + 1

    cycle_index = (k-cycle_start) % cycle_length
    return visited2[cycle_start + cycle_index] + 1




    #telepo_times = 0
    #while telepo_times < (k - cycle_start)%cycle_length:
    #    telepo_times += 1
    #    here = dests[here]







if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

if n >=k:
    answer1 = l[k]

cnt = 1
repeat =[]
repeat.append(l.pop())
z = 0

for j in range(n - 1, -1, -1):
    z = l.pop()
    if z == repeat[0]:
        break
    else:
        cnt += 1
        repeat.append(z)

repeat = repeat[::-1]

jouyo = (k - n - 1) % cnt

if n >= k:
    print(answer1)
else:
    print(repeat[jouyo])

Submission status: Accepted

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

now = 1
temp_l = [0]*N
temp_count = [-1]*N
temp_count[0] = 0
for i in range(N):
    pre = now
    now = A[pre-1]
    if temp_l[now-1] == 1:
        end = now
        temp = i+1
        break
    else:
        temp_l[now-1] = 1
        temp_count[now-1] = i+1

s_index = temp_count[end-1]
repeat = temp - s_index
if K <= s_index:
    print(temp_count.index(K)+1)
else:
    K -= s_index
    K = K % repeat
    print(temp_count.index(K+s_index)+1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
next = a[0]
tmp_list = [a[0]]
roop_list = []
tmp_set = set([a[0]])
while(True):
    next = a[next-1]
    if next in tmp_set:
        hajimari = tmp_list.index(next)
        roop_list = tmp_list[hajimari:]
        break
    tmp_set.add(next)
    tmp_list.append(next)
if k <= hajimari:
    print(tmp_list[k-1])
else:
    print(roop_list[((k-hajimari)%len(roop_list))-1])

Submission status: Accepted

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

reached=defaultdict(int)
reached[1]=1
i=1
for j in range(1,n+1):
    if reached[A[i]]==0:
        reached[A[i]]=j+1
    else:
        t1=reached[A[i]]
        t2=j+1
        break
    i=A[i]
reached=dict(reached)
if k>t1-1:
    ama=(k-(t1-1))%(t2-t1)
    ans=[s for s,h in reached.items() if h==t1+ama]
else:
    ans=[s for s,h in reached.items() if h==k+1]
print(ans[0])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.insert(0, 0)
# print(a)
if a[1] == 1:
    print(1)
else:
    reached = {i: 0 for i in range(1, n+1)}
    now = 1
    count = 0
    while reached[now] == 0:
        reached[now] = count
        now = a[now]
        count += 1
    roop = count - reached[now]
    if k < reached[now]:
        index = k
    else:
        index = (k - reached[now]) % roop + reached[now]
    # print(reached, count)
    # print(roop, index)
    for key, value in reached.items():
        if value == index:
            print(key)
            break

Submission status: Accepted

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

n, k, *a = map(int, read().split())
dict = [-1] * (n + 1)
now = a[0]
dict[0] = 0
for i in range(1, n * 2):
    if i == k:
        print(now)
        exit()
    now = a[now - 1]
    if dict[now] != -1:
        k -= (i + 1)
        k %= (i - dict[now])
        break
    else:
        dict[now] = i
for i in range(k):
    now = a[now - 1]
print(now)

Submission status: Accepted

Solution code:
def main():
  N,K=map(int,input().split())
  A=list(map(int,input().split()))
  n=[0]*N
  #行ったことある町リスト
  d=[1]
  for _ in range(K):
    T=A[d[-1]-1]
    if n[T-1]==1:
      break
    else:
      n[T-1]=1
    d.append(T)
  F=d.index(T)
  LOOP_TOWN=d[F:]
  q=(K-F)%len(LOOP_TOWN)
  print(LOOP_TOWN[q])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n,k = map(int,input().split())

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

    #ループを探す？

    checked_dict = {1:0}
    que = deque([a[0]])

    counter = 0


    while True:
        counter += 1
        x = que.popleft()
        if counter == k:
            print(x)
            exit()
        if x in checked_dict:
            startflg = checked_dict[x]
            loop_length = counter - startflg

            inverse_dict = {v:k for k,v in checked_dict.items()}

            loop_list = [inverse_dict[i] for i in range(startflg,startflg+loop_length)]
            amari = (k-startflg) % loop_length
            print(loop_list[amari])
            exit()
        else:
            que.append(a[x-1])
            checked_dict[x] = counter

if __name__ == '__main__':
    main()

Submission status: Accepted

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

a  = [0]*n

a = [int(s) for s in input().split()]

nxt = a[0]

seen = [1]
load = set()
load.add(1)
res = 0
flag = 0
for i in range(k-1):
    #print(seen)
    #print(nxt)
    if not(nxt in load):
        seen.append(nxt)
        load.add(nxt)
        nxt = a[nxt-1]
    else:
        root = i - seen.index(nxt) + 1
        #print(root)
        #print(k-1-i)
        zansa = (k-1-i)%root
        res = seen[seen.index(nxt)+zansa]
        flag = 1
        break


if(flag == 1):
    print(res)
else:
    print(nxt)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
tmp = 1
route = [tmp]
edge = {tmp}

for i in range(1, k + 1):
    tmp = A[tmp - 1]
    if tmp in edge:
        left = route.index(tmp)
        right = len(route)
        idx = left + (k - left) % (right - left)
        print(route[idx])
        break
    else:
        route.append(tmp)
        edge.add(tmp)
        continue
else:
    print(tmp)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
i=0
s=set()
s.add(1)
order=[1]
while 1:
    if a[i] in s:
        order.append(a[i])
        break
    else:
        order.append(a[i])
        s.add(a[i])
    i=a[i]-1
for i in range(len(order)):
    if order[-1]==order[i]:
        idx=i
        break
#print(order)
cnt=len(order)-(idx+1)
if len(order)>k:
    print(order[k])
else:
    k-=len(order)
    order=order[idx+1:]
    #print(cnt)
    #print(order)
    k%=cnt
    #print(k)
    print(order[k])
#print(order)

Submission status: Accepted

Solution code:
N,K = [int(i) for i in input().split(' ')]
A = [int(i) for i in 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])
mod_s = len_w-a
if K<=len_w:
	print(where_li[K-1])
else:
	if (K-len_w)%mod_s==0:
		d = mod_s
	else:
		d = (K-len_w)%mod_s
	print(where_li[d-1+a])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
L= list(map(int, input().split()))
S=[]
S.append(1)
Q=set()
Q.add(1)
p=0
cnt=0
for i in range(n):
	if L[p] in Q:
		cnt+=1
		S.append(L[p])
		break
	else:
		cnt+=1
		S.append(L[p])
		Q.add(L[p])
		p=L[p]-1

cnt2=0
for i in range(n):
	if S[i]!=L[p]:
		cnt2+=1
	else:
		S2=S[i:]
		break
loop=len(S)-cnt2-1


if cnt>=k:
	print(S[k])
else:
	print(S2[(k-cnt)%loop])

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    A=LI_()
    dist = [inf]*N

    now = 0
    start = 0
    for i in range(N+2):
        if(dist[now] != inf):
            cycle = i - dist[now]
            if(K>=dist[now]):
                K-=dist[now] ##出発点をnowにする
                start = now
                K%=cycle
            break
        dist[now] = i
        now = A[now]
    for i in range(K):
        start = A[start]
    print(start+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int,input().split()))
P = 0
Q = [0] + [1 for _ in range(N-1)]
R = [-1] + [0 for _ in range(N-1)]
L = 0
for i in range(K):
    P = A[P]-1
    if Q[P] == 0:
        L = i - R[P]
        S = (K - R[P] - 1) % L
        G = 0
        for j in range(S + R[P] + 1):
            G = A[G]-1
        print(G+1)
        exit()
    if Q[P] == 1:
        R[P] = i
        Q[P] = 0
print(P+1)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
town = list(map(int,input().split()))
cnt = 1
step = 1
now = town[0]
via = [1]
s = {1}
while True:
  now = town[via[-1]-1]
  if not now in s:
    via.append(now)
    s.add(now)
  else:
    start = via.index(now)
    roop = len(via) - start
    break
 
 
if len(via) == 1:
    print(1)
    exit()
 
elif len(via) > k:
    print(via[k])
    exit()
 
else:
    roop_remainder = (k + 1 - start) % roop
    if roop_remainder == 0:
        print(via[-1])
    else:
        print(via[start + roop_remainder -1])

Submission status: Accepted

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

f = 1
first = []
for _ in range(n):
    num = A[f-1]
    first.append(num)
    f = num

for i in range(n):
    if num == first[i]:
        roopcount = n-i-1 #3
        break

if k <= n:
    print(first[k-1])
else:
    s = (k-(n-roopcount))%roopcount
    print(first[i+s])

Submission status: Accepted

Solution code:
import sys

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

route = [1]
appearance = set()
index = 1
cnt = 0
flg = False
for _ in range(k):
    if index in appearance:
        flg = True
        break
    appearance.add(index)
    cnt += 1
    next_city = A[index - 1]
    route.append(next_city)
    index = next_city

if flg is False:
    print(route[k])
    sys.exit()

# 繰り返し個数
duplicate = route[route.index(index):len(route) - 1]
print(duplicate[(k - cnt) % (len(duplicate))])
# print(duplicate)
# print(route)

Submission status: Accepted

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

A_list = [int(a) for a in input().split()]

# print(N, K)
# print(A_list)

keiro = [1]
visit_town = [0]*N

town = 1
c = 1
while True:
    visit_town[town - 1] = c
    c += 1
    town = A_list[town - 1]
    # print('town', town)

    if len(keiro) > 1 and visit_town[town-1] != 0:
        break
    keiro.append(town)

# print(keiro)
# print(visit_town)
# print(town)


first_visit = keiro[:visit_town[A_list[keiro[-1]-1]-1]-1]
loop_visit = keiro[visit_town[A_list[keiro[-1]-1]-1]-1:]

# print(first_visit)
# print(loop_visit)

if K <= len(first_visit)-1:
    print(first_visit[K])
else:
    l = K - len(first_visit)
    # print(l)
    c = (l) % len(loop_visit)
    # print(c)
    print(loop_visit[c])

# print(keiro[len(first_visit) + (K - len(first_visit)) % len(loop_visit)])

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
while True:
    nex = data[nex]-1
    if visited[nex] is True:
        break
    else:
        visited[nex] = True
start = nex
cycle = 1
c = [start]
while True:
    nex = data[nex]-1
    if nex == start:
        break
    else:
        cycle += 1
        c.append(nex)
nex = 0
before = 1
while True:
    nex = data[nex]-1
    if nex == start:
        break
    else:
        before += 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:
# coding: utf-8
# Your code here!
import copy

N, K = map(int, input().split())
List = list(map(int, input().split()))
saki=[1]
ato=[]

i=0
j=1
while i<N:
    saki.append(List[j-1])
    j=List[j-1]
    i+=1

ato.append(List[j-1])

if K<=N:
    print(saki[K])
    quit()

start=saki.index(ato[0])

SA=(len(List)-start)+1

o=0
check=[]
while o<SA:
    check.append(List[j-1])
    j=List[j-1]
    o+=1
print(check[(K-start)%SA])

Submission status: Accepted

Solution code:
def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    pos=set()
    pos.add(0)
    i=0
    traversal=[0]
    start=0
    nodes=[1]
    while(start<K):
        position=A[i]-1
        if position in pos:
            break
        traversal.append(position)
        pos.add(position)
        start+=1
        nodes.append(A[i])
        i=position
    if start==K:
        print(nodes[-1])
    else:
        ind=traversal.index(position)
        interval=len(traversal)-ind
        print(nodes[ind+((K-ind)%interval)])
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N,K = map(int,input().split())
lisA = [0] + list(map(int,input().split()))
# arrA = np.array(input().split(),dtype=np.int64)

if K<=N:
    i = K
    j = 1
    while i > 0:
        j = lisA[j]
        i -= 1
    print(j)
    exit()

checked = {1:0}
roopstnum = 0
i = 1
for n in range(1,N+2):
    if not lisA[i] in checked:
        checked[lisA[i]] = n
        i = lisA[i]
    else:
        roopstnum = lisA[i]
        roopstidx = checked[roopstnum]
        rooplen = n - roopstidx
        break

# print(roopstnum,rooplen,roopstidx,checked)
warukazu = rooplen
for k,v in checked.items():
    if (K-roopstidx) % warukazu == v - roopstidx:
        ans = k
print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    # N = 2*(10**4)
    # K = 10**18
    # A = [i+2 for i in range(N)]
    # A[-1] = 1
    # print(A)

    visited = [0]
    visited_set = set([0])
    now = 0
    ind = 0
    my_append = visited.append
    my_add = visited_set.add
    for i in range(K):
        a = A[now]-1
        if a in visited_set:
            ind = visited.index(a)
            break
        else:
            my_add(a)
            my_append(a)
            now = a
            # ind = i

    loop_visited = visited[ind:]
    ans_ind = (K-ind) % len(loop_visited)

    print(loop_visited[ans_ind]+1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N ,K = map(int, input().split())
A = list(map(int, input().split()))
B = [0]
C = {} 
C[0] = 0
cnt = 0
jdg = 0
q = 0
while jdg == 0:
    i = A[q]-1
    q = i
    if q in C:
        l = C[q]
        #print(q,l)
        break
    cnt += 1
    B.append(i)
    C[i] = cnt
r = cnt+1
#print(q)
#print(B)
#print(C)
#print(l)
#print(r)
H = B[l:r]
#print(H) 
M = (K-l)%(r-l)
#print(N-l,M)
if K >= r:
	print(H[M]+1)
else:
  print(B[K]+1)

Submission status: Accepted

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

root = list()


def dfs(A, num, N, memo):
    if memo[A[num]-1] == 1:
        return root.index(A[num])
    else:
        root.append(A[num])
        memo[A[num]-1] = 1
        return dfs(A, A[num]-1, N, memo)


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

    memo = [0] * N
    start = dfs(A, 0, N, memo)

    if K <= len(root):
        print(root[K-1])
    else:
        index = (K - start) % (len(root)-start)
        loop = root[start:]
        print(loop[index-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
(town, tele)=[int(x) for x in input().split()]
pos=[int(x) for x in input().split()]
move=[pos[0]]
move_dict={i:0 for i in range(1, town+1)}
while move_dict[move[-1]] <= 1 and len(move) < tele:
  move.append(pos[move[-1]-1])
  move_dict[move[-1]]+=1
if len(move) < tele:
  loop_move=move[move.index(move[-1]):-1]
  print(loop_move[(tele-(len(move)-1))%len(loop_move)-1])
else:
  print(move[-1])

Submission status: Accepted

Solution code:

def getlooptime(warpmap, start='1'):
    warpmap_ = warpmap.copy()    
    counter = 0

    for _ in range(N):

        counter += 1

        nextmap = warpmap_[start]

        if type(nextmap) == int:
            return counter - 1, (counter - 1) - (nextmap - 1)
        
        warpmap_[start] = counter
        start = nextmap

def getterminal(warpmap, n, start):
    warpmap_ = warpmap.copy()

    if n == 0:
        return start
    else:
        for _ in range(1, n + 1):
            nextmap = warpmap_[start]
            start = nextmap

        return nextmap


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

warpmap = {}

for town_num, to_warp in enumerate(A):
    
    town_num = town_num + 1
    warpmap[f"{town_num}"] = f"{to_warp}"

pasttime, looptime = getlooptime(warpmap=warpmap, start='1')

if K > pasttime:
    print(getterminal(warpmap=warpmap, n=(K - pasttime) % looptime, start=getterminal(warpmap=warpmap, n=pasttime, start='1')))
else:
    print(getterminal(warpmap=warpmap, n=K, start='1'))

Submission status: Accepted

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
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()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()
tugi = [0]+a
town  =1
route = [0]*n
route[0] = town
used = [False]*n
used[0] = True
for i in range(n):
    town = tugi[town]
    if used[town-1]:
        i = route.index(town)
        notcycle = route[:i]
        cycle = route[i:]
        break
    used[town-1] = True
    route[i+1] = town

for i in range(n):
    if cycle[i] == 0:
        cycle = cycle[:i]
        break

if len(notcycle) >k:
    print(notcycle[k])
else:
    k -= len(notcycle)
    print(cycle[k%len(cycle)])

Submission status: Accepted

Solution code:

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

P=[1]
S=[0]*N
S[0]=1
now=1

for i in range(K):
    now=A[now-1]
    if S[now-1]==1:
        x = i+1
        y = P.index(now)
        break
    elif i == K-1:
        print(now)
        exit()
    else:
        P.append(now)
        S[now-1]=1

c=(K-y)%(x-y)

print(P[y+c])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(lambda x:int(x)-1,input().split()))
seen=[-1]*N
i=0
cnt=0
iri=-1

while True:
    if(cnt==K):
        print(i+1)
        exit()
    if seen[i]!=-1:
        roop=cnt-seen[i]
        iri=i
        K-=seen[i]
        K=K%roop
        break
    seen[i]=cnt
    cnt+=1
    i=A[i]
now=iri
for i in range(K):
    now=A[now]


print(now+1)

Submission status: Accepted

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

visited = [0] * n
next_town = 0
order = []

while True:
    if visited[next_town]:
        break
    order.append(next_town)
    visited[next_town] = 1
    next_town = a[next_town]

first_loop = len(order)
offset = order.index(next_town)
second_loop = first_loop - offset

if k < first_loop:
    print(order[k] + 1)
else:
    print(order[offset + (k - first_loop) % second_loop] + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    N,K=pin()
    A=list(pin())#henkan
    seen=set([0])
    junban=[0]
    #print(seen)
    
    
    point_1=0
    for n in range(N):
        #print(A[point_1])
        point_1=A[point_1]-1
        junban.append(point_1)
        if (point_1) in seen:
            #print(n)
            b=n
            break 
        seen.add(point_1)
        
        
    #print(n,junban,point_1)
    for m in range(len(junban)):
        if junban[m]==point_1:
            a=m
            break
    g=(len(junban)-1-a)
    #print(g)
    if K>a:
        k=(K-a)%g
        print(junban[a+k]+1)
    else:print(junban[K]+1)
#%%submit!
resolve()

Submission status: Accepted

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

h = set([])

c = 0
for i in range(2 * n):
  c = a[c] - 1
  if n < i:
    if c + 1 in h:
      break
    else:
      h.add(c + 1)

c = 0
d = 0
for i in range(n):
  c = a[c] - 1
  if c + 1 in h:
    break
  else:
    d += 1

c = 0
if d >= k:
  for i in range(k):
    c = a[c] - 1
else:
  for i in range(d + ((k - d) % len(h) + len(h))):
    c = a[c] - 1


print(c + 1)

Submission status: Accepted

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

lst = [0] * N
k = 1
cnt = 0
for j in range(10*N):
  lst[k-1] += 1
  k = A[k-1]
num = len(list(filter(lambda x:x>=1,lst)))
k = 1
first = []
loop = []
for j in range(num):
  if lst[k-1] == 1:
    first.append(k)
  elif lst[k-1] > 1:
    loop.append(k)
  k = A[k-1]
if K < len(first):
  print(first[K])
else:
  K -= len(first)
  print(loop[K%len(loop)])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = {i:[] for i in range(n)}
ans = 0
for i in range(k):
    b[a[ans]-1].append(ans)
    if len(b[a[ans]-1]) == 2:
        c = [ans]
        ans = a[ans]-1
        while ans != c[0]:
            c.append(ans)
            ans = a[ans]-1
        ans = c[(k-i) % len(c)]
        break
    ans = a[ans]-1
print(ans+1)

Submission status: Accepted

Solution code:
nums = [int(e) for e in input().split()]
n = nums[0]
k = nums[1]
a = [int(e) for e in input().split()]

town = 1
count = 0
visit = [0] * n

i = 0
while i < k:
    count += 1
    i = i+1
    next_town = a[town-1]
    if visit[town-1] > 1:
        k = (k-i)%(count-1)
        i = 0
    elif visit[town-1] == 0:
        count = 0
    visit[town-1] += 1
    town = next_town

print(town)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
now = 1
cnt = 0
loop = 0
cnts = [-1] * n
cnts[now - 1] = cnt
visited = [False] * n
visited[now - 1] = True
li = [now]

while True:
    cnt += 1
    now = a[now - 1]
    li.append(now)

    if cnt == k:
        print(now)
        exit()
    if visited[now - 1]:
        loop = (cnt - cnts[now - 1])
        pre = cnts[now - 1]
        print(li[pre + (k - pre) % loop])
        exit()

    cnts[now - 1] = cnt
    visited[now - 1] = True

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
N,K = map(int, input().split())		# 5 7 2
A = [0] + list( map(int, input().split()) )	# 1 2 3 4 5 ...


M = [ [0,0] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]

p(M)

i = 1
x = y = 0
for k in range(K):
	x,y = M[i]
	
	if x==0:
		M[i][0] = A[i]
		M[i][1] = k
		i = A[i]
		continue
	
	
	a = K - y
	b = a % (k-y)
	for _ in range(b):
		i = A[i]
	
	p(x,y,k)
	p("M[1:]", M[1:])
	
	break

ans = i
print(ans)

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
alist=list(map(int,input().split()))

vislist=[1]
visset={1}
loopflag=True
endflag=False
donek=0
ima=1

while loopflag:
    ima=alist[ima-1]
    if ima in visset:
        loopflag=False
        if ima == alist[ima-1]:
            endflag=True
    else:
        vislist.append(ima)
        visset.add(ima)

        donek+=1

        if donek == k:
            loopflag=False
            endflag=True

if endflag:
    print(ima)
    sys.exit()

loopstartindex=vislist.index(ima)
looplength=len(visset)-loopstartindex
if (k+1-loopstartindex)%looplength == 0:
    print(vislist[-1])
else:
    print(vislist[loopstartindex+(k+1-loopstartindex)%looplength-1])

Submission status: Accepted

Solution code:
DEBUG = False

import time

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

visited = [False] * N
next = A[0]
visited[0] = True
K -= 1
while not visited[next]:
    if DEBUG:
        print("K: {}, next: {}".format(K, next))
        print("visited: {}".format(visited))
        time.sleep(0.1)
    if K == 0:
        print(next+1)
        exit()
    visited[next] = True
    next = A[next]
    K -= 1

K -= 1
now = next
count = 1
next = A[next]
while now != next:
    next = A[next]
    count += 1
if DEBUG:
    print("count: {}".format(count))

K %= count

if DEBUG:
    print("now: {}, count: {}, K: {}".format(now, count, K))

while K > 0:
    if DEBUG:
        print("now: {}".format(now))
    now = A[now]
    K -= 1

print(A[now]+1)

Submission status: Accepted

Solution code:
N,K = list(map(int, input().split()))
A = list(map(int, input().split()))
 
B = [1]
go = [0]*N
hop = 0
ans = 0
for n in range(N):
    nc = A[B[n]-1]
    if go[nc-1] == 1:
        idx = B.index(nc)
        loop = B[idx:]
        break
    B.append(nc)
    K -= 1
    go[nc-1] = 1
    ans = nc
    if K < 1:
        break
 
if K > 0:
    L = len(loop)
    K = K % L
    K -= 1
    ans = loop[K]
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int,input().split()))
B = []
B.append(1)
C = [0]*N
C[0] = 1

c = 0
count= 0
now=1
flag = 0

while(c < K):
  now = A[now-1]
  c += 1
  if(C[now-1] == 1):
    for i in range(len(B)):
      if(now == B[i]):
        flag = 1
        count = i
        break
  if(flag == 1):
    break
  B.append(now)
  C[now-1] = 1
if(c == K):
  print(now)
else:
  print(B[(K-count)%(len(B)-count)+count])

Submission status: Accepted

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

x = [-1] * n
y = -1

while cnt < k:
    if x[ans] == -1:
        x[ans] = cnt
        ans = a[ans]
        cnt += 1
    else:
        y = x[ans] + (k-cnt) % (cnt-x[ans])
        break

if y == -1:
    print(ans+1)
else:
    print(x.index(y) +1)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
row = []
been = [0]*n
now = 0
nex = 0
t = 0
l = [-1]*n
prev = 0
while been[now] == 0:
    l[now] = t
    row.append(now)
    been[now] = 1
    now = a[now]-1
    t += 1
    if been[now] == 1:
        prev = l[now]
# print(prev,t)
print(row[prev + (k-prev)%(t-prev)]+1 if k > prev else row[k]+1)

Submission status: Accepted

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

dist = {}
for idx, d in enumerate(A):
  dist[idx+1] = d

n = 1
hist = [1]
already = {1}
flag = True
for i in range(K):
  n = dist[n]
  if n in already:
    flag = False
    break
  already.add(n)
  hist.append(n)
if flag:
  print(n)
else:
  start = hist.index(n)
  loop = hist[start:]
  print(loop[(K - start) % len(loop)])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
dst = list(map(int, input().split()))
log = [1]
log_set=set(log)
current = 1
for i in range(1, K+1):
    current = dst[current-1]
    if current in log_set:
        loop_start_ind = log.index(current)
        loop_len = i-loop_start_ind
        current = log[loop_start_ind+(K-i) % loop_len]
        break
    else:
        log.append(current)
        log_set.add(current)
print(current)

Submission status: Accepted

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

for i in range(n):
    a[i] -= 1
    
log_size = times.bit_length() + 2
double = [[-1] * n for i in range(log_size)]

# ダブリングで2^0回(= 1回)たどって到達する値を求める
for i in range(n):
    double[0][i] = a[i]

# ダブリングで2^k回たどって到達する値を求める
for k in range(1, log_size):
    for i in range(n):
        double[k][i] = double[k - 1][double[k - 1][i]]

ans = 0
for i in range(70)[::-1]:
    if times & (1 << i):
        ans = double[i][ans]
print(ans + 1)