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:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = []
i = 0
B.append(1)
for n in range(N):
  B.append(A[i])
  i = A[i]-1
if K>N:
  start = 0
  num = 0
  for j in range(len(B)):
    if B[len(B)-1] == B[j]:
      start = j
      break
  for j in range(1,len(B)-start):
    if B[start+j] == B[start]:
      num = j
      break
  print(B[((K-start)%num)+start])
else:
  print(B[K])

Submission status: Accepted

Solution code:
def D():
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    town = 1
    visited = {}
    count = 0
    while town not in visited:
        visited[town] = count
        if count == K:  #ends before cycle ends
            print(town)
            return
        town = A[town-1]
        count += 1
    start_of_cycle = visited[town]
    end_of_cycle = count
    length_of_cycle = end_of_cycle - start_of_cycle
    to_go = (K - end_of_cycle)%length_of_cycle
    # print(start_of_cycle, end_of_cycle, length_of_cycle, to_go)
    for i in range(to_go):
        town = A[town-1]
    print(town)
D()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,K = LI()
    A = [0] + LI()

    his = [0] * (N+1)
    s = 1
    cnt = K

    while cnt > 0:
        his[s] = cnt
        s = A[s]
        cnt -= 1
        if his[s] > cnt:
            cnt = cnt % (his[s]-cnt)
    print(s)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#D
N,K=map(int,input().split())
A=[0]+[int(x) for x in input().split()]

p=1
log=[[0,0] for i in range(N+1)]
log[1]=[1,0]
cnt=0
while True:
    cnt+=1
    p=A[p]
    log[p][0]+=1
    if log[p][0]==2:
        break
    else:
        log[p][1]+=cnt

re=cnt-log[p][1]
if K<cnt+log[p][1]:
    p=1
else:
    K=(K-log[p][1])%re

for i in range(K):
    p=A[p]
print(p)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
x = [1]
y = set()
y.add(1)
index = 0
for i in range(n):
    next_index = a[index]
    x.append(next_index)
    y.add(next_index)
    index = next_index - 1
    if len(x) != len(y):
        second = i
        target = next_index
        break
index = 0
for i in range(n):
    next_index = a[index]
    index = next_index - 1
    if next_index == target:
        first = i
        break

num = second - first
if num == 0:
    first = -1
    num = second - first

if first > k:
    print(x[k])
    exit()

k -= (first + 1)
k %= (second - first)
print(x[first+1+k])

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
t = [-1] * n
c = []
t[0] = 0
c.append(0)
x = 0
for i in range(k):
  x = a[x]
  if t[x] != -1:
    l = i + 1 - t[x]
    break
  t[x] = i + 1
  c.append(x)
if len(c) > k:
  print(c[k] + 1)
else:
  for i in range(k % l + (len(c) + l) // l * l, -1, -l):
    if i < len(c):
      print(c[i] + 1)
      break

Submission status: Accepted

Solution code:
N, K= map(int, input().split())
A = list(map(int, input().split()))
x = {1:0}
point = 1
count = 0
while True:
  next_point = A[point-1]
  count +=1
  if next_point in x :
    flag=next_point
    break
  x[next_point] =count
  point = next_point
  
#print(count, x[flag])
c = count - x[flag]
f = x[flag]
#print(c)
if K <f:
    print([i for i in x if x[i] == K ][0])
else :
    dic = {j-f: i for i,j in x.items()}
    print(dic[(K-f) % c])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
b=list(map(int,input().split()))
a=0
for i in range(n):b[i]-=1
if k<n:
  for _ in range(k):a=b[a]
  print(a+1);exit()
c=[-1]*n
cc=0
se=set()
while a not in se:
  c[a]=cc
  cc+=1
  se.add(a)
  a=b[a]
for _ in range((k-c[a])%(cc-c[a])):a=b[a]
print(a+1)

Submission status: Accepted

Solution code:
def main():
    _, n_teleport = map(int, input().split())
    towns = [0] + list(map(int, input().split()))

    visited_list = []
    visited_set = set()

    next_town = 1
    while 1:
        if next_town in visited_set:
            loop_start_at = visited_list.index(next_town)
            loop_length = len(visited_list) - loop_start_at
            break

        visited_list.append(next_town)
        visited_set.add(next_town)
        next_town = towns[next_town]

    if n_teleport < loop_start_at:
        end_point = n_teleport
    else:
        end_point = loop_start_at + (n_teleport - loop_start_at) % loop_length

    print(visited_list[end_point])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 

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

na = [0]*n
v = 0
while k:
    if k&1: v = a[v]
    for j, aj in enumerate(a):
        na[j] = a[aj]
    a,na = na,a
    i += 1    
    k >>= 1

print(v+1)

Submission status: Accepted

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

n = 1
order = [n]
order_set = set([n])

for i in range(1, K + 1):
    n = A[n - 1]
    if n in order_set:
        Li = order.index(n)
        Ri = len(order)
        idx = Li + (K - Li) % (Ri - Li)
        print(order[idx])
        exit()
    else:
        order.append(n)
        order_set.add(n)
        continue
print(n)

Submission status: Accepted

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

pos=-1
seen=[False]*N
last=[-1]*N
hist=[]
i=0
cnt=0

while seen[i]==False:
    seen[i]=True
    last[i]=cnt
    cnt+=1
    hist.append(i)
    next_i=A[i]-1
    i=next_i
    if seen[i]==True:
        pos=i

LOOP=hist[last[pos]:]
preLOOP=last[pos]
if K<=preLOOP:
    print(hist[K]+1)
else:
    K-=preLOOP
    ans=K%len(LOOP)
    print(LOOP[ans]+1)

Submission status: Accepted

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

for i in range(n):
    tmp = a[i] - 1
    doubling_list[0][i] = tmp

for i in range(1, 60):
    for j in range(n):
        doubling_list[i][j] = doubling_list[i - 1][doubling_list[i - 1][j]]

now = 0
for i in range(60)[::-1]:
    if k >> i & 1:
        now = doubling_list[i][now]

ans = now + 1        
print(ans)

Submission status: Accepted

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


# 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():
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    cur = 1
    c = {}
    route = []
    second_f = None
    while (True):
        if cur in c:
            second_f = cur
            break
        route.append(cur)
        c[cur] = 1
        cur = A[cur - 1]
    idx = route.index(second_f)
    if K <= idx:
        print(route[K])
        return
    roop = route[idx:]
    print(roop[(K - idx) % len(roop)])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split(" "))
routs = {}
location = [0 for i in range(N + 1)]
tereporter = list(map(int, input().split()))
for i in range(N):
  routs[i] = tereporter[i] - 1
present_location = 0
n = 0
for i in range(K):
  n += 1
  present_location = routs[present_location]
  if location[present_location] == 0:
    location[present_location] = n
  else:
    loop = n - location[present_location]
    if (K - location[present_location]) % loop == 0:
      break
    else:
      for i in range((K - location[present_location]) % loop):
        present_location = routs[present_location]
      break
print(present_location + 1)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
a = LI()
check = [-1]*n
cntr = 0
tmp = 0
while 1:
    if check[tmp] != -1:
        break
    check[tmp] = cntr
    cntr += 1
    tmp = a[tmp] - 1
c = check[tmp]
if cntr > k:
    for i in range(n):
        if check[i] == k % cntr:
            ans = i+1
            break
else:
    for i in range(n):
        if check[i] - c == (k-c) % (cntr-c):
            ans = i+1
            break
print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
	N,K = map(int, input().split())
	des = [int(a) for a in input().split()]
	ind = [0] * N
	ind[0] = 1
	h = 1
	c = 2
	check = 0
	while(check == 0):
		d = des[h-1]
		if ind[d-1] == 0:
			ind[d-1] = c
			c += 1
		else:
			check = 1
		h = d
	L = ind[d-1]
	R = c
	term = R-L
	if K <= L:
		ans = ind.index(K+1) + 1
	else:
		ans = ind.index(L + (K+1-L)%term)+1
	print(ans)

Submission status: Accepted

Solution code:
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,K = LI()
A = [0]+LI()
town = 1
route = [1]
town_set = set([1])
while 1:
    town = A[town]
    route.append(town)
    if town in town_set:
        break
    town_set.add(town)
loopstart_index = route.index(route[-1])
loop_len = (len(route)-1)-loopstart_index
ans_index = loopstart_index+(K-loopstart_index)%(loop_len)
if K<loopstart_index:
    ans_index = K
print(route[ans_index])

Submission status: Accepted

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

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

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

print(dfs(1, 0))

Submission status: Accepted

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

pos = -1
seen = [False] * n
last = [-1] * n
hist = []
i = 0
cnt = 0

while(seen[i] == False):
    seen[i] = True
    last[i] = cnt
    cnt += 1
    hist.append(i)
    ne = a[i]-1
    i = ne
    if (seen[i] == True):
        pos = i

cycle = hist[last[pos]:]
preCircle = last[pos]

if (k <= preCircle):
    print(hist[k] + 1)
else:
    k -= preCircle
    ans = k % len(cycle)
    print(cycle[ans] + 1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
*A, = map(int, input().split())
A = [0] + A
bit = list(bin(k)[2:][::-1])
m = len(bit)
DP = [[None for j in range(m)] for i in range(n + 1)]
for i in range(n + 1):
    DP[i][0] = A[i]
for j in range(1, m):
    for i in range(n + 1):
        DP[i][j] = DP[DP[i][j - 1]][j - 1]
i = 1
for j, b in enumerate(bit):
    if b == '1':
        i = DP[i][j]
print(i)

Submission status: Accepted

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

now = 0
seen = []
while True:
    seen.append(now)
    teleporter = A[now]
    A[now] = 'used'
    if teleporter == 'used':
        break
    else:
        now = teleporter  

loop_s = seen.index(now)
size = len(seen) - loop_s - 1

if K <= loop_s:
    print(seen[K] + 1)
else:
    print(seen[loop_s +(K - loop_s) % size] + 1)

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
towns = [int(i) for i in input().split()]
ind_ = 1
ts = []
visited = [0]*n
loop_s = None
while(True):
    ind_ = towns[ind_-1]
    if visited[ind_-1]:
        loop_s = ts.index(ind_)
        break
    else:
        visited[ind_-1] = 1
        ts.append(ind_)
if k <= len(ts):
    print(ts[k-1])
else:
    init = len(ts[:loop_s])
    loop_l = len(ts) - init
    loop = ts[loop_s:]
    print(loop[((k-init)%loop_l)-1])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
visited = []
visited_index = [-1] * n
pre = 0

while visited_index[pre] == -1:
    now = a[pre]
    visited.append(pre)
    visited_index[pre] = len(visited)
    pre = now - 1

loop = len(visited) - visited_index[pre] + 1
head = visited_index[pre] - 1

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

Submission status: Accepted

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

now = 0
seen = []
while True:
    seen.append(now)
    teleporter = A[now]
    A[now] = 'used'
    if teleporter == 'used':
        break
    else:
        now = teleporter  

loop_s = seen.index(seen[-1])
size = len(seen) - loop_s - 1

if K <= loop_s:
    print(seen[K] + 1)
else:
    print(seen[loop_s +(K - loop_s) % size] + 1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
s = set()
ns = []
start = 0
for i in range(N):
    if start in s:
        break
    else:
        s.add(start)
        ns.append(start)
        start = A[start]-1

si = ns.index(start)
if K < si:
    print(ns[K]+1)
else:
    print(ns[(K-si)%(i-si) + si]+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
T_list = list(map(int, input().split()))
T_list = [T_list[i]-1 for i in range(N)]
point = 0
syuuki = 0

if K < N:
  i = 0
  while i < K:
    point = T_list[point]
    i += 1  

else:
  i = 0
  while i < N:
    point = T_list[point]
    if point == 0:
      syuuki = i+1
      break
    i += 1
  second_point = point
  
  if syuuki != 0:
    L = K % syuuki

  else:
    j = 0
    while j < N:
      point = T_list[point]
      if point == second_point:
        syuuki = j+1
        break
      j += 1
    L = (K-i) % syuuki

  k = 0
  while k < L:
    point = T_list[point]
    k += 1
  
print(point+1)

Submission status: Accepted

Solution code:
def zero_index(i: str) -> int:
  return int(i) - 1

n, k = map(int, input().split())
transition = list(map(zero_index, input().split()))
places = [0]
next_place = transition[0]
virgin = [True] * n
virgin[0] = False
while virgin[next_place]:
  virgin[next_place] = False
  places.append(next_place)
  next_place = transition[next_place]
start = places.index(next_place)
period = len(places) - start
if k < start:
  t = k
else:
  t = (k - start) % period + start
print(places[t] + 1)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections

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

roop = [0]
for i in range(3*n):
    roop.append(a[roop[i]])
cnt =[0]*n
d = []
for i in range(len(roop)):
    cnt[roop[i]]+=1
    if cnt[roop[i]]>=3 and cnt[roop[i]]<4:
        d.append(roop[i])
for i in range(len(roop)):
    if roop[i] == d[0]:
        check = i
        break
if check == 0:
    k%=len(d)
    print(d[k]+1)
else:
    if k<check + len(d):
        print(roop[k]+1)
    else:
        k-=check
        k%=len(d)
        print(d[k]+1)

Submission status: Accepted

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

town = [False]*(N+1)
visited_town = []
p = 1
while True:
    if town[p]:
        break
    visited_town.append(p)
    town[p] = True
    p = A[p-1]
#ループに入るまでに訪れた街
m = visited_town.index(p)

#ループ内の街
c = len(visited_town)-m

# print(m,c)
# print(visited_town,town)

if K <= m:
    print(visited_town[K])
else:
    print(visited_town[m+(K-m) % c])

Submission status: Accepted

Solution code:
import math

def main():
    N, K = map(int, input().split())
    # 面倒なので、番号を1引いた状態で扱い、最後に1を足す
    A = [ int(x) - 1 for x in input().split()]
    
    # ダブリング用テーブル
    D = [ [A[n] for n in range(N)] ]
    # max(K) = 10^18 なので、max(log2K) = 60
    log2K = int(math.log2(K)) + 1
    for i in range(log2K):
        d = [D[i][n] for n in D[i]]
        D.append(d)
    # print(D)
    town = 0
    for i in range(log2K):
        if K & (1 << i) != 0:
            town = D[i][town]

    print(town + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

flag = [0] * n
i = 0
loop = [1]
while True:
    i = a[i] - 1
    if flag[i] == 0:
        flag[i] = 1
        loop.append(i + 1)
    else:
        start = loop.index(i + 1)
        m = len(loop)
        length = m - start
        break

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

Submission status: Accepted

Solution code:
t = 1
n,k = map(int,input().split())
a = [int(x) for x in input().split()]
f = [0] * n
c = 0
d = 0
e = 0
#ループしてるとこを見つける
for i in range(k):
    if (f[t-1] == 1):
        d = 1
        break
    f[t-1] = 1
    t = a[t-1]
    e = e + 1 # ループが1回終わるまでの回数

#ループがあったら
b = t
if(d == 1):
    for i in range(k):
        t = a[t-1]
        c = c + 1
        if t == b:#ループしている範囲を摘出
            break
    e = e - c #ループが始まる場所、原点
    k = (k - e)%c #ループが始まるとこから最後までのループ回数減らす
    k = k + e #ループが始まる場所とループを抜き取ったやつをたす

t = 1
for i in range(k):
    t = a[t-1]
print(t)

Submission status: Accepted

Solution code:
# 1-index
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()]
A = [0] + A

visited = [False]*(N+1)
visited[1] = True
step = [0]*(N+1)
step[0] = 1
step[1] = A[1]
count = [0]*(N+1)
count[1] = 0
count[A[1]] = 1

now = A[1]
cnt = 1
roop = 0

for _  in range(N):
    now = A[now]
    cnt += 1

    if visited[now]:
        roop = cnt - count[now]
        break
    count[now] = cnt
    step[cnt] = now
    visited[now] = True

if K < count[now]:
    print(step[K])
else:
    K -= count[now]
    ind = K % roop
    print(step[ind+count[now]])

Submission status: Accepted

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

seen = []
now = 0
while True:
    seen.append(now)
    to = A[now]
    A[now] = 'seen'
    if to == 'seen':
        break
    else:
        now = to

loop_s = seen.index(now)
loop_end = seen.index(now, loop_s + 1)
size = loop_end - loop_s

if K <= loop_s:
    print(seen[K] + 1)
else:
    print(seen[loop_s +(K - loop_s) % size] + 1)

Submission status: Accepted

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

now=1
flag=[0]+[-1]*(N-1)

for i in range(K):
    now = A[now-1]
    if flag[now-1]==-1:
        flag[now-1]+=i+2
    else:
        loop = i+1 - flag[now-1]
        zan=(K-i-1) - (K-i-1)//loop * loop
        ans = flag.index(flag[now-1]+zan)+1
        print(ans)
        exit()

print(now)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
loop = []
start = 0
index = 0
check = [-1] * N
fin = False
count = 0
while True:
    if check[index] != -1:
        start = check[index]
        break
    else:
        loop.append(index)
        if len(loop) == K + 1:
            print(index + 1)
            sys.exit()
        check[index] = count
        count += 1
        index = a[index]


if (K + 1 - start) % len(loop[start:]) == 0:
    print(loop[-1] + 1)
else:
    print(loop[start + (K + 1 - start) % len(loop[start:]) - 1] + 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
loop = []
start = 0
index = 0
check = [-1] * N
fin = False
count = 0
while True:
    if check[index] != -1:
        start = check[index]
        break
    else:
        loop.append(index)
        if len(loop) == K + 1:
            print(index + 1)
            fin = True
            break
        check[index] = count
        count += 1
        index = a[index]

if not fin:  # len(loop)<=K
    if (K + 1 - start) % len(loop[start:]) == 0:
        print(loop[-1] + 1)
    else:
        print(loop[start + (K + 1 - start) % len(loop[start:]) - 1] + 1)

Submission status: Accepted

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

now=1
flag=[-1]*(N)

for i in range(K):
    if flag[now-1]==-1:
        flag[now-1]=i
        now = A[now-1]
    else:
        loop = i - flag[now-1]
        zan=(K-(i-loop))%loop
        ans = flag.index(i-loop+zan)+1
        print(ans)
        exit()

print(now)

Submission status: Accepted

Solution code:
a,b=map(int, input().split())
c=list(map(int, input().split())) 
 
l = [1]
f = [0]*a
f[0] += 1
tmp = 1
s = 0
for i in range(b):
    l.append(c[tmp-1])
    tmp = c[tmp-1]
    if f[tmp-1] != 0:
        s = c[tmp-1]
        t = len(l)+1
        break
    f[tmp-1] += 1

#print(l)
if a > b:
    print(l[b])
    exit()

h = l.index(s) + 1

#print(s,h,t)
l2 = l[h-1:t-1]
#print(l2)
if s == 1:
    id = b % (t - 1)
    print(l2[id])
else:
    id = (b - h + 1) % (t - h)
    print(l2[id])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

p = [1]
for i in range(n):
    p.append(a[p[i]-1])

if k <= n:
    print(p[k])
else:
    # 周期の来る前の回数
    num = p.index(p[-1])
    p = p[num:]

    # 周期
    pn = len(p)-1
    k -= num

    # 回数/周期のあまり
    ans = k%pn
    print(p[ans])

Submission status: Accepted

Solution code:
#very important question
n,k=map(int,input().split())
L=list(map(int,input().split()))

visit=[False]*(n+1)

town=[]

next=1
while 1:
    next = L[next-1]
    if not visit[next]:
        town.append(next)
        visit[next] = True
    else:
        town.append(next)
        break
#print(town)
for i in range(n):
    if town[i]==town[-1]:
        mod=i
        index=i
        loop=len(town)-i-1
        loop_array = town[i:-1]
        break

fin_len = (k-mod)%loop
if k<=mod:
    print(town[k-1])
else:
    print(loop_array[fin_len-1])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
bl = [False]*n
now = 1
res = []
while True:
    if bl[now - 1]:
        break
    bl[now - 1] = True
    res.append(now)
    now = a[now - 1]
x = res.index(now)
roop = len(res) - x
if k <= x:
    print(res[k])
else:
    print(res[x + (k-x) % roop])

Submission status: Accepted

Solution code:
# doubling
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    TO_MAX = 60
    to = [[0 for _ in range(N)] for _ in range(TO_MAX+1)]
    for i in range(N):
        to[0][i] = A[i]-1
    for i in range(TO_MAX):
        for j in range(N):
            to[i+1][j] = to[i][to[i][j]]
    v = 0
    for i in range(TO_MAX+1)[::-1]:
        l = pow(2, i)
        if l <= K:
            v = to[i][v]
            K -= l
    print(v+1)   
if __name__ == "__main__":
    main()

Submission status: Accepted

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

count=0
k=1
countlist={}
#countlist[1]=A[0]
count=1
while True:    
    k=A[k-1]
    
    if k in countlist:
        cycle=count-countlist[k]
        rest=K-count
        move=rest%cycle
        for i in range(min(rest,move)):
            k=A[k-1]
        print(k)
        break
    
    countlist[k]=count
    
    if count==K:
        print(k)
        break
    
    count+=1

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
e = [False] * (N+1)
idx = 1
move = []
while True:
  if e[idx]:
    break
  move.append(idx)
  e[idx] = True
  idx = A[idx-1]
m = move.index(idx)
c = len(move) - m

if K <= m:
    print(move[K])
else:
    print(move[m+(K-m) % c])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
t = 0
now = 1
footprint = [1]
past = [0]*N
past[0] = 1

while t < K:
  if past[A[now-1]-1] == 0:
    now = A[now-1]
    footprint.append(now)
    past[now-1]=1
    t += 1
  else:
    s = footprint.index(A[now-1])
    l = t - s + 1
    e = (K-s) % l
    now = footprint[s+e]
    break
    
print(now)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))
T={1:1}
c=1
for i in range(2,K+1):
    c=A[c]
    K-=1
    if c in T:
        l = list(T.keys())[T[c]-1:]
        print(l[K%len(l)])
        break
    else: T[c]=i
else: print(A[c])

Submission status: Accepted

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

A = list(map(int,input().split()))
town = [[] for _ in range(N)]
visited = [0]
flag = [-1] * N

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

f = 0

while flag[f] == -1:
  t = town[f][1]
  flag[f] = t
  f = town[t][0]
  visited.append(t)
  
l = visited[-1]
lv = len(visited)

if K <= lv:
  print(visited[K] + 1)
else:
  cs = visited.index(l)
  cycle = visited[cs:-1]
  lc = len(cycle)
  print(cycle[(K - lv + 1) % lc] + 1)
##i

Submission status: Accepted

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

n=[1]
t=1
#通った場所は0,まだ通ってない場所は-1
ord=[-1]*(N+1)
ord[0]=0

while True:
    t=A[t-1]
    if ord[t] == 0:
        f=n.index(t)
        break
    n.append(t)
    ord[t]=0

k=len(n)-f

if K>=f:
    print(n[f+(K-f)%k])

else:
    print(n[K])

Submission status: Accepted

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

R = [False]*(N+1)
D = []
p = 1
while True:
    if R[p]:
        break
    D.append(p)
    R[p] = True
    p = A[p-1]
m = D.index(p)
c = len(D)-m

if K <= m:
    print(D[K])
else:
    print(D[m+(K-m) % c])

Submission status: Accepted

Solution code:
def main():
    n,k = map(int, input().split())
    town = list(map(int, input().split()))
    town = [i-1 for i in town]
    visited = [-1] * n
    current_town = 0
    current_order = 0
    memo = []
    while visited[current_town] == -1:
        visited[current_town] = current_order
        memo.append(current_town)
        current_town = town[current_town]
        current_order += 1
    loop_start = visited[current_town]
    if k < len(memo):
        print(memo[k]+1)
    else:
        loop_length = len(memo) - loop_start
        k =  (k - loop_start) % loop_length
        print(memo[k+loop_start]+1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
b = [-1] * (n+1)
now = 1
history = []

while b[now] == -1:
  b[now] = len(history)
  history.append(now)
  now = a[now-1]

c = len(history) - b[now]
l = b[now]

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = [-1] + list(map(int,input().split()))
 
visit = [False for i in range(N+1)]
now = 1
cnt = 0
while True:
    if visit[now]:
        break
    visit[now] = True
    now = A[now]
    cnt += 1
cnt2 = 0
visit2 = [False for i in range(N+1)]
while True:
    if visit2[now]:
        break
    visit2[now] = True
    now = A[now]
    cnt2 += 1
 
if cnt >= K:
    ans = 1
    for i in range(K):
        ans = A[ans]
 
else:
    K -= cnt
    K = K%cnt2
    ans = now
    for i in range(K):
        ans = A[ans]
print(ans)

Submission status: Accepted

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

visited = [-1 for i in range(n+1)] # 訪れていたら訪れたときの添字を格納する。
points = []
p = 1
while visited[p] == -1:
  visited[p] = len(points)
  points.append(p)
  p = a[p-1] #添字に直す

T = len(points) - visited[p]
s = visited[p]

if k < s:
  print(points[k])
else:
  mod = (k - s) % T
  print(points[s+mod])

Submission status: Accepted

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

R = [False]*(N+1)
D = []

p = 1
while True:
    if R[p]:
        break
    D.append(p)
    R[p] = True
    p = A[p-1]

m = D.index(p)
c = len(D)-m

if K <= m:
    print(D[K])
else:
    print(D[m+(K-m) % c])

Submission status: Accepted

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

t_zero = [-1] * N

t = 0
a = 1

while t_zero[a-1] == -1:
  if t == K:
    break
  t_zero[a-1] = t
  t += 1
  a = A[a-1]
else:
  k = (K - t_zero[a-1]) % (t - t_zero[a-1])
  for _ in range(k):
    a = A[a-1]
print(a)

Submission status: Accepted

Solution code:
cin = open(0).read().strip().split('\n')

n,k = map(int, cin[0].split(' '))
a = list(map(int, cin[1].split(' ')))

history = [1]
for i in range(n):
    history.append(a[history[i]-1])

if n >= k:
    print(history[k])
else:
    times = [-1] * n
    for i in range(n):
        if times[history[i]-1] == -1:
            times[history[i]-1] = i
        else:
            cycle = i-times[history[i]-1]
            pre = times[history[i]-1]
            mod = (k-pre)%cycle
            print(history[pre+mod])
            break

Submission status: Accepted

Solution code:
a = input().split()
N = int(a[0])
K = int(a[1])
c = input().split()
c=[int(i) for i in c]


#それぞれ頂点が向かう先。



current_num_set = set()
current_num_list=[]
#これまでの道筋
current_num = 1 #現在の位置



#今いる位置が今まで出てきていない場合に、次どこにいくのかをチェック
while (current_num not in current_num_set):
      current_num_set.add(current_num)
      current_num_list.append(current_num)
      current_num = c[current_num-1]


c = len(current_num_list)


first_index = 0
#グルグルなっているところの最初のインデックスを計算して格納
for i in range(c):
  if current_num_list[i] == current_num:
    first_index = i
    break


cicle=c-first_index
first=first_index
#cがグルグルのリストの長さ
#グルグルの始まりのインデックス
if c<=K+1 :
  index = (K - first) % cicle + first
  print(current_num_list[index])
else :
  print(current_num_list[K])