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:
#!/usr/bin/env python3


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    slow = 0
    fast = 0
    collide = -1
    while True:
        slow = A[slow]-1
        fast = A[A[fast]-1]-1
        if slow == fast:
            collide = slow
            break
    # print("loop detect")
    slow = 0
    fast = collide
    begin = 0
    while True:
        if slow == fast:
            break
        slow = A[slow]-1
        fast = A[fast]-1
        begin += 1
    # print("begin detect")
    loopC = 0
    while True:
        slow = A[slow]-1
        fast = A[A[fast]-1]-1
        loopC+=1
        if slow == fast:
            break
    # print("loop length detect")
    if begin >=K:
        current = 0
        for i in range(K):
            current = A[current]-1
        print(current+1)
    else:
        K -= begin
        current = 0
        for i in range(begin):
            current = A[current] - 1
        for i in range(K%loopC):
            current = A[current]-1
        print(current+1)
    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


n, k = map(int,input().split())
cities = list(map(lambda x:int(x)-1,input().split()))

footprint_L = list()
footprint_S = set()
i = 0
footprint_S.add(i)
footprint_L.append(i)
while cities[i] not in footprint_S:
    footprint_S.add(cities[i])
    footprint_L.append(cities[i])
    i = cities[i]

#print("terminal:", cities[i])


cyclestart = footprint_L.index(cities[i])
cyclelen = len(footprint_L) - cyclestart
#print(footprint_L)
#print(cyclestart, cyclelen)
#print((k-cyclestart) % cyclelen)
if k >= len(footprint_L):
    print(footprint_L[cyclestart+(k-cyclestart) % cyclelen]+1)
else:
    print(footprint_L[k]+1)

Submission status: Accepted

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

visited = [False]*(N)
visited[0] = True

dist = [0]*N
cur = 0
idx = 1
result = [0]
while True:
    nxt = A[cur]
    if visited[nxt]:
        amari = dist[nxt]
        MOD = idx - amari
        break
    else:
        visited[nxt] = True
        dist[nxt] = idx
        cur = nxt
        idx += 1
        result.append(cur)

if K<=amari:
    ans = result[K]+1
else:
    K -= amari
    result = result[amari:]
    ans = result[K%MOD]+1
print(ans)

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

visited = [0 for _ in range(n)]
i = 0
while visited[i] == 0:
    visited[i] = 1
    i = a[i]

cnt = 0
goal = i
i = goal
while not (i == goal and cnt > 0):
    i = a[i]
    cnt += 1

i = 0

if True:
    while i != goal and k > 0:
        k -= 1
        i = a[i]
    if k != 0:

        k = k % cnt
        i = goal

        for cnt in range(k):
            i = a[i]

print(i+1)

Submission status: Accepted

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

visited_city = {1: 0}
visited_city_inv = {0: 1}

now = 1
num = 0
while True:
    next_city = arr[now - 1]
    num += 1
    if next_city not in visited_city:
        visited_city[next_city] = num
        visited_city_inv[num] = next_city
        now = next_city
    else:
        break

if k < num:
    ans = visited_city_inv[k]
else:
    x = visited_city[next_city]
    period = num - x
    ans = visited_city_inv[x + (k - x) % period]

print(ans)
# print(visited_city)

Submission status: Accepted

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

tlist=[]
pos=1
pos_set=set()
while True:
  tlist.append(pos)
  if pos in pos_set:
    break
  pos_set.add(pos)
  pos=alist[pos]
  
dup_pos2=len(tlist)-1
dup_pos1=-1
for i in range(len(tlist)):
  if tlist[i]==tlist[-1]:
    dup_pos1=i
    break
    
#print(tlist)
cycle=dup_pos2-dup_pos1
#print(dup_pos1,dup_pos2,cycle)
if K<len(tlist):
  print(tlist[K])
else:
  print(tlist[(K-dup_pos1)%cycle+dup_pos1])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
R = {1:0}
i, t = A[0], 1

while K > t:
    r = R.get(i)
    if r == None:
        R[i] = t
        i = A[i-1]
        t += 1
    else:
        K -= r
        K %= t - r
        for k in range(K):
            i = A[i-1]

print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

def main():
    N,K = MAP()
    A = LI()
    isVisited = set()
    loop = []
    cur = 0

    while True:
        if cur in isVisited:
            break
        isVisited.add(cur)
        loop.append(cur)
        cur = A[cur]-1
    
    before_loop = loop.index(cur)
    loop_length = len(loop)- before_loop

    if K < len(loop):
        print(loop[K]+1)
    else:
        print(loop[before_loop+(K-before_loop)%loop_length]+1)


    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n,k= map(int, input().split()) 
a = list(map(int, input().split()))
# n = int(input())
# a = [int(input()) for _ in range(n)]

ans = 1
c = set()
c.add(1)
for i in range(k):
    ans = a[ans-1]
    if ans in c:
        break
    else:
        c.add(ans)
count = 0
tmp=1
for i in range(k):
    tmp = a[tmp-1]
    if tmp == ans:
        val = i +1
        break
k = k - val
if (len(c)- val) == 0:
    s = k % len(c)
else:
    s = k % (len(c) - val)

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

print(tmp)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
order = [-1]*N
crr = 0
T = 0
s = -1
order[0] = 0
for i in range(N+1):
    crr = A[crr] - 1
    if order[crr] >= 0:
        T = (i+1) - order[crr]
        s = order[crr]
        break
    order[crr] = i+1

if K <= s:
    crr = 0
    while(K):
        K -= 1
        crr = A[crr]-1
    print(crr+1)
else:
    k = K-s
    d = k % T
    while(d):
        d -= 1
        crr = A[crr]-1
    print(crr+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ok=set()
now=0
l=[]
while now not in ok and k:
    l.append(now)
    ok.add(now)
    now=a[now]-1
    k-=1
if k==0:print(now+1);exit()
length=len(ok)-(h:=l.index(now))
l=l[h:]

k=(k)%length

print(l[k]+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1

already = [-1 for i in range(n)]
already[0] = 0
mati = 0
num = 0
for _ in range(n):
    num += 1
    mati = a[mati]
    if already[mati] == -1:
        already[mati] = num
        continue
    else:
        roop = num - already[mati]
        break

saisho = already[mati]
if k <= saisho:
    tugi = 0
    for _ in range(k):
        tugi = a[tugi]
    print(tugi+1)
else:
    nokori = k - saisho
    amari = nokori % roop
    for _ in range(amari):
        mati = a[mati]
    print(mati+1)

Submission status: Accepted

Solution code:
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
c=[0 for i in range(n)]

l=1
u=0
f=True
while True:
  u+=1
  l=a[l-1]
  if u==k:
    print(l)
    f=False
  if c[l-1]:
    break
  else:
    c[l-1]=u
k=(k-(c[l-1]))%(u-c[l-1])
while k:
  k-=1
  l=a[l-1]
if f:
  print(l)

Submission status: Accepted

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

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

town_list = [-1,0]+[-1 for i in range(N-1)]
town_now = 1
n_teleport = 0

while n_teleport<K:
  n_teleport += 1
  town_now = A[town_now]
  if town_list[town_now]==-1:
    town_list[town_now] = n_teleport
  else:
    break

if n_teleport==K:
  print(town_now)
else:
  loop_start_town = town_now
  loop_start_time = town_list[town_now]
  loop_len = n_teleport-town_list[town_now]
  M = (K-loop_start_time)%loop_len
  for _ in range(M):
    town_now = A[town_now]
  print(town_now)

Submission status: Accepted

Solution code:
# coding: utf-8
N,K=map(int,input().split())
A=list(map(int,input().split()))
used=[False for i in range(N)]
used[0]=True
p=1
L=[1]

for i in range(N+1):
    p=A[p-1]
    L.append(p)
    if used[p-1]:
        looper=p
        break
    used[p-1]=True

for i in range(len(L)):
    if L[-(2+i)]==looper:
        a=i+1
        b=len(L)-1-a
        break
if K>b:
    ans=L[b+(K-b)%a]
else:
    ans=L[K]

print(ans)

Submission status: Accepted

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

t_list = [1]
t_table = { 1: 0 }
t = 1
loop = None
while True:
	t = A_list[t - 1]
	if t in t_table:
		loop = t_table[t]
		break
	t_table[t] = len(t_list)
	t_list.append(t)

t_head = t_list[:loop]
t_loop = t_list[loop:]

if K < loop:
	print(t_head[K])
else:
	print(t_loop[(K - loop) % len(t_loop)])

Submission status: Accepted

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

visited = set()
visited.add(0)
now = 0
root = [-1 for i in range(n+1)]
root[0] = 0
ind = 1
cnt = 0
first_seen = {}
first_seen[0] = 0

finished = False
while True:
    goto = arr[now]-1
    # print(goto)
    if goto not in visited:
        visited.add(goto)
        now = goto
        root[ind] = goto
        ind += 1
        cnt += 1
        first_seen[goto] = cnt
    else:
        root[ind] = goto
        cnt += 1
        now = goto
        break

    if cnt == k:
        finished = True
        break

if finished:
    print(now+1)
else:
    # print(now)
    # print(first_seen)
    pathl = cnt-first_seen[now]
    # print(cnt,first_seen[now])
    # print(pathl)
    left = k-cnt
    left = left%pathl
    fin = first_seen[now] + left
    # print(root)
    print(root[fin]+1)

Submission status: Accepted

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

if K <= N:
    now = 1
    for i in range(1, K+1):
        now = A[now]
    print(now)
else:
    check = [-1]*(N+1)
    check[1] = 0
    now = 1
    for i in range(1, N+1):
        now = A[now]
        if check[now] >= 0:
            first = check[now]
            second = i
            break
        else:
            check[now] = i
    now = 1
    for i in range(first):
        now = A[now]
    K = (K-first)%(second-first)
    for i in range(K):
        now = A[now]
    print(now)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
c=0
d={}
d[1]=0
dd={}
dd[0]=1
now=1
while True:
    now=a[now-1]
    c+=1
    if now in d:
        break
    d[now]=c
    dd[c]=now
s=d[now]
if k<=s:
    print(dd[k])
    exit()
p=c-s
k-=s
k%=p
k+=s
print(dd[k])

Submission status: Accepted

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

ved = [-1]*n
ved[0] = 0
cur = 0
i = k
while i > 0:
  cur = ls[cur]
  i -= 1  
  if ved[cur] >= 0:
    i= i % ((k-i)-ved[cur])
  else:
    ved[cur] = k-i
print(cur+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
dest = [1]
dest_set = {1}
now = 1
while True:
    nxt = a[now-1]
    if nxt in dest_set:
        loop = dest.index(nxt)
        break
    dest.append(nxt)
    dest_set.add(nxt)
    now = nxt
if k<len(dest):
    print(dest[k])
else:
    print(dest[(k-len(dest))%(len(dest)-loop)+loop])

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

city_position = {}
step = 0
city = 0

while city not in city_position:
	city_position[city] = step
	city = a[city]
	step += 1

steps_before_cycle = city_position[city]
cycle_len = step - steps_before_cycle

# k %= cycle_len

city = 0
for i in range(min(k, steps_before_cycle)):
	city = a[city]

k -= steps_before_cycle
if k > 0:
	k %= cycle_len

	for i in range(k):
		city = a[city]


print(city+1)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(lambda x: int(x)-1, input().split()))
    visited = [0]
    visited_set = {0}
    now = 0
    for i in range(2*n):
        now = a[now]
        if now in visited_set:
            break
        else:
            visited.append(now)
            visited_set.add(now)
    l = len(visited)
    v = visited.index(now)
    if k < v:
        print(visited[k]+1)
    else:
        k -= v
        k %= (l-v)
        k += v
        print(visited[k]+1)


main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
n = 1
B = [0]*N
state = 0
for i in range(2*N+1):
    if i == K:
        state = 1
        break
    B[n-1] = i+1
    n = A[n-1]
    if B[n-1] != 0:
        t = i+2
        break
if state:
    print(n)
else:
    c = t-B[n-1]
    s = (K+1-t)%c
    for i in range(s):
        n = A[n-1]
    print(n)

Submission status: Accepted

Solution code:
from sys import stdin
input=lambda : stdin.readline().strip()
from math import ceil,sqrt,factorial,gcd
n,k=map(int,input().split())
l=list(map(int,input().split()))
a=1
s=set()
count=0
while a not in s:
	s.add(a)
	a=l[a-1]
	count+=1
	if count==k:
		print(a)
		exit()
if count<k:
	k-=count
	# print(k)
else:
	a=1
	for i in range(k):
		a=l[a-1]
	print(a)
	exit()
s=set()
count=0
while a not in s:
	s.add(a)
	a=l[a-1]
	count+=1
if count<k:
	f=k%count
	for i in range(f):
		a=l[a-1]
	print(a)
else:
	for i in range(k):
		a=l[a-1]
	print(a)

Submission status: Accepted

Solution code:
def main():
    N, K = map( int, input().split())
    A = list( map( lambda x: int(x)-1, input().split()))
    T = [0]
    C = [-1]*N
    C[0] = 0
    s = 0
    count = 0
    while True:
        s = A[s]
        count += 1
        if count == K:
            print(s+1)
            return
        if C[s] != -1:
            L = count - C[s]
            break
        C[s] = count
        T.append(s)

    m = len(T) - L
    print( T[-L:][(K-m)%L]+1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
MOD = 10**9+7
# MOD = 998244353

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

visited = dict()
rvs = dict()
cur = 0
num = 0
while True:
    if cur in visited:
        # print(visited)
        # print(rvs)
        s = visited[cur]
        roop = num - s
        kk = (k-s)%roop
        # print(s, roop, kk, kk+s)
        print(rvs[kk+s]+1)
        exit()
    if num == k:
        print(cur+1)
        exit()
    else:
        visited[cur] = num
        rvs[num] = cur
        cur = A[cur]-1
        num += 1

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))


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

    # シミュレーションでループを検出
    g = Graph(N)
    for X, Y in zip(range(1, N+1), A):
        g.add_edge(X-1, Y-1)

    seen = [False]*N
    prev = []
    state = 0

    while True:
        seen[state] = True
        prev.append(state)
        for dest, _ in g.E[state]:
            state = dest
        if seen[state]:
            break
    amari = prev.index(state)
    period = len(prev)-amari
    # print(state, amari, period, prev)
    if K < amari:
        print(prev[K]+1)
    else:
        print(prev[amari + (K-amari) % period]+1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
*A, = map(int, input().split())
# n, k = 6, 727202214173249351
# A = [6, 5, 2, 5, 3, 2]
# n, k = 2, 1
# A = [1, 3]
# n, k = 3, 3
# A = [2, 3, 3]
A = [a - 1 for a in A]
now = 0
V = [False for i in range(n)]
V[0] = 0
L = [now]
cnt = 0
while not V[A[now]]:
    cnt += 1
    now = A[now]
    L.append(now)
    V[now] = cnt
a = V[A[now]]
b = cnt - a + 1
if k < cnt:
    print(L[k] + 1)
    exit()
print(L[(k - a) % b + a] + 1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
line = {}
for i in range(N):
  line[i+1] = A[i]

dp = [[0]*(N+1) for _ in range(71)]
for i in range(1, N+1):
  dp[0][i] = line[i]

for i in range(70):
  for j in range(1, N+1):
    dp[i+1][j] = dp[i][dp[i][j]]

for i in range(1, N+1):
  now = i 
  for j in range(70):
    # Kを2ビットに変換し、1のところだけ行う
    if (K&(1<<j)) != 0:
      now = dp[j][now]

  print(now)
  exit()

Submission status: Accepted

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

c=1
path=[]
d={}
l=0
while l<=k:
    if c in d:
        p=d[c]
        #print(p, path)
        pattern_l = l-p
        k-=((k-p)//pattern_l)*pattern_l
    path.append(c)
    l+=1
    d[c]=l-1
    c=A[c-1]
print(path[k])

Submission status: Accepted

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

def solve(N, K, A):
    ind = []
    tr = None
    visited = set()
    cur = 1
    while cur not in visited:
        ind.append(cur)
        visited.add(cur)
        cur = A[cur-1]
    tr = cur
    itr = ind.index(tr)
    if len(ind) > K:
        return ind[K]
    KK = K - itr
    iind = ind[itr:]
    return iind[KK%len(iind)]

        


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    print(solve(N, K, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    p=0
    l=[-1]*N
    cl=[0]*N
    for i in range(N):
        l[i]=p
        cl[p]=1
        p=A[p]-1
        if cl[p]!=0:
            x=l.index(p)
            r=i+1-x
            break
        r=N
        x=0
    #print(l,x,r)
    if K<=x:
        ans=l[K]
        print(ans+1)
    else:
        ans=l[x+(K-x)%r]
        print(ans+1)
    



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k = [int(i) for i in input().split()]
a = [0] + [int(i) for i in input().split()]

pos = 1
move= 0
colors = [-1]*(n+1)

while(colors[pos]==-1):
    colors[pos] = move
    move += 1
    pos = a[pos]
    if move==k:
        print(pos)
        break
else:
    turn = move - colors[pos]
    rest = (k-colors[pos]) % turn
    while rest:
        pos = a[pos]
        rest -= 1
    print(pos)

Submission status: Accepted

Solution code:
from collections import deque

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

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

d = [-1] * N
d[0] = 0
q = deque()
q.append(1)

while(q):
    x = q.popleft()
    n = a[x - 1]
    if(d[n-1] == -1):
        d[n-1] = d[x-1] + 1
        q.append(n)

if(k <= max(d)):
    for i in range(N):
        if(d[i] == k):
            print(i+1)
            exit()


rS = n

d2 = [-1] * N
d2[rS - 1] = 0
q = deque()
q.append(rS)

while(q):
    x = q.popleft()
    n = a[x - 1]
    if(d2[n-1] == -1):
        d2[n-1] = d2[x-1] + 1
        q.append(n)
ma = max(d2) + 1
k -= d[rS - 1]
k %= ma

for i in range(N):
    if(d2[i] == k):
        print(i+1)
        exit()

Submission status: Accepted

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

loop = [1]
now = 1
d = set([1])
for i in range(n):
    now = a[now]
    if now in d:
        for j in range(len(loop)):
            if now == loop[j]:
                ind = j
        break
    d.add(now)
    loop.append(now)

if len(loop) >= k+1:

    print(loop[k])

else:
    k -= ind
    loop = loop[ind:]
    print(loop[k%len(loop)])

Submission status: Accepted

Solution code:
import sys, os

def f():
    args = list(map(int,input().split()))
    if len(args) > 1:
        return args
    return args[0]

if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n,k  = f()
    A = f()

    A = [0] + A
    last = [-1] * (n+1)

    last[1] = 0
    cur= 1

    pos = -1
    cycle = -1

    if k < n:
        for i in range(k):
            cur = A[cur]
        print(cur)
    else:
        for i in range(n):
            nxt = A[cur]
            if  i == n-1:
                pos = nxt
                cycle = n-1 - last[nxt]
            last[nxt] = i
            cur = nxt
            

        steps = (k - n)%cycle
        cur = pos
        for i in range(steps):
            cur = A[cur]
        print(cur)

solve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))
    temp = [-1] + list(map(int, readline().split()))
    a = {i: temp[i] for i in range(1, n + 1)}

    cur = 1
    cnt = 0
    visited = {i: -1 for i in range(1, n + 1)}
    visited[1] = 0

    while True:
        cnt += 1
        cur = a[cur]
        if visited[cur] == -1:
            visited[cur] = cnt
        else:
            break

    start = cur
    st = visited[cur]
    gt = cnt
    period = gt - st
    t = k

    if t < st:
        cur = 1
        cnt = 0
        while cnt != t:
            cnt += 1
            cur = a[cur]
    else:
        t -= st
        t %= period
        cur = start
        cnt = 0
        while cnt != t:
            cnt += 1
            cur = a[cur]

    print(cur)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


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

    res = K
    step = [-1 for _ in range(N)]
    que = queue.Queue()
    que.put(0)
    step[0] = 0
    while not que.empty():
        nc = que.get()
        nn = A[nc]
        nn -= 1
        res -= 1
        if step[nn] == -1:
            step[nn] = step[nc] + 1
            if res == 0:
                return print(nn + 1)
            que.put(nn)
        else:
            start = nn
            closer = [nn]
            while True:
                nn = A[nn] - 1
                if nn != start:
                    closer.append(nn)
                else:
                    break
            ans = res % len(closer)
            print(closer[ans] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

visited = set()
visited.add(0)
now = 0
route = [0]

for i in range(1, n + 5):
    now = a[now] - 1
    if now in visited:
        break
    route.append(now)
    visited.add(now)

start = route.index(now)
loop = i - start

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

Submission status: Accepted

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

machi=[-1]*(N+1)
counter=0
basyo=1
while counter<K:
  counter+=1
  basyo=A[basyo]
  if machi[basyo]==-1:
    machi[basyo]=counter
  else:
    tmp=counter-machi[basyo]
    counter+=((K-counter)//tmp)*tmp
    
print(basyo)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))
    go = [False]*N
    
    roop = [1]
    now = 1
    while True:
        go[now-1] = True
        now = a[now-1]
        if go[now-1]:
            break
        else:
            roop.append(now)
            go[now-1] = True

    ind = roop.index(now)
    r = len(roop)-ind
    if M < ind:
        print(roop[M])
    else:
        M -= ind
        M %= r
        M += ind
        print(roop[M])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b,c,d=[],set([]),0
for i in range(200000):
    b.append(d)
    c.add(d)
    if len(b)!=len(c):
        break
    d=a[d]-1
for i in range(len(b)):
    if b[-1]==b[i]:
        e=i
        break
if k<e:
    print(b[k]+1)
else:
    print(b[(k-e)%(len(b)-e-1)+e]+1)

Submission status: Accepted

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

now = 1
visited = [ 1, -1 ] + [ -1 ] * ( n - 1 )
diary = [ -1, 0 ] + [ -1 ] * ( n - 1 )

for i in range( 1, k+1 ):
    now = a[ now ]
    visited[ i ] = now
    if diary[ now ] != -1:
        cycle = i - diary[ now ]
        d = ( k - i ) % cycle
        now = visited[ diary[ now ] + d ]
        break
    else:
        diary[ now ] = i

print( now )

Submission status: Accepted

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

def get_loop_num(start, last):
    x = start
    loops = [start]
    for i in range(K):
        x = A[x-1]
        loops.append(x)
        if x == last:
            return loops

loop_check = [False] * N
loop_check[0] = True
x = 1
for i in range(K):
    new_x = A[x-1]
    if loop_check[new_x-1]:
        start = new_x
        last = x
        loops = get_loop_num(start, last)
        l = (K-i-1) % len(loops)
        print(loops[l])
        exit()
    else:
        loop_check[new_x-1] = True
        x = new_x
print(x)

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
A = [int(x) - 1 for x in readline().split()]
assert len(A) == N


def solve():
    cur = 0
    seen = {0: 0}
    tele = [0]
    loop = []
    loopenter = -1
    while True:
        nxt = A[cur]
        if nxt in seen:
            loopenter = seen[nxt]
            loop = tele[loopenter:]
            break
        seen[nxt] = len(tele)
        tele.append(nxt)
        cur = nxt

    if K < loopenter:
        return tele[K]
    k = (K - loopenter) % len(loop)
    return loop[k]


if __name__ == "__main__":
    print(solve() + 1)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n,k = m()

a = l()

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

po[0] = 0
now = 0
for i in range(1,n):
    aaa = a[now]-1
    if po[aaa] == -1:
        po[aaa] = po[now]+1
        now = aaa
    else:
        break

un = po[aaa]
if k <= un:
    for i in range(n):
        if k == po[i]:
            print(i+1)
else:
    k -= un
    mod = po[now]+1 - po[aaa]
    ap = k % mod
    for i in range(n):
        if un + ap == po[i]:
            print(i+1)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,k = map(int, input().split())
a = list(map(lambda z:int(z)-1, input().split()))
if k <= n:
    now = 0
    for i in range(k):
        now = a[now]
    print(now+1)
    exit()
root = [0]
use = [-1 for _ in range(n)]
use[0] = 0
now = 0
l = -1
for i in range(1,n+1):
    now = a[now]
    if use[now] == -1:
        use[now] = i
    else:
        k -= i
        l = i - use[now]
        break
k %= l
for i in range(k):
    now = a[now]
print(now+1)

Submission status: Accepted

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

s = 1
route = []
route.append(s)
arrive = [0]  * N
arrive[s-1] = 1
while True:
    s = A[s-1]
    route.append(s)
    if arrive[s-1] == 1:
        break
    arrive[s-1] = 1

# print(route)
ll = route[-1]
l = len(route)
# print(l)
f = route.index(ll)

if K < f:
    print(route[K])
else:
    roll = route[f::]
    print(roll[(K-f)%(l-1-f)])