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
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))

def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1''などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))

def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,K = MI()
A = [0]+LI()
ans_l = [1]
next = A[1]
done = [0]*(N+1)
done[1] = 1
while done[next]==0:
    ans_l.append(next)
    done[next]=1
    next = A[next]
idx = ans_l.index(next)
repeat = ans_l[idx:]
if K<idx:
    print(ans_l[K])
else:
    print(repeat[(K-idx)%len(repeat)])

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = [*map(lambda x:int(x)-1, input().split())]
index = [-1]*N
path = []
pre = 0
while index[pre] < 0:
    index[pre] = len(path)
    path += [pre]
    pre = A[pre]
one = index[pre]
loops = len(path) - one
if K < one: print(path[K]+1)
else: print(path[(K-one) % loops + one]+1)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = [*map(lambda x:int(x)-1, input().split())]
index = [-1]*N
path = []
pre = 0
while index[pre] < 0:
    index[pre] = len(path)
    path += [pre]
    pre = A[pre]
one = index[pre]
loops = len(path) - one

k = max(0, K-one) % loops + min(K, one)
pre = 0
for _ in range(k): pre = A[pre]
print(pre + 1)

# if K <= one: print(path[K])
# else: print(path[(K-one) % loops + one]+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
bit = k.bit_length()
table = [[0]*n for _ in range(bit)]
table[0] = A

for i in range(1, bit):
    for j in range(n):
        table[i][j] = table[i-1][table[i-1][j]]

ans = 0
for i in reversed(range(bit)):
    if (1 << i) <= k:
        k -= 1 << i
        ans = table[i][ans]
print(ans+1)

Submission status: Accepted

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

def main():
  N, K = map(int, readline().split())
  A = list(map(int, readline().split()))
 
  n = []
  for i in range(N):
    n.append(-1)
  s = 0
  c = -1
  d = A[1-1]
  r = [1]
  n[0] = 0
  for i in range(1, K+1):
    if n[d - 1] == -1:
      n[d - 1] = i
    else:
      s = n[d - 1]
      c = i - n[d - 1]
      break
    r.append(d)
    d = A[d - 1]
  if c == -1:
    print(r[-1])
  else:
    cr = r[s:s+c]
    k = (K - s)%c
    print(cr[k])
  exit()

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
sys.setrecursionlimit(10**7)
n, k = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))

visited = [0]*n


def teleport(v):
    if visited[v]+1 == 3:
        return 0
    visited[v] += 1
    teleport(A[v])


teleport(0)
c = Counter(visited)
init = c[1]
loop_cnt = c[2]

if k <= init:
    min_k = k
else:
    min_k = init + ((k-init) % loop_cnt)

ans = 0
for _ in range(min_k):
    ans = A[ans]
print(ans+1)

Submission status: Accepted

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

index = [-1]*N
pre, path_cnt = 0, 0
for i in range(N):
    if index[pre] >= 0: break
    else:
        index[pre] = i
        path_cnt += 1
    pre = A[pre]

one = index[pre]
loops = path_cnt - one
k = max(0, K-one) % loops + min(K, one)

pre = 0
for _ in range(k): pre = A[pre]
print(pre + 1)

Submission status: Accepted

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

index = [-1]*N
pre, path_cnt = 0, 0
for i in range(N):
    if index[pre] >= 0: break
    else:
        index[pre] = i
        path_cnt += 1
    pre = A[pre]

loops = path_cnt - index[pre]
one = index[pre]
k = max(0, K-one) % loops + min(K, one)

pre = 0
for _ in range(k): pre = A[pre]
print(pre + 1)

Submission status: Accepted

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

visited = {}
for i in range(1, N+1):
    visited[i] = False

i2p = {}
p2i = {}
i = 0
cur = 1
while True:
    i2p[i] = cur
    p2i[cur] = i
    visited[cur] = True
    if visited[A[cur]]:
        break
    cur = A[cur]
    i += 1

start_loop = p2i[A[cur]]
end_loop = len(i2p)
num_loop = end_loop - start_loop

if K < end_loop:
    print(i2p[K])
else:
    print(i2p[(K-start_loop)%num_loop+start_loop])

Submission status: Accepted

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

pre = 0
index = [-1]*N
path_cnt = 0
for i in range(N):
    if index[pre] >= 0:
        break
    else:
        index[pre] = i
        path_cnt += 1
    pre = A[pre]

loops = path_cnt - index[pre]
one = path_cnt - loops
k = max(0, K-one) % loops + min(K, one)

pre = 0
for _ in range(k): pre = A[pre]
print(pre + 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]

visited = [0] * n
steps = []

i = 0
cnt = 0
while visited[i] == 0:
  visited[i] = 1
  steps.append(i)
  cnt += 1
  i = A[i]
  if cnt == k:
    print(i + 1)
    exit()

loop_start = steps.index(i)
loop_cycle = len(steps) - loop_start

pos = (k - loop_start) % loop_cycle
ans = steps[loop_start:][pos] + 1

print(ans)

Submission status: Accepted

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

s=1
q=[0]*n
q[0]=1
r=[1]
for i in range(k):
  s=l[s-1]
  if q[s-1]==0:
    q[s-1]+=1
    r.append(s)
    if i==k-1:
      print(s)
  else:
    x=r.index(s)
    mod=len(r)-x
    t=(k-i-1)%mod
    print(r[x+t])
    break

Submission status: Accepted

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

pre = 0
index = [-1]*N
path = []
for n in range(N):
    if index[pre] >= 0:
        # print('len(path)',len(path),'pre',pre)
        # print('n',n,'index[pre]',index[pre])
        # print('index',index)
        # print('path',path)
        break
    else:
        index[pre] = n
        path += [pre]
    pre = A[pre]

loops = len(path) - index[pre]
one = len(path) - loops
k = max(0, K-one) % loops + min(K, one)
# print('one',one,'loops',loops,'k',k)

pre = 0
for _ in range(k): pre = A[pre]
print(pre + 1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
G = []
visited = [-1]*N
count = 0
v = 0
while visited[v] == -1:
    visited[v] = count
    G.append(v+1)
    v = A[v]-1
    count += 1
if visited[v] >= K:
    print(G[K])
else:
    m = count - visited[v]
    K -= visited[v]
    K %= m
    print(G[K+visited[v]])

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from collections import deque

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n, k = rli()
	A = list(rli())
	for i in range(n):
		A[i] -= 1
	L, seen = 0, set()
	cycle = deque()
	curr, cnt = 0, 0
	final = 0
	init = 0
	while cnt <= k:
		if cnt == k:
			print(curr + 1)
			return
		seen.add(curr)
		cycle.append(curr)
		L += 1
		curr = A[curr]
		if curr in seen:
			final = curr
			break
		cnt += 1
	while cycle and cycle[0] != final:
		init += 1
		cycle.popleft()
	L = len(cycle)
	last = (k-init) % L
	print(cycle[last] + 1)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

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

now = 0
for d in range(64):
    if ((1 << d) & K) > 0:
        now = A[now]
    A = [A[a] for a in A]
print(now + 1)

Submission status: Accepted

Solution code:
from sys import stdin

D = 60
MAX_N = 200005


def input():
    return stdin.readline()[:-1]

def main():
    from builtins import int, map
    N, K = map(int, input().split())
    to = [[None for _ in range(N)] for _ in range(D)]
    to[0] = list(map(lambda x: int(x) - 1, input().split()))
    for i in range(D - 1):
        for j in range(N):
            to[i + 1][j] = to[i][to[i][j]]

    v = 0
    for i in range(D - 1, -1, -1):
        l = 1 << 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(lambda a: int(a) - 1, input().split()))

T = [A]
for _ in range(64):
    prev = T[-1]
    T.append([prev[a] for a in prev])

now = 0
for d, P in enumerate(T):
    if ((1 << d) & K) > 0:
        now = P[now]
print(now + 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
used = set()
num = [0]*n
used.add(0)
now = 0
cnt = 0
while True:
    cnt += 1
    if not a[now] in used:
        used.add(a[now])
        num[a[now]] = cnt
        now = a[now]
    else:
        lps = a[now]
        mod = cnt - num[a[now]]
        # k %= mod
        break
now = 0
# print(mod, lps, k, num)
while k:
    if now == lps:
        k %= mod
    if k == 0:
        break
    now = a[now]
    k -= 1

print(now+1)

Submission status: Accepted

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

T = [A[:]]
for _ in range(64):
    prev = T[-1]
    T.append([prev[a] for a in prev])

now = 0
for d, P in enumerate(T):
    if ((1 << d) & K) > 0:
        now = P[now]
print(now + 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
path = []
now = 0
used = [False]*N
while not used[now]:
    path.append(now)
    used[now] = True
    now = A[now]

s = path.index(now)
loop_len = len(path) - s
if K < s:
    print(path[K] + 1)
else:
    print(path[(K-s)%loop_len + s] + 1)

Submission status: Accepted

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

b = []
ord = [-1 for x in range(n+1)]
c = 1
l = 1

v = 1
while(ord[v] == -1):
    ord[v] = len(b)
    b.append(v)
    v = a[v-1]
c = len(b) - ord[v]
l = ord[v]

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

Submission status: Accepted

Solution code:
def main():
    # ダブリング
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    T = [[0]*(N+1) for _ in range(61)]
    T[0][1:] = A
    for t in range(1, 61):
        for i in range(1, N+1):
            T[t][i] = T[t-1][T[t-1][i]]
    v = 1
    B = "{:0b}".format(K)[::-1]
    for i, b in enumerate(B):
        if b == "1":
            v = T[i][v]
    print(v)


if __name__ == '__main__':
    main()

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

used = [False]*N
path = []
now = 0
while not used[now]:
    path.append(now)
    used[now] = True
    now = A[now]
# print(now)
# print(path)

# ループがpath(0-indexed)に格納されてループの始点がnow
start_idx = path.index(now)
# print(start_idx)
loop_len = len(path) - start_idx
if K < start_idx:
    print(path[K] + 1)
else:
    print(path[(K-start_idx)%loop_len + start_idx] + 1)

Submission status: Accepted

Solution code:
import sys

N, K = list(map(int, sys.stdin.readline().split()))
A = [None] + list(map(int, sys.stdin.readline().split()))

dist = [None, 0] + [None] * (N-1)
cycle_len = None
i = 0
town = 1

while True:
    next_town = A[town]
    if dist[next_town] is None:
        dist[next_town] = i+1
    elif cycle_len is None:
        cycle_len = i + 1 - dist[next_town]
        K = K % cycle_len
    
    if K <= 0:
        break
    
    town = next_town
    i += 1
    K -= 1

print(town)

Submission status: Accepted

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

b = []
ord = [-1 for x in range(n+1)]
c = 1
l = 1

v = 1
#while(ord[v] == -1):
for x in range(n):
    if (ord[v] != -1):
        break
    ord[v] = x
    b.append(v)
    v = a[v-1]
c = len(b) - ord[v]
l = ord[v]

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

Submission status: Accepted

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

used_dict = {}
used_list = []

current_node = 0

while True:
    if current_node not in used_dict:
        used_dict[current_node] = True
        used_list.append(current_node)
        current_node = a_list[current_node]-1
    else:
        break

repeat_index = used_list.index(current_node)
repeat_list = used_list[repeat_index:]
repeat_length = len(used_list) - repeat_index

if k > repeat_index:
    amari = (k-repeat_index) % repeat_length
    print(repeat_list[amari]+1)
else:
    print(used_list[k]+1)

Submission status: Accepted

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

cnt, pre = [0]*N, 0
for _ in range(N*2):
    cnt[pre] += 1
    pre = A[pre]

one, loops = 0, 0
for c in cnt:
    if c == 1: one += 1
    elif c > 1: loops += 1

k = max(0, K-one) % loops + min(K, one)

pre = 0
for _ in range(k): pre = A[pre]
print(pre + 1)

Submission status: Accepted

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

from collections import deque 
tmp = 1
num = []
seen = [-1]*(N+1)
 
while seen[tmp] == -1:
    seen[tmp] = tmp
    num.append(tmp)
    tmp = A[tmp]


l = num.index(tmp)
c = len(num) - l

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

Submission status: Accepted

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

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

one = 0
loops = 0
for c in cnt:
    if c == 1: one += 1
    elif c > 1: loops += 1

k = max(0, K-one) % loops + min(K, one)

pre = 0
for _ in range(k):
    now = A[pre]
    pre = now

ans = pre + 1
print(ans)

Submission status: Accepted

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

ans = deque()
ans.appendleft(1)
count = 1
s = -1
zeros = [0]*n

while True:
    if zeros[a[count-1]-1] == 1:
        s = a[count-1]
        break
    else:
        ans.append(a[count-1])
        zeros[count-1]=1
        count = a[count-1]

ans = list(ans)
if s == -1:
    print(ans[k])
else:
    t = ans.index(s)
    if t >= k:
        print(ans[k])
    else:
        ans = ans[t:]
        print(ans[(k-t)%len(ans)])

Submission status: Accepted

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

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


one = 0
loops = 0
for c in cnt:
    if c == 1: one += 1
    elif c > 1: loops += 1

# k = max(0, K-one) % loops + one
k = max(0, K-one) % loops + min(K, one)

# print('N,K',N,K)
# print('A',A)
# print('cnt',cnt)
# print('one',one,'loops', loops)
# print('K-one',K-one)
# print('min(0, K-one) \% loops',max(0, K-one) % loops)
# print('k',k)

pre = 0
for _ in range(k):
    now = A[pre]
    pre = now

ans = pre + 1
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
l = [1]
b = [1] + [0] * (n-1)
for i in range(n):
  b[a[l[i]-1]-1] += 1
  if b[a[l[i]-1]-1] == 2:
    break
  else:
    l.append(a[l[i]-1])

lindex = l.index(a[l[i]-1])
r = len(l) - lindex
rlist = l[lindex:]

if k >= lindex:
  kmod = (k - lindex) % r
  ans = rlist[kmod]
else:
  ans = l[k]
  
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
count=0
lst={}
lst2=[]
now=1
c=0

while True:
    lst2.append(now)
    lst[now]=c
    now=a[now-1]
    if now in lst:
        break
    c+=1



amari=lst[now]
looplen=c-lst[now]+1


if k<=amari:
    print(lst2[k])

else:
    newlst=lst2[amari:]
    
    newk=k-amari
    num=newk%looplen
    print(newlst[num])

Submission status: Accepted

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

pos = [1]

for i in range(2 * n):
	nxt = A[pos[-1]]
	pos.append(nxt)

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

loop_end = n
loop_start = n - 1

while pos[loop_start] != pos[loop_end]:
	loop_start -= 1

period = loop_end - loop_start
m = n - period
k = m + (k - m) % period

print(pos[k])

Submission status: Accepted

Solution code:
def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    d = [-1]*(N+1)
    v = 1
    i = 0
    P = []
    while d[v] == -1:
        P.append(v)
        d[v] = i
        v = A[v-1]
        i += 1
    c_length = i - d[v]  # 閉路長
    pre_c_length = d[v]
    if K < i:
        return print(P[K])
    else:
        K -= pre_c_length
        K %= c_length
        return print(P[pre_c_length+K])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(input().split())
p = [0]*200000
q = [0]*200000
p[0]=1
p[1]=int(a[0])
q[0]=1
q[p[1]-1]=2
f=0
for i in range(k-1):
    p[i+2]=int(a[p[i+1]-1])
    if q[p[i+2]-1]>0:
        r=q[p[i+2]-1]-1
        q=i+2-r
        f=1
        l=k-r
        l%=q
        s=p[r+l]
        break
    if f==1:
        break
    q[p[i+2]-1]=i+3
if f==0:    
    print(p[k])
else:
    print(s)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
now = 0
loop = []
flag = [0 for _ in range(n)]
for _ in range(n):
    loop.append(now+1)
    if flag[now]:
        break
    else:
        flag[now] = 1
        now = a[now]-1
tloop = loop[loop.index(loop[-1]):len(loop)-1]
floop = loop[:loop.index(loop[-1])]
if k < len(floop):
    print(floop[k])
else:
    k -= len(floop)
    print(tloop[k%len(tloop)])

Submission status: Accepted

Solution code:
def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    d = [-1]*(N+1)
    v = 1
    i = 0
    while d[v] == -1:
        d[v] = i
        v = A[v-1]
        i += 1
    c_length = i - d[v]  # 閉路長
    pre_c_length = d[v]
    if K < i:
        return print(d.index(K))
    else:
        K -= pre_c_length
        K %= c_length
        return print(d.index(pre_c_length+K))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
s = []
o = [-1] * (n + 1)  # ord 訪れた箇所, v が1スタートなので注意
c, l = 1, 0  # 周期, 例外

v = 1
while o[v] == -1:
    o[v] = len(s)
    s.append(v)
    v = a[v-1]
c = len(s) - o[v]
l = o[v]

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

Submission status: Accepted

Solution code:
# 4 5 (4 cities and 5 steps)
# 3 2 4 1

# 1 => 3
# 2 => 2
# 3 => 4
# 4 => 1

# 1 (0)
# 1 => 3 (1)
# 3 => 4 (2)
# 4 => 1 (3)

# 2 を作る 5 と2 と 1 を使う
# 2  = (5 - 3) % 2 + 3 - 1

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

paths = {}

for i in range(N):
    paths[i+1] = A_i[i]

# print('paths:', paths)

# 6 5 2 5 3 2

# 1 => 6 (1)
# 6 => 2 (2)
# 2 => 5 (3)
# 5 => 3 (4)
# 3 => 2 (5)

# loop_steps = 5 - 2 - 1 = 2
# 5 + 2 * m + r = 727202214173249351
# steps + loop_steps * m + r = K
# r = (K - steps) % loop_steps

state = 1
steps = 0
flag = False
known_states = {}

while steps < K:
    known_states[state] = steps # state => 2, steps => 2

    state = paths[state] # state => 5
    steps += 1 # steps => 3

    # print(f'steps: {steps}, state: {state}')

    if state in known_states and not flag: # state => 2 steps => 5
        loop_steps = steps - known_states[state]
        K = (steps - loop_steps) + (K - (steps - loop_steps))  % loop_steps
        # print('loop_steps:', loop_steps)
        # print('steps - loop_steps:', steps - loop_steps)
        # print('K:', K)
        state = 1
        steps = 0
        # print('steps:', steps)
        flag = True
        # print('loop detected')



print(state)

Submission status: Accepted

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

end_idx, start_idx = 0, 0
dup = {}
for i, j in enumerate(journey):
    if j in dup:
        end_idx = i
        break
    else:
        dup[j] = 0
for i, j in enumerate(journey):
    if j == journey[end_idx]:
        start_idx = i
        break

if K <= start_idx:
    print(journey[K])
    exit()
b = end_idx - start_idx
m = (K - start_idx) % b
print(journey[start_idx + m])

Submission status: Accepted

Solution code:
# ダブリングを使って解く
n, k = map(int, input().split())
a = list(map(int, input().split()))

cur = 0
pre_doubling = list(range(1, n+1))
doubling = a[:]
while k > 0:
    if k & 1:
        cur = doubling[cur] - 1
    k >>= 1
    pre_doubling = doubling[:]
    for i in range(n):
        doubling[i] = pre_doubling[pre_doubling[i]-1]
print(cur+1)

Submission status: Accepted

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

genzaichi=1
rireki=set()
houmon=[0]*(N+1)
flag=0

for i in range(1,K+1):
    genzaichi=A[genzaichi-1]
    if genzaichi not in rireki:
        houmon[genzaichi]=i
        rireki.add(genzaichi)
    else:
        roop_from=genzaichi
        x=houmon[roop_from]
        roop=i-x
        flag=1
        break

if flag==0:
    print(genzaichi)
else:
    genzaichi=roop_from
    K=(K-x)-((K-x)//roop)*roop
    for i in range(K):
        genzaichi=A[genzaichi-1]
    print(genzaichi)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = [1]
c = 1
for i in range(n):
    ans.append(a[ans[i] - 1])
b = ans.index(ans[n])
if k < b:
    for l in range(k):
        c = a[c - 1]
else:
    for l in range((k-b)%(n-b)+b):
        c = a[c - 1]
print(c)

Submission status: Accepted

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

"""
1からのループだけを考えれば良い
"""

i = A[0]
ok = True
R = [1]
seen = [0] * N
seen[0] = 1
count = 1

if A[0] == 1:
    print(1)
    exit()

while ok:
    count += 1
    seen[i-1] += count
    R.append(i)
    i = A[i-1]
    # 訪れたことがあれば
    if seen[i-1] != 0:
        k = seen[i-1]
        loop = R[k-1:]
        remain = R[:k-1]
        ok = False

L = len(loop)

if K < len(remain):
    print(remain[K])
else:
    print(loop[(K - len(remain)) % L])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    if A[0]==1:
        print(1)
        sys.exit()
    cur_a=1
    cunt=0
    visited=[False]*n
    visited[0]=True
    route=[1]
    for _ in range(k):
        next_a=A[cur_a-1]
        if visited[next_a-1]:
            loop=len(route)-route.index(next_a)
            cunt-=loop-1
            break
        cur_a=next_a
        cunt+=1
        route.append(cur_a)
        visited[cur_a-1]=True
    else:
        print(next_a)
        sys.exit()
    #print(route)
    #rint(cunt,loop)
    k-=cunt
    k=k%loop
    #print(k)
    print(route[cunt+k])
    

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a_list = list(map(int,input().split()))
a = 0
t = 1
d = 0
hoge_list = []
hoge_set = set()
while a < k:
  hoge_list.append(t)
  hoge_set.add(t)
  t = a_list[t-1]
  a += 1
  if t in hoge_set:
    b = hoge_list.index(t)
    d += 1
    break
if d == 0:
  print(t)
else:
  e = (k-b)%(a-b)
  print(hoge_list[b+e])

Submission status: Accepted

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

cnt = 0
dic = {1:0}
x = 1
for i in range(N):
    y = A[x-1]
    cnt += 1
    if y in dic:
        x = y        
        break
    else:
        dic[y] = cnt
        x = y

    if cnt == K:
        print(y)
        quit()
       
loop = (K-dic[x]) % (cnt - dic[x])

for i in range(loop):
    x = A[x-1]
print(x)

Submission status: Accepted

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

pos = [1]

for i in range(2 * n):
	nxt = A[pos[-1]]
	pos.append(nxt)

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

loop_end = n
loop_start = n - 1

while pos[loop_start] != pos[loop_end]:
	loop_start -= 1

period = loop_end - loop_start
k = k % period

while k < n:
	k += period

print(pos[k])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(lambda x: int(x) - 1, input().split())

    t = 0
    while K:
        if K & 1:
            t = A[t]
        nA = [0] * N
        for i in range(N):
            nA[i] = A[A[i]]
        A = nA
        K >>= 1
    print(t + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=tuple(map(int,input().split()))
s=1
state=[s]
count={}
for i in range(1,k+1):
    s=A[s-1]
    if s in count:
        start=state.index(s)
        end=len(state)
        print(state[start+(k-start)%(end-start)])
        break
    else:
        count[s]=i
        state.append(s)
        continue
else:
    print(s)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(n) - 1 for n in input().split()]  # indexに合うように調整する
v = [-1] * n  # 到達してるかどうかを格納するリスト

D = [0]  # Dは循環するもののindexを格納する
v[0] = 0  # 初期スタート位置の到達ステータスは0

cur = a[0]  # 初期位置はindex=0
i = 1

while v[cur] == -1:
    D.append(cur)
    v[cur] = i # 到達済みに変更(iは何番目に到達したか）
    if k == i:  # 循環が発生する前にkの上限に達してしまった場合
        print(cur + 1)
        exit()

    i += 1
    cur = a[cur]

# 循環している場合を考える
k -= v[cur]  # 1回目の到達点を引く
k %= (i - v[cur])  # kを循環する回数で割った余りを考える = 循環した中でどれかという事が分かる

print(D[v[cur] + k] + 1)  # v[cur]で循環しない部分を表し、kで循環した中でどこかを表す

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
now=1
if k<=n:
  for i in range(k):
    now=a[now-1]
  print(now)
  exit()
# 絶対ループする
visited=[False]*n
visited[now-1]=-1
for i in range(4*10**5):
  now=a[now-1]
  if visited[now-1]==False:
    visited[now-1]=i
  else:
    c,d=visited[now-1],i
    break

k=(k-c)%(d-c)+c
while k<n:
  k+=(d-c)
now=1
for i in range(k):
  now=a[now-1]
print(now)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())

now=1
if k<=n:
  for i in range(k):
    now=a[now-1]
  print(now)
  exit()
# 絶対ループする
visited=[False]*n
visited[now-1]=-1
for i in range(4*10**5):
  now=a[now-1]
  if visited[now-1]==False:
    visited[now-1]=i
  else:
    c,d=visited[now-1],i
    break

k=(k-c)%(d-c)+c
while k<n:
  k+=(d-c)
now=1
for i in range(k):
  now=a[now-1]
print(now)

Submission status: Accepted

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

teleport = [-1] * (N+1)
teleport[0] = 1
visited = [(False, -1)] * (N+1)
visited[1] = (True, 0)

for i in range(1, N+1):
    next_town = A[teleport[i-1]-1]
    if visited[next_town][0]:
        before = visited[next_town][1]
        now = i
        break
    teleport[i] = next_town
    visited[next_town] = (True, i)

if K < before:
    print(teleport[K])
else:
    K -= before
    period = now - before
    K %= period
    print(teleport[before + K])

Submission status: Accepted

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

repeat = [0] * (n+1)
circle = [1]
point = 1
flag = 0
for _ in range(k):
    circle.append(a[point])
    repeat[point] = 1
    point = a[point]
    if(repeat[point] == 1):
        flag = 1
        break

if flag == 0:
    print(circle[-1])
else:
    index = circle.index(point)
    circle_cut = circle[index:-1]
    k = (k-index) % len(circle_cut)
    print(circle_cut[k])

Submission status: Accepted

Solution code:
def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    cnt = [-1] * n
    cnt[0] = 0
    ary = []
    now = 0
    for i in range(n):
        a[i] -= 1

    ary.append(now)
    if k <= n:
        for i in range(1,k+1):
            now = a[now]
            if i == k:
                print(now+1)
                return
    else:
        for i in range(1,k+1):
            now = a[now]
            if cnt[now] != -1:
                break
            else:
                cnt[now] = i
                ary.append(now)
        loop_s = cnt[now]

        print(ary[cnt[now] +((k-cnt[now]) % (i - cnt[now]))] + 1)
        # print(cnt)
        # print(now)
        # print(ary)

if __name__=='__main__':
    main()