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:
# coding: utf-8


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A = [a-1 for a in A]  # 0-index

    cnt = 0
    i = 0
    # appeared = [0]
    appeared = [False] * N
    appeared[0] = True
    arrive = [None] * (N+1)
    arrive[0] = 0
    roop_s = None
    n_roop = None
    for k in range(N):
        i = A[i]
        cnt += 1

        if cnt == K:
            return i+1

        if appeared[i]:
            for j in range(N+1):
                if arrive[j] == i:
                    roop_s = j
                    n_roop = (k+1) - roop_s
                    break
        # if i in appeared:
            # for j in range(len(appeared)):
            #     if appeared[j] == i:
            #         roop_s = j
            #         n_roop = len(appeared) - roop_s
            #         break

            break

        # appeared.append(i)
        appeared[i] = True
        arrive[k+1] = i

    # K > cnt
    rest = (K-roop_s) % n_roop
    # i = appeared[roop_s]
    i = arrive[roop_s]
    for _ in range(rest):
        i = A[i]

    return i+1


print(main())

Submission status: Accepted

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
sys.setrecursionlimit(10**7)

N, K = map(int, input().split())
a = map(int, input().split())
a = [a-1 for a in a]

first = 0
second = 0
cnt = 0
visited = [0] * N
city = [None] * N

def nex_node(x):
    global first
    global second
    global cnt
    city[cnt] = x
    cnt += 1

    if visited[x] > 0:
        first = visited[x]
        second = cnt
        val = K - first +1
        idx = val % (second - first)
        # print(first, second, idx)
        # print(city)
        print(city[first - 1 +idx] + 1)
        sys.exit()

    visited[x] = cnt

    # print(x, cnt, a[x])
    if cnt == K:
        # print(city)
        print(a[x]+1)
        sys.exit()
    if a[x] == x:
        print(x+1)
        sys.exit()

    nex_node(a[x])


nex_node(0)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = [0]+list(map(int,input().split()))
visit = [-1]*(N+1)
point = 1
notloop_cnt = 0
while(visit[point]==-1):
    visit[point] = 1
    point = A[point]
    notloop_cnt += 1
s_point = point
loop_cnt = 0
visit = [-1]*(N+1)
while(visit[point]==-1):
    visit[point] = 1
    point = A[point]
    loop_cnt += 1
    
visit = [-1]*(N+1)
if(K<=notloop_cnt):
    point,cnt = 1,0
    while(cnt != K):
        point = A[point]
        cnt += 1
    print(point)
else:
    K = (K-notloop_cnt)%loop_cnt
    point = s_point
    cnt = 0
    while(cnt != K):
        point = A[point]
        cnt += 1
    print(point)

Submission status: Accepted

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

table = [0]
dic = dict()
dic[0] = 1

nxt = a[0] - 1
x = None

while True:
    table.append(nxt)
    if not nxt in dic:
        dic[nxt] = 1
    else:
        x = nxt
        break
    nxt = a[nxt] - 1
    
cnt = 0
while table[cnt] != x:
    cnt += 1

roop = len(table) - 1 - cnt

if k <= cnt:
    print(table[k] + 1)
else:
    k -= cnt
    k %= roop
    print(table[cnt + k] + 1)

Submission status: Accepted

Solution code:
#author: raghav_0901
from math import *

mod = (10**9) + 7


def _in():
    return [int(x) - 1 for x in input().split(' ')]


def main():
    n, k = [int(x) for x in input().split(' ')]
    arr, dp = _in(), [0, ]
    vis = [False] * (n)
    vis[0], nxt = True, arr[0]
    while(not vis[nxt] and len(dp) <= k):
        dp.append(nxt)
        vis[nxt] = True
        nxt = arr[nxt]
    if(len(dp) == k + 1):
        print(dp[-1] + 1)
    else:
        i = 0
        while(dp[i] != nxt):
            k, i = k - 1, i + 1
        rem = k % (len(dp) - i)
        print(dp[rem + i] + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
history = []
mark = set()

pos = 0
cnt = 0
while pos not in mark and cnt < k:
  history.append(pos)
  mark.add(pos)
  pos = a[pos] - 1
  cnt += 1

if cnt == k:
  print(pos + 1)
else:
  cnt_before = history.index(pos)
  print(history[cnt_before + (k - cnt_before) % (cnt - cnt_before)] + 1)

Submission status: Accepted

Solution code:

input = raw_input
n, k = map(int, input().split(" "))

a_list = [int(a)-1 for a in  input().split(" ")]
uses = [-1] * n
path = [-1] * n
path[0] = 0
uses[0] = 0

count = 0
cur = 0
end = False
for i in range(n):
    count += 1
    cur = a_list[cur]
    if k == count:
        end = True
        break

    if uses[cur] != -1:
        break
    uses[cur] = count
    path[count] = cur

if end:
    out = cur+1
else:
    shuuki = count - uses[cur]

    shift = uses[cur]
    k1 = (k - shift) % shuuki + shift
    out = path[k1] + 1

print(out)

Submission status: Accepted

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

ls = [0]*N

count = 0
now = 0
roop = 0

while ls[now] == 0 and count < K:
    ls[now] = 1
    now = A[now] - 1
    count += 1
k = K - count
if k > 0:
    while ls[now] == 1:
        ls[now] = 2
        now = A[now] - 1
        roop += 1

    k = k%roop

    while k > 0:
        now = A[now]-1
        k -= 1

print(now+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
s=[]
s.append(1)
a1=1
a2 = a[a1-1]
l=[0]*n
l[0]=1

while l[a2-1] != 1:
    s.append(a2)
    a1 = a2
    a2 = a[a1-1]
    l[a1-1] = 1

loop_num=s.index(a2)
loop=s[loop_num:]
cnt=len(loop)

if k<len(s):
    print(s[k])
else:
    ans = (k-loop_num)%cnt
    print(loop[ans])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
adic = {}
for s in range(n):
  adic[s+1] = a[s]
if k<=10**6:
  kpos = 1
  for i in range(k):
    kpos = adic[kpos]
  print(kpos)
else:
  passpt = set()
  passpt.add(1)
  kpos = 1
  looppt = 0
  for i in range(4*(10**5)):
    kpos = adic[kpos]
    if kpos in passpt:
      looppt = kpos
      break
    else:
      passpt.add(kpos)
  kpos = looppt
  looppass = set()
  for i in range(4*(10**5)):
    kpos = adic[kpos]
    if kpos in looppass:
      break
    else:
      looppass.add(kpos)
  remk = (k-len(passpt))%len(looppass)
  kpos = looppt
  for i in range(remk):
    kpos = adic[kpos]
  print(kpos)

Submission status: Accepted

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

p = [-1] * N
p[0] = 0
flag = 0
now = 1
i = 0

while flag == 0:
    i += 1
    now = A[now - 1]
    if p[now - 1] != -1:
        flag = 1
    else:
        p[now - 1] = i
    if i == K:
        flag = 2
if flag == 2:
    print(now)

else:
    r = i - p[now - 1]
    e = p[now - 1]

    count = K - e
    pi = count % r

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

    print(now)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

def main():
    n,k = mi()
    a =li()

    fp = [0] * n

    nxt = 0
    for i in range(1,n+10):
        
        idx = a[nxt]-1
        # print('idx',idx)
        if i == k:
            print(idx+1)
            return
        elif fp[idx] > 0:
            rs = fp[idx]
            re = i
            break
        
        else:
            fp[idx] = i
            nxt = idx

    roop_count = re - rs

    modd = (k - rs)%roop_count
    for i in range(modd):
        idx = a[idx]-1
    print(idx+1)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
used=[-1]*n
pos=0
flag=False
loop=0

for i in range(k):
    used[pos]=i
    pos=a[pos]-1
    if used[pos]!=-1:
        flag=True
        loop=i+1
        break
    
if flag:
    loop-=used[pos]
    start=used[pos]
    mins=start+(k-start)%loop
    
    pos=0
    for i in range(mins):
        pos=a[pos]-1


print(pos+1)

Submission status: Accepted

Solution code:
from itertools import combinations

import numpy as np


def run():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))

    history = [0 for _ in a_list]

    history[0] = 1

    current_a = 1
    loop_num = 0
    history_flag = True
    while True:
        next_a = a_list[current_a - 1]

        if history[next_a - 1] != 0 and history_flag:
            pre_visit = history[next_a - 1]
            current_visit = loop_num + 2

            same_loop_num = (current_visit - pre_visit)

            loop_num += same_loop_num * ((k - loop_num) // same_loop_num - 1)
            history_flag = False
            # print('hit')
            # print(loop_num)
            # print(same_loop_num)

        history[next_a - 1] = loop_num + 2
        current_a = next_a

        loop_num += 1
        if loop_num == k:
            print(current_a)
            exit()
        if loop_num > k:
            print('error')
            print(loop_num)
            print(k)
            raise ValueError()


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
C = {i:0 for i in range(1,N+1)}
loop = [1]
C[1] = 1
tmp = A[0]
for i in range(N):
    x = A[tmp-1]
    #print(x)
    if C[x] == 1:
        loop.append(tmp)
        X = x
        break
    else:
        loop.append(tmp)
        C[x] = 1
        tmp = x
#print(loop)
lenloop = len(loop)
tail = 0
for i in loop:
    if i != X:
        tail += 1
    else:
        break
if K > tail:
    loop = loop[tail:]
    K -= tail
    lenloop -= tail
    XX = K % lenloop
    ans = loop[XX]
    #print(tail,loop,XX)
else:
    ans = loop[K]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(lambda: -1)
d[1] = 0
L = [1]
i = 0
k = i
while i<N:
    if d[A[k]]==-1:
        d[A[k]] = i+1
        L.append(A[k])
        k = A[k]-1
    else:
        p = d[A[k]]
        q = i+1
        break
    i += 1

try:
    print(L[K])
except:
    L = L[p:]
    print(L[(K-p)%(q-p)])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
vidited = [False] * (N+1)
ans = [1, A[1]]
vidited[1] = True
vidited[A[1]] = True
step = 1
n2i = {1:0, A[1]:1}
while step < K:
    next_a = A[ans[-1]]
    if vidited[next_a]:
        break
    # if next_a == 1:
    #     break
    step += 1
    n2i[next_a] = step
    vidited[next_a] = True
    ans += [next_a]
# print(ans)
# print(ans[(K)%len(ans)])
if step >= K:
    print(ans[K])
else:
    # print(step, n2i[next_a])
    # print(n2i[next_a], K-n2i[next_a], step-n2i[next_a])
    print(ans[n2i[next_a]+(K-n2i[next_a])%(step+1-n2i[next_a])])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
teleport_list = list(map(int, input().split()))
t_cycle = [1]
c_set = set([1])
now = 1
while len(t_cycle) == len(c_set):
  now = teleport_list[now-1]
  t_cycle.append(now)
  c_set.add(now)

start_cycle = t_cycle[-1]
before_cycle_len = t_cycle.index(start_cycle)
cycle_len = len(t_cycle) - t_cycle.index(start_cycle) - 1

if k <= before_cycle_len:
  print(t_cycle[k])
else:
  print(t_cycle[(k-before_cycle_len)%cycle_len + before_cycle_len])

Submission status: Accepted

Solution code:
def find_cycle_start(A, start=1):
    N = len(A)
    next_nodes = [a - 1 for a in A]
    start -= 1
    visited = [0 for _ in range(N)]
    node = start
    visited[node] = 1
    for _ in range(N):
        node = next_nodes[node]
        if visited[node] == 1:
            break
        visited[node] = 1
    return node + 1  # start of cycle


def main():
    N, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    cycle_start = find_cycle_start(A)
    offset = list()
    a = 1
    while True:
        a = A[a - 1]
        if a == cycle_start:
            break
        offset.append(a)
    cycle = [cycle_start]
    period = 0
    for _ in range(N):
        a = A[a - 1]
        period += 1
        if a == cycle_start:
            break
        cycle.append(a)
    # calculate answer
    if K <= len(offset):
        print(offset[K - 1])
    else:
        rest = K - len(offset)
        print(cycle[(rest - 1) % period])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰回数の上限を変更
from collections import deque

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

L=[]
chk=[0 for _ in range(N)]
tmp=0
while(1):
    if chk[tmp]==1:
        break
    chk[tmp]=1
    L.append(tmp)
    tmp=A[tmp]-1
#print(L)
loop_s=A[L[-1]]-1
loop_g=L[-1]
one_to_s=0
tmp=0
#print(loop_s)
#print(loop_g)

while(1):
    if tmp==loop_s:
        break
    tmp=A[tmp]-1
    #print(tmp)
    one_to_s+=1

loop_l=0
tmp=loop_s
Loop=[loop_s]
while(1):
    if tmp==loop_g:
        break
    tmp=A[tmp]-1
    Loop.append(tmp)
    loop_l+=1
loop_l+=1
#print(one_to_s)
if K<=one_to_s:
    tmp=0
    #print("ON")
    cnt=0
    while(1):
        if cnt==K:
            break
        tmp=A[tmp]-1
        cnt+=1
    ans=tmp + 1
else:
    K-=one_to_s
    num=K%loop_l
    ans=Loop[num]+1

print(ans)

Submission status: Accepted

Solution code:
n,k = [int(e) for e in input().split(" ")[:2]]
a_ls = [int(e) for e in input().split(" ")[:n]]

a_dic = {i+1: a_ls[i] for i in range(n)}
v_f_dic = {i+1: False for i in range(n)}

pos = 1
v_ls = [pos]
v_f_dic[pos] = True
# 繰り返しの探索
for i in range(k):
	# 更新
	pos = a_dic[pos]
	v_ls.append(pos)
	if v_f_dic[pos] is True:
		# 繰り返しの長さを計算
		idx0, idx1 = [i for i,e in enumerate(v_ls) if e == pos][:2]
		rep_l = idx1 - idx0
		rep_ls = v_ls[idx0:idx1]
		ans_idx = (k-idx0)%rep_l
		print(rep_ls[ans_idx])
		import sys
		sys.exit()
	v_f_dic[pos] = True
print(pos)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[0]
aa=list(map(int,input().split()))
for i in range(n):
    a.append(aa[i])
count=[0]*(n+1)
now=1
r=[]
kaburi=-1
for i in range(1,n+1):
    if count[now]==0:
        count[now]=1
        r.append(now)
        now=a[now]
    else:  
        kaburi=now
        break
# print(r)
syuki=len(r)
kaburi_i=0
for i in range(syuki):
    if kaburi==r[i]:
        kaburi_i=i
num=syuki-kaburi_i #何周期か
#print(num)
if k<kaburi_i:
    print(r[k])
else:
    ind=k-kaburi_i
    ind=ind%num
    print(r[kaburi_i+ind])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
l1=[0]*(n+1)
l2=[1]
a=0
l1[1]=1
while 1:
    if l1[l[a]]==1:
        l2.append(l[a])
        break
    l2.append(l[a])
    l1[l[a]]=1
    a=l[a]-1
if k<=len(l2)-1:
    print(l2[k])
else:
    a=l2.index(l2[-1])
    b=len(l2)-a-1
    c=(k-len(l2)+1)%b
    print(l2[a+c])

Submission status: Accepted

Solution code:
N,K = list(map(int, input().split()))
A = list(map(int, input().split()))
now = 1
path = [1]
flag = []
for i in range(N):
  if(i==0):
    flag.append(1)
  else:
    flag.append(0)
for i in range(N):
  now = A[now - 1]
  if(flag[now - 1] == 0):
    path.append(now)
    flag[now - 1] += 1
  else:
    break
roop = [path[len(path) - 1]]
for i in range(N):
  now = A[roop[i] - 1]
  if(flag[now - 1] == 1):
    roop.append(now)
    flag[now - 1] += 1
  else:
    break
roop.pop(0)
if(K <= len(path) - 1):
  print(path[K])
elif(K == len(path)):
  print(roop[0])
else:
  print(roop[(K - len(path))%len(roop)])

Submission status: Accepted

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

ls = [1]
s = {1}
cnt = 0
flag = 0
for i in range(K):
    t = A[ls[-1]-1]
    if t in s:
        nls = ls[ls.index(t):]
        flag = 1
        break
    else:
        ls.append(t)
        s.add(t)
        cnt += 1
        
if flag == 1:
    nokori = K-cnt-1
    amari = nokori % len(nls)
    print(nls[amari])
else:
    print(ls[-1])

Submission status: Accepted

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

otozureta = []

otozureta2 = [0]
for i in range(n):
    otozureta.append(False)
otozureta[0] = True

flag = False
i = 0
loop = 0
looppoint = 0

while not flag:
    genzai = otozureta2[i]
    next = a[genzai] - 1
    otozureta2.append(next)

    if not otozureta[next]:
        otozureta[next] = True
        i = i + 1
    else:
        loop = i - otozureta2.index(next) + 1
        looppoint = otozureta2.index(next)
        flag = True

if k < looppoint:
    print(otozureta2[k] + 1)
else:
    print(otozureta2[((k - looppoint) % loop) + looppoint] + 1)

Submission status: Accepted

Solution code:
def ma():
    return map(int,input().split())
def main():
    n,k=ma()
    A=list(ma())
    ans=[]
    exp=[0]*(n+1)
    now=1
    
    while True:
        ans.append(now)
        exp[now]=1
        now=A[now-1]
        if exp[now]==1:
            use=ans.index(now)
            tool=len(ans)-use
            break 

    if use>=k:
        print(ans[k])
        exit()
    else:
        p=(k-use)%tool
        print(ans[use+p])

main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
chk = [0] * N
start = -1
ido = [0]
chk[0] = 1
index = 0
cnt = 0

while True:
    index = a[index] - 1
    if chk[index] == 0:
        chk[index] += 1
        cnt += 1
        ido.append(index)
    else:
        start = index
        break

if cnt >= K:
    print(ido[K] + 1)
    exit()
tmp = ido.index(start)
ido = ido[tmp:]
K -= tmp

print(ido[K % len(ido)] + 1)

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, K = read_ints()
    A = [a-1 for a in read_ints()]
    distance = [-1]*N
    i = 0
    k = K
    while k > 0:
        if distance[i] != -1:
            cycle_length = K-k-distance[i]
            k %= cycle_length
            if k == 0:
                break
        else:
            distance[i] = K-k
        i = A[i]
        k -= 1
    return i+1


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import sys


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


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    went = [0] * N
    went[0] = 1
    Flag = True
    check = [0]
    cnt = 1
    now = 0
    while Flag and (cnt <= K + 1):
        now = A[now] - 1
        if went[now] == 1:
            ind = check.index(now)
            if ind == 0:
                cnt = len(check)
            else:
                cnt = len(check) - ind

            Flag = False
        else:
            check.append(now)
            went[now] = 1
            cnt += 1
            continue

    if len(check) > K:
        print(check[K] + 1)
    else:
        if ind == 0:
            K = K % cnt
            print(check[K] + 1)
        else:
            ind -= 1
            K = (K - ind - 1) % cnt
            print(check[ind + K + 1] + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

List=[0]*n
pattern=[1]
now=0
nex=0
List[0]=1
end_flag=0

while end_flag==0:
    nex=a[now]
    if (List[nex-1]==1):
        target1=nex
        end_flag=1
        break
    else:
        List[nex-1]+=1
        pattern.append(nex)
        now=nex-1

left=pattern.index(target1)
right=len(pattern)
kaisu=right-left
kaisu2=(k-right)%kaisu


if (k<=right-1):
    print(pattern[k])
else:
    print(pattern[left+kaisu2])

Submission status: Accepted

Solution code:
import sys
import math
from  collections import defaultdict

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

def solve(test):
	n, k = map(int, input().split())
	a = list(map(int, input().split()))
	fast = 1
	slow = 1
	fast = a[a[fast - 1] - 1]
	slow = a[slow - 1]
	while fast != slow:
		fast = a[a[fast - 1] - 1]
		slow = a[slow - 1]

	fast = 1
	count = 0
	while fast != slow:
		fast = a[fast - 1]
		slow = a[slow - 1]
		count += 1

	res = 1
	if k < count:
		while k:
			res = a[res - 1]
			k -= 1
		print(res)
		return
	k -= count

	cycle = 1
	fast = a[fast - 1]
	while fast != slow:
		fast = a[fast - 1]
		cycle += 1

	k %= cycle

	while k:
		fast = a[fast - 1]
		k -= 1

	print(fast)







if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Submission status: Accepted

Solution code:
def resolve():
    n, g = map(int, input().split())
    a = list(map(int, input().split()))
    ar = [-1] * n
    k = 0
    now = 0
    for i in range(n+1):
        if ar[now] == -1:
            ar[now] = k
            now = a[now]-1
            k += 1
        else:
            start = ar[now]
            startnode = now
            end = k
    if g <= start:
        ans = 0
        for i in range(n):
            if ar[i] == g:
                ans = i+1
    else:
        g -= start
        g %= (end-start)
        now = startnode
        for i in range(g):
            now = a[now]-1
        ans = now + 1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
cnt=0
s=1
M=[0]
B=[0]*(n+1)
while cnt<n:
    s=A[s-1]
    if B[s-1]==0:
        B[s-1]+=1
    else:
        imp=s-1
        break
    M.append(s-1)
    cnt+=1
x=M.index(imp)
y=len(M)-x

if k<=x:
    print(M[k]+1)
else:
    N=M[x:]
    print(N[(k-x)%y]+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
already=[0]*(n+1)
already[1]=1
history=[1]
tmp=1
now=0
jump=1
while jump:
  now+=1
  tmp=a[tmp]
  history.append(tmp)
  if now==k:
    ans=tmp
    break
  elif already[tmp]==1:
    jump=0
    past=history.index(tmp)
    loop=now-past
    ans=history[past+(k-now)%loop]
    break
  else:
    already[tmp]=1

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(a) - 1 for a in input().split()]
visited = [False] * N
if N >= K:
    ans = 0
    while K > 0:
        ans = A[ans]
        K -= 1
    print(ans + 1)
    exit()
cur = 0
visited[cur] = True
nxt = A[cur]
turn = 1
path = [[cur, turn]]
while True:
    if visited[nxt]:
        break
    cur = nxt
    visited[cur] = True
    nxt = A[cur]
    turn += 1
    path.append([cur, turn])
st = A[path[-1][0]]
st_turn = 1
for x in path:
    if x[0] == st:
        st_turn = x[1]
        break
fq = path[-1][1] - st_turn + 1
go = (K - (st_turn - 1)) % fq
ans = nxt
while go > 0:
    ans = A[ans]
    go -= 1
print(ans + 1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
chk = [0] * N
start = -1
ido = [0]
chk[0] = 1
index = 0
cnt = 0
while True:
    index = a[index] - 1
    if chk[index] == 0:
        chk[index] += 1
        cnt += 1
        ido.append(index)
    else:
        start = index
        break

if cnt >= K:
    print(ido[K] + 1)
    exit()
tmp = ido.index(start)
ido = ido[tmp:]
K -= tmp
print(ido[K % len(ido)] + 1)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))
d = dict()
c = 1
loop = False
k = 0
while(k<K):

    if not loop and str(c) in d:
        T = k-d[str(c)]
        #print ('K',k)
        a =  max((((K-k) // T)) - 1,0)
        #print(a)
        k += a*T
        #print ('K',k)
        loop = True
    d[str(c)] = k
    c = A[c]
    k+=1
print (c)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  l=LI()

  ans=[[] for _ in range(n)]
  basho=0
  f=inf
  for i in range(2*n+1):
    if f==inf and len(ans[basho])>1:
      f=basho
    ans[basho].append(i)
    basho=l[basho]-1

  # print(ans)
  # print(f)

  if k<(2*n+1):
    for i,x in enumerate(ans):
      if k in x:
        return i+1

  k-=ans[f][0]
  span=ans[f][2]-ans[f][1]
  # print(span)
  xx=k%span
  # print(k,span,xx)
  start=f
  while xx>0:
    start=l[start]-1
    xx-=1

  return start+1

# main()
print(main())

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 = [int(a) for a in input().split()]

    count = 0
    now = 1
    visited = [-1] * N
    visited[now - 1] = 0 # 町1 は0かいでいける
    while count < K:
        now = A[now - 1]
        count += 1
        if visited[now - 1] == -1:
            visited[now - 1] = count
        else:
            loop = count - visited[now - 1]
            rest = (K - visited[now - 1]) % loop
            #print("resr", rest)
            if rest == 0:
                break
            for i in range(len(visited)):
                if visited[i] == visited[now - 1] + rest:
                    now = i + 1
                    count = K # break
                    break
    #print(visited[0])
    print(now)




    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve(N, K, A):
    slow, fast = 1, 1
    is_first = True
    while is_first or slow != fast:
        is_first = False
        slow = A[slow - 1]
        fast = A[A[fast - 1] - 1]
    fast = 1
    steps_before_entering_cycle = []
    while slow != fast:
        steps_before_entering_cycle.append(fast)
        slow = A[slow - 1]
        fast = A[fast - 1]

    if K < len(steps_before_entering_cycle):
        return steps_before_entering_cycle[K]

    cycles = [slow]
    while A[slow - 1] != cycles[0]:
        cycles.append(A[slow - 1])
        slow = A[slow - 1]
    ret = cycles[(K - len(steps_before_entering_cycle)) % len(cycles)]
    return ret

if __name__ == '__main__':
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    print(solve(N, K, A))

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
que = deque([0])
while que:
    x = que.popleft()
    if check[x] != -1:
        break
    check[x] = cntr
    cntr += 1
    que.append(a[x]-1)
c = check[x]
if k < cntr:
    for i in range(n):
        if check[i] == k % cntr:
            print(i+1)
            quit()
    
check = [-1]*n
cntr = 0
que = deque([x])
while que:
    x = que.popleft()
    if check[x] != -1:
        break
    check[x] = cntr
    cntr += 1
    que.append(a[x]-1)

for i in range(n):
    if check[i] == (k-c) % cntr:
        print(i+1)

Submission status: Accepted

Solution code:
N, K = [int(v) for v in input().strip().split(" ")]
A = [int(v) for v in input().strip().split(" ")]

visited = set()
epoch = [0] * N
round = -1

# try
now = 0
epoch[0] = -1
visited.add(now)
for i in range(K):
    now = A[now] - 1
    if now not in visited:
        visited.add(now)
        epoch[now] = i
    else:
        round = i - epoch[now]
        break

K -= (i + 1)

K = K % round

for _ in range(K):
    now = A[now] - 1

print(now + 1)

Submission status: Accepted

Solution code:
import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

visited = [0] * N
order = [0]
visited[0] = 1

pos = 0
while True:
    next_town = A[pos]
    
    if visited[next_town] == 1:
        order.append(next_town)
        break
    visited[next_town] += 1
    pos = next_town
    order.append(pos)

idx = order.index(order[-1])
l_l = len(order) - idx - 1
l = len(order) -1 - l_l

if K < len(order):
    print(order[K] + 1)
    sys.exit()
    
K -= l
K %= l_l

print(order[l+K]+1)

Submission status: Accepted

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

count=[0]*(n+1)
cnt=0
i=1
while count[i]==0:
    count[i]=cnt
    if cnt==k:
        print(i)
        exit()
    cnt+=1
    i=a[i]

if cnt==k:
    print(i)
    exit()



loop=cnt-count[i]
#print("loop",loop)
goal=(k-cnt)%loop
#print(loop,goal)
if goal==0:
    print(i)
else:    
    print(count.index(count[i]+goal))

Submission status: Accepted

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

went={i:0 for i in range(1,n+1)}

now=1
cnt=1
for i in range(n+1):
    if went[now]>0:
        t=cnt-1
        s=went[now]
        break
    else:
        went[now]=cnt
        now=A[now-1]
        cnt+=1


if k <= t-1:
    val=k+1
else:
    val=((k+1-t)%(t-s+1)-1)%(t-s+1)+s
for ele in went:
    if went[ele]==val:
        print(ele)
        break

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
d={}
for i in range(0,len(l)):
    d[i+1]=l[i]
ans=1
s=set()
seq=[]
e=0
for i in range(0,k):
    ans=d[ans]
    if ans in s:
        seq.append(ans)
        break
    else:
        s.add(ans)
    seq.append(ans)
else:
    print(ans)
    e=1
if e==0:
    b = seq.index(seq[-1])
    rep = seq[b:-1]
    sl = len(seq) - seq.index(seq[-1]) - 1
    k = k - b - 1
    ans = seq[b]
    x = k % sl
    # print(x,sl)
    print(rep[x])