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 numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

dist = [0]*N
dist[0] = 0
cnt = 0
cp = 0
while cnt < N+10:
    if cnt == K:
        print(cp + 1)
        exit()
    np = A[cp]-1
    if np == cp: # ikidomari
        print(np+1)
        exit()
    elif dist[np]>0 or np == 0: # loop
        lstep = cnt - dist[np] + 1
        cp = np
        break
    dist[np] = cnt + 1
    cp = np
    cnt += 1

K -= dist[cp]
K %= lstep
cnt = 0
while cnt < K:
    np = A[cp]-1
    cp = np
    cnt += 1
    
print(cp+1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A=[0]+A
tmp=1
flist=[0 for i in range(N+1)]
blist=[]
for i in range(1,N+1):
  if flist[tmp]==0:
    flist[tmp]=i
    blist+=[tmp]
  else:
    ls=flist[tmp]
    le=i
    T=le-ls
    break
  tmp=A[tmp]
else:
  ls=1
  le=N+1
  T=N
Tlis=[]
for i in range(T):
  Tlis+=[tmp]
  tmp=A[tmp]
if K<=ls-1:
  print(blist[K])
else:
  K2=K-(ls-1)
  K2=K2%T
  print(blist[ls+K2-1])

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = [0] + list(map(int,input().split()))
#1 6 2 5 3 2 5 3 2 5 3
tmp = 1
list_tmp = [1]
set_tmp = set([1])
for n in range(K):
    #n回
    tmp = A[tmp]
    #print(tmp)
    if not tmp in set_tmp:
        set_tmp.add(tmp)
        list_tmp.append(tmp)
        ans = tmp
    else:
        
        list_loop = list_tmp[list_tmp.index(tmp):]
        
        ans = list_loop[(K-n-1)%len(list_loop)]
        break

print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

sys.setrecursionlimit(10 ** 7)

n, k = na()
a = na()

proc = [0] * n
def rec(i, cnt):
    if proc[i]:
        return (cnt, i)
    proc[i] = 1
    return rec(a[i] - 1, cnt + 1)

def rec2(i, arr):
    if proc[i] >= 2:
        return arr
    proc[i] += 1
    arr.append(i)
    return rec2(a[i] - 1, arr)

cnt, i = rec(0, 0)
arr = rec2(i, [])

nk = k
nk -= cnt - len(arr)
if nk < 0:
    ans = 0
    for i in range(k):
        ans = a[ans] - 1
    print(ans + 1)
else:
    print(arr[nk % len(arr)] + 1)

Submission status: Accepted

Solution code:
n,k=map(int, input().split())
A = list(map(int, input().split()))
A=[i-1 for i in A]
order=[-1]*n
order[0]=0
now=0
cnt=0
loop=-1
while True:
    now=A[now]
    cnt+=1
    if order[now]==-1:
        order[now]=cnt
    else:
        loop=now
        break

neworder=[]
for i in range(n):
    if i==loop:
        loop=[order[i],i]
    if order[i]!=-1:
        neworder.append([order[i],i])


neworder=sorted(neworder)
#print(neworder)
if k<=loop[0]:
    print(neworder[k%len(neworder)][1]+1)
else:
    k-=loop[0]
    neworder=neworder[loop[0]:]
    print(neworder[k%len(neworder)][1]+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = set()
s.add(1)
former = []
latter = []
temp = [1]
cur = a[0]
buf = 0

while True:
    if cur not in s:
        s.add(cur)
        temp.append(cur)
        cur = a[cur-1]
    else:
        buf = temp.index(cur)
        former = temp[:buf]
        latter = temp[buf:]
        break

# print('buf:', buf)
# print('former:', former)
# print('latter:', latter)

if len(latter) == 0:
    mod = k % len(temp)
    print(temp[mod])
    exit()

if k <= len(former):
    # print(former[k])
    print(temp[k])
else:
    # mod = k % len(latter)
    mod = (k-len(former)) % len(latter)
    # print('mod:', mod)
    # idx = mod - len(former)
    idx = mod
    
    print(latter[idx])

Submission status: Accepted

Solution code:
def main():
    N,K  = map(int, input().split()) 
    A = list(map(int, input().split()))  
    A.insert(0,0)
    B = [0]*(N+1)
    tel = 1
    telmae = 1

    for i in range(K):
        if B[tel] ==0:
            B[tel] = i
            telmae = tel
            tel = A[tel]
        else:
            temp =  i - B[tel]
            joyo = (K-B[tel]) % temp
            for j in range(joyo):
                telmae = tel
                tel = A[tel]
            print(tel)
            return


    print(tel)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
r = [0]*N
p = 0
q = 1 #現在地
for i in range(K):
    if i == K-1:
        print(A[q-1])
        exit()
    q = A[q-1] #次の町
    if r[q-1] == 0:
        p += 1
        r[q-1] += p       
    else:
        p += 1
        y = r[q-1]
        break
z = (K-y) % (p-y)
for i in range(N):
    if r[i] == y+z:
        print(i+1)

Submission status: Accepted

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

A = list(map(int, input().split()))
past = [0]*min(K, 2*10**5)
ps = set()
now = 1
step = 0
for i in range(K):
    past[i] = now
    ps.add(now)
    now = A[now-1]
    if now in ps:
        step += 1
        break

if step > 0:
    id = past.index(now)
    step = i+1 - id
    p = (K-id) % step
    now = past[id+p]

print(now)

Submission status: Accepted

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *

def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, K = In.ints()
A = [0]+In.ints()

cur = 1
seen = set()
seen.add(cur)
circleStart = 0

i = 0
while i<K:
    cur = A[cur]

    if cur not in seen:
        seen.add(cur)
    else:
        circleStart = cur
        i+=1
        break
    i+=1

if i == K:
    Out.int(cur)
else:
    K-=i

    dist = dict()
    dist[0] = circleStart
    cur_dist = 0
    longest = 0

    i = 0
    while i<K:
        cur_dist+=1

        cur = A[cur]

        if cur!=circleStart:
            dist[cur_dist] = cur
            longest = max(cur_dist, longest)
        else:
            i+=1
            break

        i+=1

    if i == K:
        Out.int(cur)
    else:
        K-=i
        Out.int(dist[K%(longest+1)])


######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Accepted

Solution code:
N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
doko = 0
for i in range(N):
    if A[doko] <= 0:
        saishou = min(A)
        loop = A[doko] - saishou + 1
        hajimarimade = A[doko]
        K += hajimarimade
        print(A.index(-1*(K % loop)+hajimarimade)+1)
        exit()
    if i == K:
        print(doko+1)
        exit()
    hoji = doko
    doko = A[doko] - 1
    A[hoji] = (-1)*i

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
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 operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
n,k=mii()
arr=limii()

visited=[0]*n

i=0

town=[0]

while visited[i]==0:
    visited[i]=1
    if i==0:
        visited[i]=1
    
    i=arr[i]-1

    town.append(i)

#town=[0, 5, 1, 4, 2, 1]
b=town.index(town[-1])
#at=[1, 4, 2]
at=deepcopy(town[b:-1])
#print(at,b)

if k<=b:
    print(town[k]+1)
    exit()

else:
    k-=b
    #print(k)
    a=k%len(at)
    #print(a)
    #print(at)
    print(at[a]+1)

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

start=0
finish=0

for i in range(1,n):
	if C[A[B[i-1]-1]-1]!=1:
		B.append(A[B[i-1]-1])
		C[A[B[i-1]-1]-1]+=1
	else:
		start=B.index(A[B[i-1]-1])
		finish=i
		break

roop=finish-start
line=sum(C)-roop

if line+(roop-1)>=k:
	print(B[k])
else:
	print(B[(k-line)%roop+line])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
chk=[False]*n
x=0
visit=[0]
chk[x]=True
while chk:
    x=a[x]-1
    if chk[x]:
        break
    else:
        visit.append(x)
        chk[x]=True
l1=0
while visit[l1]!=x:
    l1+=1
l2=len(visit)-l1
if k>=l1:
    print(visit[l1+((k-l1)%l2)]+1)
else:
    print(visit[k]+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited_set = set([1])
visited_list = [1]
i = 0
loop_pos = 0
for _ in range(len(A)):
    if A[i] in visited_set:
        while A[i] != visited_list[loop_pos]:
            loop_pos += 1
        break
    visited_set.add(A[i])
    visited_list.append(A[i])
    i = A[i] - 1
if K < loop_pos:
    print(visited_list[K])
else:
    loop_len = len(visited_list) - loop_pos
    K -= loop_pos
    pos = loop_pos + (K % loop_len)
    print(visited_list[pos])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
c=2
t=0
path=[]
s=set()
cycle=[]
while(c<=k):
    if a[t] in s:
        #print(path.index(a[t]),a[t])
        cycle=path[path.index(a[t]):]
        k-=c-1
        break
    path.append(a[t])
    s.add(a[t])
    t=a[t]-1
    c+=1
if cycle==[]:
    print(a[t])
else:
    print(cycle[k%len(cycle)])

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/abc167/tasks/abc167_d
"""
import numpy as np
from numba import jit


@jit(nopython=True, parallel=False)
def calc(N: int, K: int, A: np.ndarray) -> int:
    current_pos = 0
    first_sight = np.zeros((N,), dtype=np.int64) - 1
    consumed = 0
    first_sight[0] = 0
    while consumed < K:
        next_pos = A[current_pos] - 1
        consumed += 1
        current_pos = next_pos

        if first_sight[next_pos] == -1:
            first_sight[next_pos] = consumed
        else:
            loop_size = consumed - first_sight[current_pos]
            if loop_size <= K - consumed:
                remain = (K - consumed) % loop_size
                consumed = K - remain
    return current_pos + 1


def load_input_as_int_array() -> np.ndarray:
    return np.array([int(v) for v in input().split(" ")], dtype=np.int64)


def main() -> None:
    N, K = load_input_as_int_array()
    A = load_input_as_int_array()
    result = calc(N, K, A)
    print(result)
    # print("Yes" if result else "No")


main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
seq=list(map(int,input().split()))
v=[False]*n
path=[1]
i=0
v[0]=True
while True:
        if v[seq[i]-1]==False:
                v[seq[i]-1]=True
                path.append(seq[i])
                i=seq[i]-1
                
        else:
                t=seq[i]
                break

ind=path.index(t)
path2=path[ind:]
path1=path[:ind]
x=len(path1)
if k>=x:
        k-=x
        #print(t,ind,path1,path2)
        print(path2[(k%len(path2))])

else:
        print(path1[k])

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
visit = [-1 for i in range(n)]
root = []
now = 1
length = 0
root.append(now)
if k > n:
    for i in range(n):
        if visit[now - 1] != 1:
            visit[now - 1] = 1
            now = a[now - 1]
            root.append(now)
            length += 1
        else:break
    start = 0
    for i in range(n):
        if root[i] == now:
            start = i
            break
    length -= start
    k -= start
    k %= length
    ans = root[start + k]
    print(ans)
else:
    for i in range(k):
        now = a[now - 1]
    print(now)

Submission status: Accepted

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

check = {}
i = 0
number = []
next = a[0]
start = 0

for i in range(1,n+1):
    if next in check:
        start = number.index(next)
        rep = number[number.index(next):]
        break
    else:
        check[next] = 1
        number.append(next)
        next = a[next-1]

if k <= start:
    print(number[k-1])
else:
    c = len(rep)
    print(rep[(k-start-1)%c])

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
for tt in range(1):
	n,k = map(int,input().split())
	l = list(map(int,input().split()))
	cycle = []
	s = set()
	pos = 0
	while True:
		pos = l[pos]-1
		if pos in s:
			start = cycle.index(pos+1)
			break
		cycle.append(pos+1)
		s.add(pos)
	new = cycle[start:]
	size = len(cycle) - len(new)

	if k<=size:
		print(cycle[k-1])
	else:
		k-=size
		print(new[(k-1)%len(new)])

Submission status: Accepted

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

R = []
done = set()
todo = [0]
done = set()
bp = None
while todo:
    p = todo.pop()
    R.append(p)
    done.add(p)
    np = A[p]
    if np in done:
        bp = np
    else:
        todo.append(np)
b = R.index(bp)
if K < b:
    ans = R[K] + 1
else:
    K -= b
    R = R[b:]
    ans = R[K%len(R)] + 1
print(ans)

Submission status: Accepted

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

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

visited=[0]*n
if k<=n:
    now=0
    nex=0
    loop_start=0
    target=0

    for i in range(n):
        now=nex
        visited[now]+=1
        nex=a[now]-1
        if i+1==k:
            print(nex+1)
            exit()
now=0
nex=0
loop_start=0
target=0
lis=[]
s=set()
flag=False

for i in range(2*n):
    now=nex
    visited[now]+=1
    nex=a[now]-1
    if flag:
        if now+1 not in s:
           lis.append(now+1)
           s.add(now+1)
           continue
        else:
            break
    if visited[now]==2:
        loop_start=i
        target=now+1
        lis.append(now+1)
        s.add(now+1)
        flag=True


dif=len(lis)
first=loop_start-dif
k-=first
print(lis[k%dif])

Submission status: Accepted

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

C = [0]*N
C[0] = 1
place = 1
i = 1
while True:
  place = A[place-1]
  if C[place-1] == 0:
    i += 1
    C[place-1] = i
  else:
    break
if K <= i-1:
  print(C.index(K+1) +1)
  exit()
K -= i-1
loop = i + 1 -C[place-1]
K %= loop
if K == 0:
  print(C.index(i) +1)
else:
  print(C.index(K-1 + C[place-1]) +1)

Submission status: Accepted

Solution code:
from sys import stdin
n,k = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(x) for x in stdin.readline().rstrip().split()]
b = [-1]*n
b[0] = 0
tf = True
t = 1
g = 0
m = 0
while k > 0:
    k -= 1
    if b[a[g]-1] == -1:
        b[a[g]-1] = t
    else:
        m = b[a[g]-1]
        g = a[g]-1
        break
    t += 1
    g = a[g]-1
mo = t-m
k = k % mo
while k > 0:
    g = a[g]-1
    k -= 1
print(g+1)

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

n,k = MI()
a = LI()

b = [0]
visited = [0]*n
for _ in range(n):
    if visited[a[b[-1]]-1] == 1:
        break
    visited[a[b[-1]]-1] = 1
    b.append(a[b[-1]]-1)
first = b.index(a[b[-1]]-1)
second = len(b)
if k <= first:
    print(b[k]+1)
else:
    print(b[(k-first)%(second-first)+first]+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
a = list(map(int, input().split()))

posit = [0]*n
arrive_time = [0]*n

loop_len = 0
preloop_len = 0

post_posit = 1
for i in range(n):
    next_posit = a[post_posit-1]
    # print("PostPosit: " + str(post_posit) + ", NextPosit: " + str(next_posit))
    if arrive_time[next_posit-1] == 0:
        arrive_time[next_posit-1] = i+1
        posit[i] = next_posit
        post_posit = next_posit
    else:
        preloop_len = arrive_time[next_posit-1]
        loop_len = i+1 - preloop_len
        # print("Already Visited")
        # print("PreloopLen: " + str(preloop_len) + ", LoopLen: " + str(loop_len))
        break

if k <= preloop_len:
    print(posit[k-1])
else:
    move_in_loop = k-preloop_len
    posit_in_loop = move_in_loop % loop_len
    # print(posit_in_loop)
    print(posit[preloop_len+posit_in_loop-1])

Submission status: Accepted

Solution code:
#coding: utf-8
from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [False for _ in range(N)]
state = 0
heiro = [0]
visited[0] = True
while True:
    state = A[state]-1
    heiro.append(state)
    # print("state", state, A[state])
    if visited[state]:
        break
    visited[state] = True
if K < len(heiro):
    print(heiro[K] + 1)
else:
    cnter = dict(Counter(heiro))
    for k in cnter.keys():
        if cnter[k] == 2:
            v = k
            break
    idx = heiro.index(v)
    K -= idx
    # ans = heiro[idx:-1][K % (len(heiro) - idx - 1)] + 1
    ans = heiro[idx:-1][K % len(heiro[idx:-1])] + 1
    print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
test_pos = 1
sub = 0
loop = 0
city = [0 for i in range(n)]
while True:
    test_pos = a[test_pos-1]
    city[test_pos-1] += 1
    sub += 1
    if city[test_pos-1] == 2:
        loop_start = test_pos
        break

while True:
    test_pos = a[test_pos-1]
    loop += 1
    if test_pos == loop_start:
        break
if k > sub:
    k -= sub
    k %= loop
    pos = loop_start
    for i in range(k):
        pos = a[pos-1]
    print(pos)
else:
    pos = 1
    for i in range(k):
        pos = a[pos - 1]
    print(pos)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=[i-1 for i in a]
memo = [1]+[0]*(n-1)
telep=0
now=0
point=-1
while telep<k:
  telep+=1
  now=a[now]
  if memo[now]==0:
    memo[now]+=1
  else:
    point=now
    break
if point==-1:
  print(now+1)
  exit()
count=0
now=0
t=-1
while True:
  if now==point and t==-1:
    t=0
  now=a[now]
  if t==-1:
    count+=1
  if t>=0:
    t+=1
  if now==point and t!=-1:
    cycle=t
    break
l=(k-count)%cycle
k=count+l
telep=0
now=0
while telep<k:
  telep+=1
  now=a[now]
print(now+1)

Submission status: Accepted

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

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

tp = []
current = 1
tp.append(1)
if k > n:
  for i in range(n):
    current = an[current-1]
    tp.append(current)
  tps = len(set(tp))
  tp = tp[0:tps]
    
  kurikaesi_start = an[tp[-1]-1]
  start_ind = tp.index(kurikaesi_start)
  num = (k - start_ind) % (tps - start_ind)
  
  print(tp[start_ind+num])
else:
  for i in range(k):
    current = an[current-1]
  print(current)

Submission status: Accepted

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

visited = [-1] * n
order = []
idx = 0
num = 0
while True:
  if not visited[idx] == -1:
    break
  visited[idx] = num
  num += 1
  order.append(idx)
  idx = alist[idx]-1
if visited[idx] == 0:
  print(order[k%len(order)]+1)
else:
  kotei = order[:visited[idx]]
  kurikaesi = order[visited[idx]:]
  if k <= len(kotei):
    print(order[k]+1)
  else:
    k -= len(kotei)
    print(kurikaesi[k%len(kurikaesi)]+1)

Submission status: Accepted

Solution code:
def main():
    n, k = tuple([int(e) for e in input().split()])
    arr = [0] + [int(e) for e in input().split()]

    seen = set()
    actual = 1
    seen.add(1)
    pos = [1]
    mp = {1:1}
    while k > 0:
        actual = arr[actual]
        k -= 1
        if actual in seen:
            break
        seen.add(actual)
        pos.append(actual)
        mp[actual] = len(pos)

    c = 1 + len(pos) - mp[actual]
    k = k % c
    print(pos[mp[actual] + k - 1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [i-1 for i in a]
v = [-1 for _ in range(n)]
p = 0
x = 0
c = 0
while k > 0 and v[x] < 0:
    v[x] = p+1
    p = v[x]
    x = a[x]
    c += 1
    k -= 1

z = c-v[x]+1
k = k%z

while k > 0:
    k -= 1
    x = a[x]
print(x+1)

Submission status: Accepted

Solution code:
import numpy as np

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

A = np.array(list(map(int, input().split()))) - 1

roop = [-1]*N
is_visited = [-1]*N

roop[0] = 0
is_visited[0] = 0

for i in range(N-1):
    if is_visited[A[roop[i]]] >= 0:
        for idx, j in enumerate(roop):
            if j == A[roop[i]]:
                r = i+1-idx
                print(roop[idx + (K - idx) % r] + 1)
                exit()

    elif i == K:
        print(roop[i] + 1)
        exit()

    roop[i+1] =  A[roop[i]]
    is_visited[roop[i]] = i

Submission status: Accepted

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


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

    first_vis = dict() #key = machi, value = visited k
    loop = dict()
    k = 0
    c_cur = 1
    while k < K:
        #print('k = {} at {}, vis={}, loop={}'.format(k, c_cur, first_vis, loop))
        if c_cur in loop:
            len_loop = loop[c_cur]
            if k + len_loop <= K:
                k += len_loop * ((K - k) // len_loop)
                continue

        if c_cur in first_vis:
            loop[c_cur] = k - first_vis[c_cur]
        else:
            first_vis[c_cur] = k
        c_cur = A[c_cur-1]
        k += 1
    print(c_cur)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = lambda: sys.stdin.readline()


def cin_int_list():
    return [int(x) for x in input().split()]


def cin_int_iter():
    return (int(x) for x in input().split())


def cin_int():
    return int(input())


def cout_int_iter(a):
    print(' '.join(map(str, a)))


def iota(n, start=0):
    return list(range(start, n))


def cin_digits_list():
    return [ord(x) - ord('0') for x in input()]


def main():
    n, k = cin_int_iter()

    g = {}

    for u, x in enumerate(cin_int_list()):
        v = x - 1
        g[u] = v

    visited = set()

    u = 0
    while u not in visited:
        visited.add(u)
        u = g[u]

    cycle_starts = u

    u = cycle_starts
    cycle = []
    while True:
        cycle.append(u)
        u = g[u]

        if u == cycle_starts:
            break

    before_cycle = []
    u = 0

    while u != cycle_starts:
        before_cycle.append(u)
        u = g[u]

    if k < len(before_cycle):
        print(before_cycle[k] + 1)
        return

    if before_cycle:
        k -= len(before_cycle)

    print(cycle[k % len(cycle)] + 1)




main()


"""
6 1
6 5 2 5 3 2

6 2
6 5 2 5 3 2

6 3
6 5 2 5 3 2

6 4
6 5 2 5 3 2

6 6
6 5 2 5 3 2

6 5
6 5 2 5 3 2


no cycle

4 1
2 3 4 5

4 111111111111111111
2 3 4 1

1 111111111111111111
1

2 1999999999999999999
2 1

3 99999999999999999999
2 3 2

3 99999999999999999999
2 3 4
"""

Submission status: Accepted

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

is_passed_list = [None] + [False] * N

first_find_indexes = [None] + [-1] * N

root = []

i = 1
j = 0
k = K
while k > 0:
    if not is_passed_list[i]:
        is_passed_list[i] = True
        first_find_indexes[i] = j
        B.append(A[i])

        i = A[i]
    else:
        break
    j += 1
    k -= 1

if k > 0:
    cur_index = j
    first_find_index = first_find_indexes[i]

    i = (K - first_find_index) % (cur_index - first_find_index)
    print(B[first_find_index:cur_index][i])
else:
    print(B[j])

Submission status: Accepted

Solution code:
n,k=list(map(int,input().split()))
lis=list(map(int,input().split()))
for i in range(len(lis)):
    lis[i]-=1
# print(a[:-1])
count=0
start=0
vis=[0]*len(lis)
trav=[0]*(len(lis)+1)
while(vis[start]==0):
    vis[start]=count+1
    trav[count]=start
    start=lis[start]
    count+=1
start2=0
flag=0
rount=count
while(start!=start2):
    start2=lis[start2]
    k-=1
    count-=1
    if k==0:
        print(start2+1)
        flag=1
if not flag:
    if k==0:
        k=rount
    t=k%count
    for i in range(t):
        start2=lis[start2]
    print(start2+1)

Submission status: Accepted

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

lc = [1]
lcnt = [1]
lcnt.extend([0]*(N-1))

i = 1
while lcnt[lc[i-1]-1] == 1:
    if i == N:
        break
    else:
        lc.append(la[lc[i-1]-1])
        lcnt[la[lc[i-1]-1]-1] += 1
        i += 1

lpst = lc.index(lc[-1])
lpnum = len(lc) - lpst - 1
if K <= lpst:
    loclst = K
elif lpnum == 0:
    loclst = lpst
else:
    loclst = (K - lpst) % lpnum + lpst

print(lc[loclst])

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    n, k = list(map(int, input().split()))
    A = list(map(int, stdin.readline().split()))
    roots = [1]
    position = 0
    for _ in range(n):
        position = A[roots[-1]-1]
        A[roots[-1]-1] = - position
        if position < 0:
            break
        roots.append(position)

    x = roots.index(-position)
    y = len(roots) - x

    if k <= x:
        print(roots[k])
    elif k > x:
        print(roots[x + ((k-x) % y)])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

A = [0] + A

i = 1
n = 1
past = [0] * (N+i)
while K:
    if past[i] != 0:
        #print("twice",i , n, past[i])
        sub = n - past[i]
        K = K % sub
        break

    past[i] = n
    #print(i, n, past[i])
    i = A[i]
    n += 1
    K -= 1
    
while K:
    i = A[i]
    K -= 1
    
print(i)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
dir = a[0]
hash_a = [0 for _ in range(n)]
hash_a[0] = 1
cnt = 0
two = 0
while True:
    k -= 1
    cnt += 1
    if k == 0:
        break
    dir = a[dir - 1]
    if hash_a[dir - 1] == 0 or hash_a[dir - 1] == 1 or hash_a[dir - 1] == 2:
        hash_a[dir - 1] += 1
        if hash_a[dir - 1] == 2:
            two += 1
    elif hash_a[dir - 1] == 3:
        k = (k + cnt) - (cnt - (two * 2))
        k %= two
        hash_a = [-k for _ in range(n)]
print(dir)