Problem:


Score: 400 points

Problem Statement

The Kingdom of Takahashi has N towns, numbered 1 through N.

There is one teleporter in each town. The teleporter in Town i (1 \leq i \leq N) sends you to Town A_i.

Takahashi, the king, loves the positive integer K. The selfish king wonders what town he will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Help the king by writing a program that answers this question.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

1 \leq K \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the integer representing the town the king will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Sample Input 1

4 5
3 2 4 1

Sample Output 1

4

If we start at Town 1 and use the teleporter 5 times, our travel will be as follows: 1 \to 3 \to 4 \to 1 \to 3 \to 4.

Sample Input 2

6 727202214173249351
6 5 2 5 3 2

Sample Output 2

2



Sample input:
4 5
3 2 4 1


Sample output:
4

Submission status: Accepted

Solution code:
import sys
N, K = [int(x) for x in input().split()]
A = [None] + [int(x) for x in input().split()]

visited = [False] * (N + 1)
by = [None] * (N + 1)

visited[1] = True
by[1] = 0 # 0番目のテレポーテーションで到着

i = 1
tel = 0
for tel in range(1, N + 2):
    i = A[i]
    if tel == K:
        print(i)
        sys.exit(0)
    if visited[i]:
        cycle = tel - by[i]
        offset = by[i]
        break
    visited[i] = True
    by[i] = tel

# iからスタートして、M回移動した地点
M = (K - offset) % cycle

for j in range(M):
    i = A[i]

print(i)

Submission status: Accepted

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

flag = [False]*N
from collections import deque

q = deque([])
q.append(0)
flag[0] = True
now = 0
while True:
  now = A[now]
  if flag[now]:
    break
  else:
    flag[now] = True
    q.append(now)
    
l = list(q)
if K<len(l):
  print(l[K]+1)

else:
  for i,x in enumerate(l):
    if x==now:
      l = l[i:]
      K -= i
      break
  
  print(l[K%len(l)]+1)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    n, k = LI()
    A = LI_()
    visited = set()
    path = []
    cur = 0
    while True:
        visited.add(cur)
        path.append(cur)
        cur = A[cur]
        if cur in visited:
            break
    for i, city in enumerate(path):
        if cur == city:
            loop_st = i
            break
    loop_en = len(path) - 1
    n_loop = loop_en - loop_st + 1
    
    if k > loop_st:
        k -= loop_st
        k %= n_loop
        print(path[loop_st + k] + 1)
    else:
        print(path[k] + 1)

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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


cnt = 0
path = []
visited = [False]*n
junban = [-1]*n

now = 0
while True:

    if visited[now]:
        loopstart = now
        break
    else:
        path.append(now)
        junban[now] = cnt
        visited[now]=True
        loopend = now
        cnt+=1
        now = a[now]-1

loopsize = junban[loopend] - junban[loopstart] + 1

if k < junban[loopend]:
    print(path[k]+1)
else:
    ans = path[junban[loopstart]+ (k-junban[loopstart])%loopsize]
    print(ans+1)

Submission status: Accepted

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

d = {1:0}
pre_a = 0
a = 1
c = 0
while K:
    K -= 1
    next_a = A[a]
    c += 1
    if next_a in d:
        idx = d[next_a]
        n = len(d)
        K %= (n - idx)
        K += 1
        break
    else:
        d[next_a] = c
        pre_a = a
        a = next_a

while K:
    pre_a = a
    a = A[a]
    K -= 1

print(a)

Submission status: Accepted

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

for i in range(N):
    A[i] -= 1

path = [0]
went = {0: 0}
while True:
    town = A[path[-1]]
    if town in went.keys():
        break
    else:
        went[town] = len(path)
        path.append(town)
start = went[town]
if K < len(path):
    ans = path[K]
else:
    ans = path[(K - start) % (len(path) - start) + start]
ans += 1
print(ans)
pass

Submission status: Accepted

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

cur_town = 1
visited = {1: 1}
before_loop = [1]
cnt = 2
while True:
    cur_town = A[cur_town - 1]
    if cur_town in visited:
        break
    visited[cur_town] = cnt
    before_loop.append(cur_town)
    cnt += 1

# loop に入る前の回数
before_loop_cnt = visited[cur_town] - 1
if K < before_loop_cnt:
    print(before_loop[K])
else:
    loop_lst = before_loop[visited[cur_town] - 1 :]
    print(loop_lst[(K - before_loop_cnt) % len(loop_lst)])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.jump = None
    self.step = None


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

  for i, a in enumerate(map(int, input().split())):
    nodes[i].jump = nodes[a - 1]

  current = nodes[0]
  current.step = 0

  while current.jump.step is None:
    current.jump.step = current.step + 1
    current = current.jump

  loop = current.step - current.jump.step + 1

  if K >= current.jump.step:
    remain = (K - current.jump.step) % loop
    current = current.jump
  else:
    remain = K
    current = nodes[0]

  for _ in range(remain):
    current = current.jump

  print(current.idx + 1)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
v=[0]*n
v[0]=1
i=1
l=[1]
while True:
  i=a[i-1]
  l.append(i)
  if v[i-1]:
    t=i
    break
  else:
    v[i-1]=1
pre=l.index(t)
loop=len(l)-pre-1
if pre>=k:
  print(l[k])
else:
  k=k-pre
  mod=k%loop
  print(l[pre+mod])

Submission status: Accepted

Solution code:
# D - Teleporter

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

# なげなわ検出
p = [1]
hash = {1: 0}  # p[hash[1]] == 1
while True:
    x = a[p[-1] - 1]
    if x in hash:
        break
    hash[x] = len(p)  # p[hash[x]] == x
    p.append(x)

# 0, 1, 2, ..., (hash[x], ..., len(p)-1)*
looplen = len(p) - hash[x]
if k < len(p):
    print(p[k])
else:
    print(p[(k - len(p)) % looplen + hash[x]])

Submission status: Accepted

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

kyori = [-1]*n

now = 0;kyori[now] = 0
jyunkan = 0;v = 0
for i in range(n):
    tugi = a[now] - 1
    if kyori[tugi] != -1:
        jyunkan = kyori[now] + 1
        v = tugi
        break
    kyori[tugi] = kyori[now] + 1
    if kyori[tugi] == k:
        print(tugi + 1)
        sys.exit()
    now = tugi
k -= kyori[v]
mawaru = jyunkan - kyori[v]
amari = k % mawaru

now = v;cunt = 0
for i in range(amari):
    now = a[now] - 1
    
print(now + 1)

Submission status: Accepted

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

visited = [-1] * len(a)

now = 0
visited[0] = 0
while k > 0:
    k -= 1
    old = now
    now = a[now]
    if visited[now] != -1:
        p = visited[old] + 1 - visited[now]
        k %= p
        visited = [-1] * len(a)
    else:
        visited[now] = visited[old] + 1
print(now + 1)

Submission status: Accepted

Solution code:
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())


    
n,m=mi()
a=li()
x=[]
c=1
k=0
m1={}
m1[1]=k
k+=1
x1=0
while(1):
    if a[c-1] in m1:
        x1=a[c-1]
        break
    m1[a[c-1]]=k
    k+=1
    c=a[c-1]
if(m<k):
    for i in m1.keys():
        if m1[i]==m:
            print(i)
            break
else:
    m-=k
    m1={}
    m1[x1]=0
    k=1
    c=a[c-1]
    while(1):
        if a[c-1] in m1:
            break
        m1[a[c-1]]=k
        k+=1
        c=a[c-1]
    m%=k
    for i in m1.keys():
        if m1[i]==m:
            print(i)
            break

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
a=[x-1 for x in a]
dist=[0]*n
cur=0
while True:
	nxt=a[cur]
	if k==0:
		print(cur+1)
		break
	if dist[nxt]:
		k=(k-dist[nxt])%(dist[cur]-dist[nxt]+1)+dist[nxt]
		k-=1
		dist=[0]*n
		cur=nxt
	else:
		k-=1
		dist[nxt]=dist[cur]+1
		cur=nxt

Submission status: Accepted

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

x = 0
l = [0]
s = set([0])
flag = False
for i in range(N):
    x = A[x]-1
    if x in s:
        break
    s.add(x)
    l.append(x)

for i in range(len(l)):
    if l[i]==x:
        break

y = len(l)
z = i

if K<len(l):
    print(l[K]+1)
else:
    #print(z)
    #print(y)
    #
    #print((K-z)%(y-z))
    #print(z)
    print(l[z + (K-z)%(y-z)]+1)

Submission status: Accepted

Solution code:
nk = input().split()
n = int(nk[0])
k = int(nk[1])

a = list(map(lambda x:int(x), input().split()))

visited_i = [-1]*n

i = 0
visited_i[0] = 0

loops = -1
loopn = -1

nowp = 0
while i < k:
  i += 1
  nowp = a[nowp]-1
  #print(nowp)
  
  if visited_i[nowp] != -1 and loops == -1:
    loops = nowp
    loopn = i-visited_i[nowp]
    
    #print("loopn = "+str(loopn), end = " ")
    #print(nowp)
    
    k = (k-i)% loopn
    i = 0
    #print("k = "+str(k))
  else:
  	visited_i[nowp] = i

#print(visited_i)
print(nowp+1)

Submission status: Accepted

Solution code:
#0や1のケースに注意
#index out of range

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    tugi = [0]*n
    tugi[0] = 1
    s = 0
    cnt = 1
    while 1:
        s = a[s] - 1
        cnt += 1
        if tugi[s] > 0:
            break
        tugi[s] = cnt
    cnt -= 1
    if cnt-1 >= k:
        for i in range(n):
            if tugi[i]==k+1:
                print(i+1)
    else:
        #s=ループスタート
        loop = [s]
        for i in range(cnt - (tugi[s]-1)-1):
            s = a[s] - 1
            loop.append(s)
        s = a[s]-1
        amari = (k-(tugi[s]-1)) % (len(loop))
        print(loop[amari]+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

seen[0] = 0

cur = 1

fin = 0

for step in range(1, n+3):
    n_c = a[cur-1]
    if step == k:
        fin = 1
        print(n_c)
        break
    if seen[n_c-1] >= 0:
        loop = step - seen[n_c-1]
        before = seen[n_c-1]
        start = n_c
        break
    seen[n_c-1] = step
    cur = n_c

if not fin:
    if loop == 0:
        print(start)
    else:
        rem = k - before
        ama = rem % loop
        cur = start
        for i in range(ama):
            n_c = a[cur-1]
            cur = n_c
        print(cur)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
*A, = map(int, input().split())
s = 0
l = 0
n = 0
h = [0]*N
while True:
    h[s] = l
    s = A[s]-1
    l += 1
    if h[s]:
        n = l-h[s]
        break

if K < h[s]:
    s = 0
else:
    K -= h[s]
    K = K % n

while K > 0:
    s = A[s]-1
    K = K-1
print(s+1)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    import numpy as np
    # import math
    # import random
    input = stdin.readline


    n, k = map(int, input().split())
    aa = [0]+list(map(int, input().split()))
    arrive = [1]
    next = aa[1]
    visited = set([1])
    if next == 1:
        print(1)
        exit()
    while not (next in visited):
        arrive.append(next)
        visited.add(next)
        next = aa[next]
    num_town = len(arrive)
    start_index = arrive.index(next)
    if k < num_town:
        print(arrive[k])
        exit()
    print(arrive[start_index+(k-start_index)%(num_town-start_index)])

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
now = 1
used = [0]*n
for i in range(1,2*n):
    now = a[now-1]
    if (used[now-1]==0):
        used[now-1]=i
    else:
        bef = used[now-1]
        loop = i-used[now-1]
        break
if (bef>=k):
    print(used.index(k)+1)
else:
    over = (k-bef)%loop
    #print(bef,over,loop,used)
    print(used.index(bef+over)+1)

Submission status: Accepted

Solution code:
def main():
    N, K = [int(_n) for _n in input().split()]
    A = [int(_n)-1 for _n in input().split()]
    visited = [-1] * N
    loop = []
    current = 0
    siz = 0
    visited[0] = 0
    loop.append(0)
    start = 0
    while True:
        current = A[current]
        siz += 1
        if visited[current] != -1:
            start = visited[current]
            break
        visited[current] = siz
        # print(visited)
        loop.append(current)
    #     print(loop)
    # print(start)
    if K <= start:
        print(loop[K]+1)
    else:
        print(loop[start + (K-start)%(len(loop)-start)]+1)

    
main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = {1: 0}
log = {0: 1}
current = 1
move = 0
roop_exist = False
while True:
    move += 1
    current = A[current - 1]
    if current in visited:
        roop = move - visited[current]
        roop_start = current
        roop_exist = True
        break
    if move == K:
        print(current)
        break
    visited[current] = move
    log[move] = current
if roop_exist:
    remain = (K - move) % roop
    print(log[visited[roop_start] + remain])

Submission status: Accepted

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

now = 0
cnt[now] += 1
root_to_loop = [now]
while cnt[now] != 2:
    now = a[now] - 1
    root_to_loop.append(now)
    cnt[now] += 1

loop = [now]
while cnt[now] != 3:
    now = a[now] - 1
    loop.append(now)
    cnt[now] += 1

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
*A, = map(int, input().split())
visited = [False] * N
towns = []
now = 0
length = 0
while not visited[now] and K > 0:
    visited[now] = True
    towns.append(now + 1)
    length += 1
    K -= 1
    now = A[now] - 1
if K == 0: print(now + 1)
else:
    idx = towns.index(now + 1)
    length -= idx
    print(towns[idx:][K % length])

Submission status: Accepted

Solution code:
# 同じ町に二回到達したときに、前回たどり着いたときとの差を観る

import sys

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

Flag = [0] * (N+1)
X = [0] * (N + 1)
X[0] = 1

for i in range(1, K + 1):
    if Flag[A[X[i - 1] - 1]] == 1:
        # 前回の位置を取得
        hoge = X.index(A[X[i - 1] - 1])
        print(X[hoge + ((K - hoge) % ((i-1) - hoge + 1))])
        sys.exit()
    else:
        X[i] = A[X[i - 1] - 1]
        Flag[A[X[i - 1] - 1]] = 1


print(X[K])

Submission status: Accepted

Solution code:
inf=10**15
n,k=map(int,input().split())
a=list(map(int,input().split()))
num=[inf]*n
num[0]=0
now=0
for i in range(n):
	now=a[now]-1
	if num[now]==inf:
		num[now]=i+1
	else:
		loop=i+1-num[now]
e=-1
for i in range(n):
	if num[i]!=inf:
		if e<num[i]:
			e=num[i]
if e>=k:
	for i in range(n):
		if num[i]==k:
			print(i+1)
			break
else:
	k-=e
	k%=loop
	for i in range(n):
		if num[i]==e:
			now=i
			break
	for i in range(k):
		now=a[now]-1
	print(now+1)

Submission status: Accepted

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

A = [a-1 for a in A]

g = [[] for i in range(n)]
for i, a in enumerate(A):
    g[i].append(a)

s = []
visit = [-1]*n
s.append(0)
visit[0] = 0
while s:
    v = s.pop()
    for u in g[v]:
        if visit[u] == -1:
            visit[u] = visit[v]+1
            s.append(u)
        else:
            temp = visit[u]
#print(temp)
#print(visit)
d = max(visit)-temp+1
#print(d)
if k < temp:
    for i in range(n):
        if visit[i] == k:
            print(i+1)
            exit()
else:
    q, r = divmod(k-temp, d)
    for i in range(n):
        if visit[i]-temp == r:
            print(i+1)
            exit()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A = [int(c) -1 for c in input().split()]

is_used = [False for _ in range(N)]
cycle_head, cycle_tail = -1, -1
cur, k = 0, 0
while True:
    if k == K:
        print(cur+1)
        exit()

    next_cur = A[cur]
    if is_used[next_cur]:
        head = next_cur
        tail = cur
        break

    else:
        is_used[cur] = True
        cur = next_cur
        k += 1


before_cycle = 0
len_cycle = 1
cur = 0
while cur != head:
    before_cycle += 1
    cur = A[cur]

while cur != tail:
    len_cycle += 1
    cur = A[cur]


k = (K - before_cycle) % len_cycle
cur = head
while k != 0:
    k -= 1
    cur = A[cur]
print(cur+1)

Submission status: Accepted

Solution code:
import collections

n,k=map(int,input().split())
a=list(map(int,input().split()))
L=[1]
count=1
nowt=1
roops=0
v=[False]*n
while(True):
    if v[a[nowt-1]-1]==True:
        roops=a[nowt-1]
        break

    L.append(a[nowt-1])
    v[a[nowt-1]-1]=True
    nowt=a[nowt-1]
    count+=1

play=0
for i in range(len(L)):
    if L[i]==roops:
        break
    play+=1

rooplen=len(L)-play

if k<play:
    print(L[k])
    exit() 

ans=L[play+(k-play)%rooplen]

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,k = na()
    As = [a-1 for a in na()]
    memo = [[0]] + [[] for _ in range(n-1)]#何回目にそこを訪れたか
    now = 0
    time = 0
    while k > 0:
        time += 1
        now = As[now]
        k -= 1
        if len(memo[now]) < 2:
            memo[now] += [time]
        if len(memo[now]) == 2:
            shortcut = memo[now][1] - memo[now][0]
            k %= shortcut
    print(now+1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
flag = [0] * (N+1)
cnt = [0] * (N+1)
now = 0
i = 1
while(flag[i] == 0 and K > now):
  flag[i] = 1
  cnt[i] = now
  i = A[i-1]
  now += 1
if(K <= now):
  print(i)
else:
  loop = now-cnt[i]
  kn = (K-now)%loop
  for j in range(kn):
    i = A[i-1]
  print(i)

Submission status: Accepted

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

t = [[] for _ in range(n)]
u = 0
for i in range(k + 1):
    t[u].append(i)
    if len(t[a[u] - 1]) == 2:
        break
    else:
       u = a[u] - 1
ans = 0
for i in range(n):
    if len(t[i]) == 2 and (k - t[i][1]) % (t[i][1] - t[i][0]) == 0:
        ans = i + 1
        break
    elif len(t[i]) == 1 and t[i][0] == k:
        ans = i + 1
        break
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int,_in[0].split(' ')))  # type:list(int)
    A_arr = [0]+list(map(int,_in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    period = N
    visit = [False] * (N+1)
    order = []
    next_visit = 1
    for i in range(N):
        order.append(next_visit)
        visit[next_visit] = True
        next_visit = A_arr[next_visit]
        if visit[next_visit]:
            period = len(order[order.index(next_visit):])
            ofst = len(order[:order.index(next_visit)])
            break
    if K<=ofst:
        cnt = order[K]
    else:
        tmp = order[order.index(next_visit):]
        cnt = tmp[(K-ofst)%period]
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Accepted

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

now=0
cnt=0
from collections import defaultdict
d = defaultdict(lambda: -1)

d[0]=0

while True:
    cnt+=1
    nxt=a[now]-1
    now=nxt
    if k==cnt:
        print(nxt+1)
        exit()
    if d[nxt]!=-1:
        break
    d[nxt]=cnt

k-=d[nxt]
k%=(cnt-d[nxt])

cnt=0
while cnt<k:
    cnt+=1
    nxt=a[now]-1
    now=nxt

print(now+1)

Submission status: Accepted

Solution code:


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

    # k < nの場合は普通にO(n)で実行可能
    if k < n:
        curr = 1
        while k:
            curr = a[curr]
            k -= 1
        print(curr)
        return
            
    # n < kの場合はループするまで回ってみる
    attach = {i: -1 for i in range(1, n + 1)}
    curr = 1
    cnt = 0
    while True:
        if attach[curr] < 0:
            attach[curr] = cnt
            curr = a[curr]
            cnt += 1
        else:
            break
    
    loop_st = curr
    loop_time = cnt - attach[curr]
    
    skip = ((k - attach[loop_st]) // loop_time) * loop_time
    k -= skip

    curr = 1
    while k:
        curr = a[curr]
        k -= 1
    print(curr)
    return
    

submit()

Submission status: Accepted

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

route = [0]
visited = [0]*n
visited[0]=1

while visited[a[route[-1]]-1]==0:
    visited[a[route[-1]]-1]=1
    route.append(a[route[-1]]-1)

if k<len(route):
    print(route[k]+1)
else:
    b = route.index(a[route[-1]]-1)
    ans = (k-b)%(len(route)-b)
    print(route[b+ans]+1)

Submission status: Accepted

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

a=[0]+list(map(int,input().split()))

visited=[0]*(n+1)
visited[1]=1

now=1
loop=0
isloop=0
for i in range(k):
  #print(now,visited)
  if visited[a[now]]>0:
    loop=visited[now]-visited[a[now]]+1
    now=a[now]
    isloop=1
    k-=i+1
    break
  
  visited[a[now]]=visited[now]+1
  now=a[now]
  
#print("k=",k)
ans=now
if isloop:
  k%=loop
  #print("k=",k,"now:",now,"loop=",loop)
  for i in range(k):
    now=a[now]
  
print(now)

Submission status: Accepted

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


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

visited[1] = 0

i = 1
k = 0
while True:
    nv = A[i]
    k += 1
    if K == k:
        print(nv)
        exit()
    if not visited[nv] == -1:
        break
    visited[nv] = k
    i = nv

loop = k - visited[nv]
res = (K-visited[nv]) % loop

for i in range(res):
    nv = A[nv]

print(nv)

Submission status: Accepted

Solution code:
def resolve():
    N,K = map(int,input().split())
    A = [int(i)-1 for i in input().split()]
    visited =[False]*N
    steps = [K for i in range(N)]

    current = 0
    while True:

        if K == 0:
            print(current+1)
            return
        if not visited[current]:
            visited[current]=True
            steps[current]=K
            current=A[current]
            K-=1
        else:
            K= K % (steps[current]-K)
            break
    
    while K != 0:

        current= A[current]
        K-=1
    print(current+1)




if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
memory = [1]
dic = {}
cur = 1
count = 0
while True:
    if count == k:
        print(cur)
        exit()
    if a[cur] in dic.keys():
        loop_begin = dic[a[cur]]
        loop_end = count
        break
    else:
        count += 1
        memory.append(a[cur])
        dic[a[cur]] = count
        cur = a[cur]
loop = memory[loop_begin:]
loop_length = loop_end-loop_begin+1
k -= loop_begin
print(loop[k%loop_length])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,k=MI()
    aa=LI1()
    pos=[-1]*n
    i=aa[0]
    pos[0]=0
    log=[0]
    j=1
    while pos[i]==-1:
        log.append(i)
        if j==k:
            print(log[-1]+1)
            exit()
        pos[i]=j
        i=aa[i]
        j+=1
    pre=pos[i]
    k-=pre
    t=len(log)-pre
    k%=t
    print(log[pre+k]+1)

main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
roop = [1]
roop2 = set([1])
while True:
    next_i = a[roop[-1] - 1]
    if next_i in roop2:
        break
    else:
        roop.append(next_i)
        roop2 |= set([next_i])
temp = roop.index(next_i)
if k <= temp:
    print(roop[k])
else:
    period = len(roop) - temp
    temp2 = (k - temp) % period
    print(roop[temp + temp2])

Submission status: Accepted

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

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

pos = 1

seen = {}
seen[1] = 1

count = 0

ans = 0
loop_pos = 0

for i in range(n):
    pos -= 1
    next_pos = As[pos]
    pos = next_pos
    count += 1
    if count == k:
        ans = next_pos
        break
    elif seen.get(next_pos, None) is None:
        seen[next_pos] = 1
    else:
        loop_pos = next_pos
        break

if ans != 0:
    print(ans)
else:
    k -= count
    count = 0
    for i in range(n):
        pos -= 1
        next_pos = As[pos]
        pos = next_pos
        count += 1
        if count == k:
            ans = next_pos
            break
        elif next_pos == loop_pos:
            break

    if ans != 0:
        print(ans)
    elif k % count == 0:
        print(loop_pos)
    else:
        k = k % count
        count = 0
        for i in range(n):
            pos -= 1
            next_pos = As[pos]
            pos = next_pos
            count += 1
            if count == k:
                ans = next_pos
                break

        print(ans)

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt
import fractions
import collections
import itertools
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
trail=[0]*N
trail[0]=1
buf=0
firstonly=[]
loop=[]
#print(trail)
cnt=0
while True:
    nxt=A[buf]-1
    if trail[nxt]<2:
        trail[nxt]=trail[nxt]+1
        cnt=cnt+1
    else:
        break
    buf=nxt
    #print(trail)
    #input()
#print(trail)
buf=0
if trail[buf]==1:
    firstonly.append(buf)
else:
    loop.append(buf)
i=0
while i<cnt:
    nxt=A[buf]-1
    if trail[nxt]==1:
        firstonly.append(nxt)
    else:
        loop.append(nxt)
    i=i+1
    buf=nxt
    #print(firstonly, loop)
    #input()
#print(firstonly,loop)
if K+1<=len(firstonly):
    print(firstonly[K]+1)
else:
    K=K-len(firstonly)
    print(loop[K%len(loop)]+1)

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = {i:int(x) for i, x in enumerate(input().strip().split(), start=1)}
    dic = {}
    p = 1
    cnt = 0
    dic[p] = cnt
    while K > 0:
        p = A[p]
        cnt += 1
        K -= 1
        if p in dic:
            K %= (cnt - dic[p])
        else:
            dic[p] = cnt

    print(p)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
ans = [1]
gone = [0] * n
now = 0
cnt = 0
lis = list(map(int,input().split()))
while True:
    if cnt == k:
        print(ans[k])
        exit()
    gone[now] = 1
    if gone[lis[now]-1] == 0:
        gone[lis[now]-1] = 1
        now = lis[now]-1
        ans.append(now+1)
    else:
        num = len(ans)
        now = lis[now]
        first = ans.index(now)
        k -= first
        k %= (num-first)
  #         print(ans,now)
  #         print(first,k)
  #         print(ans,now)
        print(ans[first+k])
        exit()
    cnt += 1

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
a.insert(0,0)
now = 1
seen = [0]*(n+1)
seen[1] = 1
for i in range(1,n+1):
  now = a[now]
  if seen[now] != 0:
    break
  else:
    seen[now] = i+1
if k <= max(seen):
  print(a[seen.index(k)])
elif (k - max(seen)) % (max(seen)-seen[now]+1) == 0:
  print(a[seen.index(max(seen))])
else:
  print(a[seen.index(max(seen) - (max(seen)-seen[now]+1) + (k - max(seen)) % (max(seen)-seen[now]+1))])

Submission status: Accepted

Solution code:
def resolve():
    n, k = map(int, input().split())
    a = [int(x) - 1 for x in input().split()]
    dist = [-1] * n
    dist[0] = 0
    now = 0
    road = [0]
    while True:
        nxt = a[now]
        if dist[nxt] < 0:
            dist[nxt] = dist[now] + 1
            now = nxt
            road.append(now)
        else:
            first = dist[now] + 1
            roop = first - dist[nxt]
            break
    if k < first:
        print(road[k] + 1)
        return
    k -= first - roop
    k %= roop
    print(road[first - roop + k] + 1)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = list(map(int, input().split()))
dic = {1:0}
now = 1
flag = 0
T = 0
log = [1]
for i in range(K):
  now = A[now-1]
  #print(i+1,now)
  if now in dic:
    flag=1
    T=i+1-dic[now]
    log = log[dic[now]:]
    break
  dic[now] = i+1
  log.append(now)
if flag!=1:
  print(now)
else:
  print(log[(K-dic[now])%T])