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 os

import sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


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

A = np.array(A, dtype=int) - 1

dp = np.zeros((K.bit_length(), N), dtype=int)
dp[0] = A
for h in range(len(dp) - 1):
    dp[h + 1] = dp[h, dp[h]]

ans = 0
for i in reversed(range(K.bit_length())):
    if K >> i & 1:
        ans = dp[i, ans]
print(ans + 1)

Submission status: Accepted

Solution code:
import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
N, K = map(int, sys.stdin.readline().split())
A = inpl()
dic = {}
for i in range(N):
    dic[i+1] = A[i]
i = 1
visit = []
visit_set = set()
while i not in visit_set:
    visit.append(i)
    visit_set.add(i)
    i = dic[i]
find = visit.index(i)
if K < find:
    print(visit[K])
else:
    root = visit[find:]
    length = len(root)
    K = (K-find) % length
    print(root[K])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
mylist =   [0] + list(map(int,input().split()))
#print(mylist)
flag_list = [float('INF') for n in range(N+1)]
#print(flag_list)
myseries = []

myflag = 0
mypos = 1
mycnt = 0 
while myflag == 0:
    if flag_list[mypos] == float('INF'):
        flag_list[mypos] = mycnt
        #print(mypos)
        myseries.append(mypos)
        mypos = mylist[mypos]
        mycnt += 1
    else:
        myflag = 1
        mystart = flag_list[mypos]
        mylen = mycnt-mystart
#print(flag_list)
#print(myseries)
#print(mystart, mylen)

if K < mystart:
    print(myseries[K])
else:
    print(myseries[(K-mystart)%mylen + mystart])

Submission status: Accepted

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

time=0
color=["white" for _ in range(n+1)]
D=[-1 for _ in range(n+1)]
C,s=[],A[0]
point=0
while 1:
    if color[s]=="white":
        color[s]="gray"
        C.append(s)
        D[s]=time
        time +=1
        s=A[s-1]
    else:
        point=D[s]
        break

loop=C[point:]
if k>len(C):
    k -=point+1
    print(loop[k%len(loop)])
else:print(C[k-1])

Submission status: Accepted

Solution code:
if __name__=="__main__":
    N, K = map(int, input().split(' '))
    _town_list = input().split(' ')
    town_list = [int(n) for n in _town_list]

    next_town = town_list[0]
    visited_town = set()
    visited_town.add(1)
    visited_town.add(next_town)
    lst_visited_town = [1]
    lst_visited_town.append(next_town)
    counter = 1

    while True:
        counter += 1
        next_town = town_list[next_town-1]
        if counter == K:
            print(next_town)
            break
        if next_town in visited_town:
            repeated_town_idx = lst_visited_town.index(next_town)
            loop_num = counter - repeated_town_idx
            print(lst_visited_town[(K-repeated_town_idx)%loop_num + repeated_town_idx])
            break
        lst_visited_town.append(next_town)
        visited_town.add(next_town)

Submission status: Accepted

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

loc = 1
loclog=[1]
flag = 0
hist = [0]*N

for i in range(K):
    hist[loc-1] = 1
    loc = A[loc-1]
    if hist[loc-1] != 0:
        roopstart = loclog.index(loc)
        roopend = len(loclog)
        flag = 1
        break
    loclog.append(loc)

if flag == 0:
    ans = loc
else:
    roopidx = (K+1-roopstart)%(roopend-roopstart)
    if roopidx == 0:
        ans = loclog[roopend-1]
    else:
        ans = loclog[roopstart+roopidx-1]
print(ans)

Submission status: Accepted

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

G = {}
for i in range(1, n + 1):
    G.update({i: a[i - 1]})

seen = [False] * (n + 1)
path = [1]

i = 1
while True:
    seen[i] = True
    i = G[i]
    
    if seen[i]:
        break
    else:
        path.append(i)

m = path.index(i)

if m > k:
    print(path[k])
else:
    k -= m
    path = path[m:]
    k %= len(path)
    print(path[k])

Submission status: Accepted

Solution code:
n, k = map(int, input().strip().split())
L = list(map(int, input().strip().split()))
L = [v - 1 for v in L]
 
seen = set()
intersec = 0
route=[]
while intersec not in seen:
    seen.add(intersec)
    route.append(intersec)
    intersec = L[intersec]

intersecInd = route.index(intersec)

if k<=intersecInd:
    ans=route[k]
else:
    loopSize = len(route) - intersecInd
    ans = route[(k - intersecInd) % (loopSize) + intersecInd]
 
print(ans + 1)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

    v = 1
    s = []
    order = [-1] * (N + 1)
    while order[v] == -1:
        order[v] = len(s)
        s.append(v)
        v = A[v - 1]
    l = order[v]
    c = len(s) - order[v]

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
[N,K] = list(map(int,input().split()))
A = list(map(int,input().split()))
 
#ループする場合
flag=[0]*N
patt=[]
aaaa=0
i=0
while True:
    patt.append(i)
    if flag[i]==1:
        #del patt[-1]
        break
    flag[i]=1
    i=A[i]-1
 
 
srt = patt.index(patt[-1])
#print('srt',srt)
end = len(patt)-2
ptrn = patt[srt:end+1]
 
if K<srt:
    print(patt[K]+1)
else:
    B = (K-srt) % len(ptrn)
    #print('B',B)
 
    print(ptrn[B]+1)
    #print('0000000')
 
    #print('ptrm',ptrn)
    #print(patt)

Submission status: Accepted

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

journey = [1]

for i in range(2 * n + 100):
    next = a[journey[-1]]
    journey.append(next)

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

loop_end = n

loop_start = n - 1

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

period = loop_end - loop_start
k %= period

while k < n:
    k += period

print(journey[k])

Submission status: Accepted

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

flag=[0]*N
patt=[]
i=0
while True:
    patt.append(i)
    if flag[i]==1:
        break
    flag[i]=1
    i=A[i]-1

srt = patt.index(patt[-1])
end = len(patt)-2
ptrn = patt[srt:end+1]

if K<srt:
    print(patt[K]+1)
else:
    B = (K-srt) % len(ptrn)
    print(ptrn[B]+1)

Submission status: Accepted

Solution code:
import math
N, K = map(int, input().split())
P = [i -1 for i in map(int,input().split())]
lgk = int(math.log(K,2))
last = P
point = 0
for j in range(lgk+1):
    if (K >> j) & 1:
        point = last[point]
    res = []
    for i in last:
        res.append(last[i])
    last = res

print(point+1)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    prev_p = 1
    g = []
    seen = [0]*N
    i = 0
    while True:
        if seen[prev_p-1]:
            break
        seen[prev_p-1] = i
        g.append(A[prev_p-1])
        prev_p = g[-1]
        i += 1
    g_periodic = g[seen[prev_p-1]:]  
    g_before = g[:seen[prev_p-1]]

    if K <= len(g_before):
        print(g_before[K-1])
    else:
        K_new = (K - len(g_before)) % len(g_periodic)
        print(g_periodic[K_new-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

n, k = [0] * 2
a = []

def format_input(filename = None):
	global n, k
	global a
	if filename == None:
		n, k = list(map(int, input().split()))
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**5)
		k = rng(1, 10**18)
		a = [rng(1, n) for i in range(n)]
		print(n, k)
		print(' '.join(list(map(str, a))))

def get_answer():
	loop = [1]
	loop_index = defaultdict(int)
	start = -1
	while start == -1 and len(loop) < k + 1:
		node = a[loop[-1]-1]
		if loop_index[node] > 0:
			start = loop_index[node]
		elif node == 1:
			start = 0
		else:
			loop.append(node)
			loop_index[node] = len(loop) - 1

	l = len(loop)
	if k >= l:
		answer = loop[(k - l) % (l - start) + start]
	else:
		answer = loop[k]

	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Accepted

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

def bin(arr,val):
    left,right = 0,len(arr)-1
    while left<=right:
        mid = (left+right)//2
        if arr[mid]==val: return 1
        elif arr[mid]<val: left = mid + 1
        else: right = mid - 1
    return 0

know = []
now = 1
while not bin(know, now):
    know.append(now)
    now = a[now]

start = a[know[-1]]
for i,num in enumerate(know):
    if num == start: loop = know[i:] ; break

ans = know[k] if k<len(know) else loop[(k-len(know))%len(loop)]
print(ans)

Submission status: Accepted

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

for i in range(2*n+1000):
    nxt = a[journey[-1]]
    journey.append(nxt)

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

loop_end = n
loop_start = n-1

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

period = loop_end-loop_start
k %= period

while k < n:
    k += period

print(journey[k])

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

    pos = 1
    order = [-1] * (N+1)
    order[1] = 0
    s = [1]
    for i in range(1, N + 1):
        npos = A[pos-1]
        if i == K:
            print(npos)
            return
        if order[npos] != -1:
            l = order[npos]
            c = i - order[npos]
            break

        order[npos] = i
        s.append(npos)
        pos = npos

    L = l + (K - l) % c
    pos = s[L]

    print(pos)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# = int(input())
N, K = map(int, input().split())
A = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]
next = 1
List = [-1]*N

for i in range(K):
    if List[next-1] == -1:
        List[next-1] = i
        next = A[next-1]

    else:
        loop = i - List[next-1]
        afterloop = (K-(i-loop))%loop
        print(List.index((i-loop) + afterloop)+1)
        exit()

print(next)

Submission status: Accepted

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

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

P=0
L=[0]*int(N+1)
D=[0]*int(N+1)
c=0
R=0
while(1):
    c+=1
    P=A[P]-1
    L[c]=P
    if D[P]>0: 
        R=D[P]
        break
    D[P]=c
    if P==0: break
    

if K < R:
    ans=L[K]+1
else:
    K-=R
    K%=(c-R)
    ans=L[R+K]+1

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
aaa = list(map(lambda x: int(x) - 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 = aaa[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:
n,k = map(int,input().split())
A = list(map(int,input().split()))
dp = [-1] * (n+1)
B = []
f = 1
c = 0
ans = n
bal = 0
while dp[f-1] == -1:
    dp[f-1] =c
    B.append(f)
    f = A[f-1]
    c +=1
t = B.index(f)
if k>t:
    k -= t
    B = B[B.index(f):]
    k%=len(B)
    print(B[k])
else:
    print(B[k])

Submission status: Accepted

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

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

stack = [1]
s = {1}

def dfs(a, k):
  global stack
  global s
  if k == 0:
    return a
  next_a = A[a]
  if next_a in s:
    idx = stack.index(next_a)
    n = len(stack)
    k = (k - 1)%(n - idx)
    return stack[idx + k]
  else:
    stack.append(next_a)
    s.add(next_a)
    res = dfs(next_a, k-1)
  return res

print(dfs(1, K))

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A =[0]
B=list(map(int, input().split()))
for m in range(N):
    A.append(B[m])
place=set([])
p=[]
i=1
count=0
while i not in place:
    place.add(i)
    p.append(i)
    i=A[i]
    count+=1
if count>K:
    print(p[K])
else:
    loop=[i]
    start=i
    j=A[i]
    count+=1
    while j!=start:
        loop.append(j)
        j=A[j]
        count+=1
    if count>K:
        print(loop[K-len(p)])
    else:
        num=(K-count)%len(loop)
        print(loop[num])

Submission status: Accepted

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

for i in range(n):
  l.append(a[l[i]-1])
p = l.index(l[n])
#print(p,l[n])
if k<=n:
  print(l[k])
else:
  x = (k-n+1)%(n-p)
  if x ==0:
    x += (n-p)
    print(l[x-1])
  else:
    print(l[x+p-1])

Submission status: Accepted

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

MAX_N=2*10**5
b=[1]
visited=[-1]*(n+10)
for i in range(1,2*MAX_N+1):
    nxt=a[b[-1]]
    b.append(nxt)
        
if k<=n:
    print(b[k])
    exit()
# print(b)  
for i,bi in enumerate(b):
    if visited[bi]==-1:
        visited[bi]=i
    else:
        m=i-visited[bi]
        l=visited[bi]
        break
k=k%m

while k<n:
    k+=m
print(b[k])

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
i = 0
visit = []
visit_set = set()
while i not in visit_set:
    visit.append(i)
    visit_set.add(i)
    i = A[i] - 1
find = visit.index(i)
if K < find:
    print(visit[K] + 1)
else:
    root = visit[find:]
    K = (K-find) % len(root)
    print(root[K] + 1)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
As = list(map(int,input().split()))
towns = [0]*N
route = [0]
pre = 0
i = 0
towns[0] = 1
for _ in range(K):
    i = As[i]-1
    if towns[i]>0:
        pre = route.index(i)
        route = route[pre:]
        break
    route.append(i)
    towns[i] = 1
mod = len(route)
print(route[(K-pre)%mod]+1)

Submission status: Accepted

Solution code:
from sys import stdin
N,K=list(map(int,(stdin.readline().strip().split())))
A=list(map(int,(stdin.readline().strip().split())))
cycle=[1]
count=[0]*N
tele=0
count[tele] += 1
while(True):
    cycle.append(A[tele])
    tele=A[tele]-1
    count[tele] += 1
    if count[tele] == 2:
        break
a=cycle.index(tele+1)
if K<len(cycle):
    print(cycle[K])
else:
    num=len(cycle[a:-1])
    num=(K-len(cycle[:a]))%num
    print(cycle[num+len(cycle[:a])])

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

    pos = 1
    order = [-1] * (N+1)
    order[1] = 0
    s = [1]
    for i in range(1, N + 1):
        npos = A[pos-1]
        if order[npos] != -1:
            l = order[npos]
            c = i - order[npos]
            break

        order[npos] = i
        s.append(npos)
        pos = npos

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = []
ord = [-1 for i in range(n+1)]
v = 1
c = 1
l = 0
while ord[v] == -1:
    ord[v] = len(s)
    s.append(v)
    v = a[v-1]
c = len(s) - ord[v]
l = ord[v]
if k < l:
    print(s[k])
else:
    k -= l
    k %= c
    print(s[l+k])

Submission status: Accepted

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

def bin(arr,val):
    left,right = 0,len(arr)-1
    while left<=right:
        mid = (left+right)//2
        if arr[mid]==val: return 1
        elif arr[mid]<val: left = mid + 1
        else: right = mid - 1
    return 0

know = []
now = 1
while not bin(know, now):
    know.append(now)
    now = a[now]

loop_start = a[know[-1]]
for i,num in enumerate(know):
    if num == loop_start:
        loop_init = i
        loop = know[i:]
        break

#print(know,start,loop)

cnt = len(loop)
if k < len(know):
    ans = know[k]
else:
    ans = loop[(k-loop_init)%cnt]
# ans = loop[k%cnt]


print(ans)

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
vis_ti=[-1]*n
vis_at=[0]
now=0
for i in range(1,k+1):
  now=a[now]-1
  if vis_ti[now]>=0:
    bgn=vis_ti[now]
    print(vis_at[bgn+(k-bgn)%(i-bgn)]+1)
    sys.exit()
  vis_ti[now]=i
  vis_at.append(now)
print(vis_at[-1]+1)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A_dict = {i:a for i,a in enumerate(A,1)}

History = [1]
History_set = {1}
now = 1
for i in range(N):
    now = A_dict[now]
    if now not in History_set:
        History.append(now)
        History_set.add(now)
    else:
        break
#print(History,now)
if K < i:
    print(History[K])
else:
    e = History.index(now)
    #print(e)
    #print(History[e:])
    loop_num = len(History[e:])
    #print(loop_num)
    num = (K-e)%loop_num
    #print(num)
    print(History[e:][num])

Submission status: Accepted

Solution code:
def main():
    n, k, *a = map(int, open(0).read().split())
    a = [0] + a
    root = [1]
    visited = [False for _ in range(n+1)]
    nx = 1
    visited[1] = True

    step = 0
    while True:
        step += 1
        now = nx
        nx = a[now]
        if step == k:
            print(nx)
            break
        if visited[nx]:
            end = step
            start = root.index(nx)
            d = end - start
            r = k - step
            index = start + r % d
            print(root[index])
            break

        visited[nx] = True
        root.append(nx)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans1 = [1]
temp = 0
visit = [0]*(n+1)
visit[1] = 1
while(True):
    ans1 += [a[temp]]

    if visit[a[temp]] == 1:
        break

    visit[a[temp]] = 1
    temp = a[temp]-1


    if len(ans1) == m+1:
        print(ans1[len(ans1)-1])
        exit()


num1 = ans1.index(a[temp])
ans2 = ans1[num1:len(ans1)-1]

num = len(ans2)

print(ans2[(m-num1)%num])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
D = [0] * (n+1)
now = 1
for i in range(1, k+1):
    tmp = A[now-1]
    if not D[tmp]:
        now = tmp
        D[now] += i
    else:
        pre = D[tmp]
        loop = i - D[tmp]
        if loop>1:
            now=D.index((k - pre) % loop + pre)
        else:
            now=tmp
        break
print(now)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = []
x = [0] * n
x.append(0)
v = 1
c = 1
l = 0
while x[v] == 0:
    x[v] = len(s)
    s.append(v)
    v = a[v-1]
c = len(s) - x[v]
l = x[v]


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

Submission status: Accepted

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

def bin(arr,val):
    left,right = 0,len(arr)-1
    while left<=right:
        mid = (left+right)//2
        if arr[mid]==val: return 1
        elif arr[mid]<val: left = mid + 1
        else: right = mid - 1
    return 0

know = []
now = 1
while not bin(know, now):
    know.append(now)
    now = a[now]

start = a[know[-1]]
for i,num in enumerate(know):
    if num == start: loop = know[i:] ; break

#print(know,start,loop)

if k < len(know):
    ans = know[k]
else:
    k -= len(know)
    ans = loop[k%len(loop)]

print(ans)

Submission status: Accepted

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

li = [-1] * n
li[0] = 0
town = [0]
now = 0
flag = False

for i in range(k):
    now = a[now] - 1
    if li[now] != -1:
        s = li[now]
        break
    else:
        li[now] = i + 1
        town.append(now)
    if i == k-1:
        flag = True

if flag:
    print(now+1)
    exit()

town2 = town[s:]
m = len(town2)
l = len(town) - len(town2)

print(town2[(k - l) % m]+1)

Submission status: Accepted

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, k = input_to_int_map()
    a = {i + 1: int(val) for i, val in enumerate(input().split())}

    place = 1
    visit = {place}
    place_visits = [place]
    for i in range(k):
        place = a[place]
        if place in visit:
            left = place_visits.index(place)
            loop_list = place_visits[left:]
            return loop_list[(k - left) % len(loop_list)]
        else:
            visit.add(place)
            place_visits.append(place)

    return place


if __name__ == "__main__":
    print(main())

Submission status: Accepted

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

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

visited = [-1] * n
now = 0
visited[0] = 0
pre_roop = 0
pos = 0
i = 1
r = 1
while i <= k:
    next = a[now]
    #print('roop:',i,now+1,next+1)
    if visited[next] >= 0:
        r = i-visited[next]
        pre_roop = visited[next]
        pos = next
        #print(i,r,pre_roop,next)
        #print(visited)
        break
    else:
        visited[next] = i
        now = next
        #print(i,visited)
        i += 1

if i > k:
    print(now + 1)
else:
    l = (k - pre_roop) % r
    #print(l)
    i = 0
    p = pos
    while i < l:
        p = a[p]
        i +=1

    print(p+1)

Submission status: Accepted

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, k = input_to_int_map()
    a = {i + 1: int(val) for i, val in enumerate(input().split())}

    place = 1
    visit = {place}
    place_visits = [place]
    for i in range(k):
        place = a[place]
        if place in visit:
            left = place_visits.index(place)
            return place_visits[left + (k - left) % (i + 1 - left)]
        else:
            visit.add(place)
            place_visits.append(place)

    return place


if __name__ == "__main__":
    print(main())

Submission status: Accepted

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

history = []
is_visited = [False] * n

index = 0
cnt = 0
loop_start_city_index = 0
for i in range(k+1):
    if i == k:
        print(index+1)
        exit()

    if is_visited[index]:    # すでに訪れた街にきた
        loop_start_city_index = index
        break
    
    is_visited[index] = True
    history.append(index)
    index = a[index] - 1
    cnt += 1

from_start_to_loop_start = history.index(loop_start_city_index)
loop_length = len(history) - from_start_to_loop_start

print(history[from_start_to_loop_start + (k-from_start_to_loop_start)%loop_length] + 1)

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 = [0] + list(map(int, input().split()))
 
s = [0] * (N+1)
p = 1
h = []
for i in range(K):
    h.append(p)
    s[p] = 1
    p = A[p]

    if s[p] != 0:
        break

if i == K-1:
    print(p)
    exit()
else: 
    period = len(h) - h.index(p)
    rem = (K - h.index(p)) % period
    print(h[h.index(p):][rem])

Submission status: Accepted

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

visited = [False for _ in range(N)]
now = 0

cycle = []

while True:
    cycle.append(now)
    visited[now] = True
    now = A[now] - 1

    if visited[now]:
        break

total_len = len(cycle)

cycle_start = 0

for i in range(total_len):
    if cycle[i] == now:
        cycle_start = i
        break

cycle_len = total_len - cycle_start

if K < cycle_start:
    print(cycle[K] + 1)
else:
    print(cycle[cycle_start + (K - cycle_start) % cycle_len] + 1)

Submission status: Accepted

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

  current = 0
  if K < N:
    for i in range(K):
      current = A[current]
    print(current + 1)
    return True
  else:
    history = [False] * N
    load_map = []
    while True:
      load_map.append(current)
      current = A[current]
      if history[current]:
        loop_length = len( load_map[load_map.index(current):] )
        if loop_length == 0:
          print(current + 1)
          return True

        length_to_loop = len( load_map[:load_map.index(current)] )
        additional_way = (K-length_to_loop)%loop_length
        print(load_map[length_to_loop + additional_way] + 1)
        return True
      else:
        history[current] = True

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def main(N, K, A):
    i = 0   # 現在地
    lst_memo = []
    set_memo = set([])
    while i not in set_memo:
        lst_memo.append(i)
        set_memo.add(i)
        i = A[i] - 1    # pythonは一つずれる
    key = lst_memo.index(i)
    if K < key:
        print(lst_memo[K] + 1)
    else:
        roop = lst_memo[key:]
        print(roop[(K - key) % len(roop)] + 1)    # pythonは一つずれる


if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    main(N, K, A)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,k=mp()
a=lmp()
l=[]
i=0
ch=[0]*(n+1)
while True:
    if ch[i]==1:
        break
    else:
        ch[i]=1
        l.append(a[i])
        i=a[i]-1


x=l.index(a[i])
y=len(l)-x

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

Submission status: Accepted

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

done = [1]
donedic = {}
donedic[1] = 1
now = 1
for i in range(1,N+1):
    nexttown = A[now-1]
    #print(now, "->", nexttown)
    try:
        a = donedic[nexttown]
    except:
        donedic[nexttown] = 1
        done.append(nexttown)
        now = nexttown
    else:
        break

start = done.index(nexttown)
end = len(done)-1
before = start #ループに入るまでの転移数
loop = done[start:]

if K < before:
    saisyuu = done[K]
else:
    nokori = K-before
    n_loop = int(nokori/len(loop))
    loopfirst = done[start]
    hasuu = nokori%len(loop)
    saisyuu = loop[hasuu]
    #print("1から",before,"回転移して",loopfirst,"に到着します。")
    #print("その後、大きさ",len(loop),"のループを",n_loop,"回転移して",loopfirst,"にいます。")
    #print("その後、",hasuu,"回の転移をして",saisyuu,"に到着します。")
print(saisyuu)

Submission status: Accepted

Solution code:
import sys
N, K = map(int, input().split()) #N: 町の数, K: ちょうどこの回数でたどり着く町

visited = [False for _ in range(N)]

A = list(map(lambda n: int(n)-1, input().split()))
tmp = 0 #次に訪れる番号
visited[0] = True
#cnt = 0 #テレポートの回数
log = [0] #テレポートの記録

for i in range(1, K+1):
    tmp = A[tmp]
    if visited[tmp]:
        start = log.index(tmp)
        break

    visited[tmp] = True
    log.append(tmp)

if i == K:
    print(tmp+1)
else:
    loop = log[start:i+1]
    period = len(loop)
    remain = K - i
    print(loop[remain%period] + 1)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
n, k = map(int, input().split())
An = list(map(int, input().split()))
root = deque([1])
check = np.zeros(n, np.int)
check[0] = 1
i = 0
dup = 1
cnt = 1
for _ in range(n):
    temp = An[i]
    if check[temp-1] == 1:
        dup = temp
        break
    root.append(temp)
    check[temp-1] = 1
    i = temp - 1
    cnt += 1
index = root.index(dup)
if index >= k:
    print(root[k])
elif index == cnt - 1:
    print(dup)
else:
    print(root[(k-index) % (cnt-index) + index])

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
import numpy as np
link = set()
next = a[0]
link.add(1)
while next not in link:
    link.add(next)
    next = a[next-1]

# print(next)
link2 = set()
next2 = a[0]
link2.add(1)
while next not in link2:
    link2.add(next2)
    next2 = a[next2-1]

link2.remove(next)
ans = 0

rep = len(link) - len(link2)
# print(rep)
if (len(link2) == 0):
    p = k%rep
    # print('e')
    for i in range(p+rep):
        next = a[next-1]
elif(k > len(link2)):
    # print('f')
    p = (k-len(link2))%rep
    # print(p)
    # print(next)
    for i in range(p+rep):
        next = a[next-1]
else:
    # print('d')
    next = a[0]
    for i in range(k-1):
        next = a[next-1]
# print(next)
ans = next
# print(link,link2)
print(ans)