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()))# 0index
visi = [-1 for i in range(N)]# 訪れたタイミングを記録(-1: 訪れてない)
L = [1] # 今いる町を追加(町番号:1index)
visi[0] = 0
way = A[0] #次に向かう町の番号を取得
#l = []
count = 1

while visi[way-1] == -1: #すでに訪れた町が出てくるまでループ
    visi[way-1] = count
    count += 1
    L.append(way)
    way = A[way-1]

l = count - visi[way-1]
l_pre = visi[way-1]
loop_L = L[l_pre:]



if K > l_pre:
    index = (K- l_pre)% l
    ans = loop_L[index]
else:
    ans = L[K]
print(ans)

Submission status: Accepted

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

journey = [1]

for i in range(2*n + 100):
    nxt = a[journey[-1]]
    journey.append(nxt)
    
if k < n + 1:
    print(journey[k])
    exit()

loop_end = n

loop_start = n-1

while(journey[loop_start] != journey[loop_end]):
    loop_start -= 1

period = loop_end - loop_start

k %= period
while k<= n:
    k += period

print(journey[k])

Submission status: Accepted

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

    doubling = [[0]*(N+1) for _ in range(60)]
    for i,a in enumerate(A):
        doubling[0][i+1] = a
    for i in range(1,60):
        for j in range(1,N+1):
            doubling[i][j] = doubling[i-1][doubling[i-1][j]]
            
    t = 1
    for i in range(59,-1,-1):
        if (K>>i)&1:
            t = doubling[i][t]
    print(t)
main()

Submission status: Accepted

Solution code:
def f(x):
    return int(x)-1
n, k = map(int, input().split())
a = list(map(f, input().split()))
town = 0
i=0
l = [-1] * n
while True:
    if l[town] != -1:
        j = l[town]
        break
    i += 1
    l[town] += i
    town = a[town]
    # print(town,l)
# print(town)
if k >= i:
    k = (k - j) % (i - j) + j
print(l.index(k)+1)

Submission status: Accepted

Solution code:
nk = input(' ')
n = int(nk.split()[0])
k = int(nk.split()[1])
alist = list(map(int,input('').split()))

loop_start=0
loop_end=0
root = [1]
next_val=1
flag=[True]*n
flag[0]=False # 踏んだかどうか判定機
a=1
for i in range(k):
    a = alist[a-1]
    if flag[a-1]: # 踏んでたらそこでブレイク
        root.append(a)
        flag[a-1]=False # 踏んだらFalseに
    else:
        break

#print("{} {}->{}".format(root,loop_start,loop_end))

loop_start=root.index(a)
loop_end=len(root)
step=(k-loop_start)%(len(root)-loop_start)
#print("step:({}-{})%({} - {})={}".format(k,loop_start,loop_end,loop_start,step))
#print("root[{}+{}]={}".format(loop_start,step,root[loop_start+step]))
print(root[loop_start+step])

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[2**61]*-~n
s=1
while k:k-=1;s=a[s-1];k%=d[s]-k;d[s]=k
print(s)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
d={}
s=1
while k:k-=1;s=a[s-1];k%=d.get(s,2**61)-k;d[s]=k
print(s)

Submission status: Accepted

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

num = 1
li = [1]
flag = [True]*n
flag[0] = False

for i in range(k):
    num = a[num-1]
    if flag[num-1]:
        li.append(num)
        flag[num-1] = False
    else:
        break

d = li.index(num)
ans = (k-d)%(len(li)-d)+d

print(li[ans])

Submission status: Accepted

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

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

s = []
od = [-1]*(n+1)
c=1
l=0

v=1

while od[v] == -1:
  od[v] = len(s)
  s.append(v)
  v = a[v-1]

c=len(s)-od[v]
l=od[v]

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

Submission status: Accepted

Solution code:
def f(x):
    return int(x)-1
n,k=map(int,input().split())
A=list(map(f,input().split()))
B=[-1]*n
a=0
i=0
while True:
    if B[a]!=-1:
        j=B[a]
        break
    i+=1
    B[a]+=i
    a=A[a]
if k<i:
    print(B.index(k)+1)
else:
    k=(k-j)%(i-j)+j
    print(B.index(k)+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import log2

class Doubling:
    def __init__(self, lst, max_step):
        self.lst = lst
        self.max_step = max_step
        self.k = int(log2(max_step * 2 - 1)) + 1
        # print(self.k)
        self.D = self.create()

    def create(self):
        len_ = len(self.lst)
        D = [[-1] * len_ for _ in range(self.k)]
        D[0] = self.lst
        d = 2
        for i in range(1, self.k):
            for j in range(len_):
                D[i][j] = D[i - 1][D[i - 1][j]]
            d *= 2
        # print(D)
        return D

    def step(self, start, step):
        v = start
        for i in range(self.k, -1, -1):
            l = 1 << i
            if l <= step:
                v = self.D[i][v]
                # print(i, l)
                step -= l
        return v

def solve():
    n, k = MI()

    A = LI1()
    d = Doubling(A, k)

    v = d.step(0, k)
    print(v+1)







if __name__ == '__main__':

    solve()

Submission status: Accepted

Solution code:
def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    visited = [0 for i in range(n)]
    visit = [0]
    visited[0]=1
    s = 0
    while True:
        s = a[s]-1
        if visited[s]==1:
            x = visit[0:visit.index(s)]
            y = visit[visit.index(s):]
            break
        visit.append(s)
        visited[s]=1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

class doubling:
    # A: 各頂点の親の番号 (0-indexed)
    # 頂点SのK個上の親の番号を返す．

    # 構築
    def __init__(self, A, K):
        self.M = 0
        temp = K
        N = len(A)
        self.Kb = []
        # 2^(M-1)乗まで計算
        while temp>0:
            self.M += 1
            self.Kb.append(temp&1)
            temp>>=1

        # 初期化
        self.nexts = [[-1]*N for _ in range(self.M)]
        for i in range(N):
            self.nexts[0][i] = A[i]

        # ダブリング計算
        for t in range(1,self.M):
            for i in range(N):
                self.nexts[t][i] = self.nexts[t-1][self.nexts[t-1][i]]

    def query(self, S, K):
        res = S
        for i in reversed(range(self.M)):
            if self.Kb[i]:
                res = self.nexts[i][res]
        return res

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

Double = doubling(A, K)
ans = Double.query(0,K)+1
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
teleporters = list(map(int, input().split()))
n = 0
present = 0
praces = [-1 for i in range(N)]
praces[0] = 0
for i in range(K):
  present = teleporters[present] - 1
  n += 1
  if praces[present] == -1:
    praces[present] = n
  else:
    before = praces[present]
    loop = n - before
    remainder = (K - before) % loop
    present = praces.index(before + remainder)
    break
print(present + 1)

Submission status: Accepted

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

M = 0
temp = K
while temp>0:
    M += 1
    temp>>=1

nexts = [[-1]*N for _ in range(M)]
for i in range(N):
    nexts[0][i] = A[i]-1

for t in range(1,M):
    for i in range(N):
        nexts[t][i] = nexts[t-1][nexts[t-1][i]]

Kb = [0]*M
temp = K
for i in range(M):
    Kb[i] = temp&1
    temp >>= 1

ans = 0
for i in reversed(range(M)):
    if Kb[i]:
        ans = nexts[i][ans]
print(ans+1)

Submission status: Accepted

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

def main():
    N,K = map(int, readline().split())
    A = [int(i) - 1 for i in readline().split()]

    p = 0
    route = []
    seen = set()
    while True:
        route.append(p)
        seen.add(p)
        p = A[p]
        if p in seen:
            break
    
    loop_start = route.index(p)
    loop_len = len(route) - loop_start

    if K <= loop_start:
        ans = route[K] + 1
    else:
        r = (K - loop_start) % loop_len
        ans = route[loop_start + r] + 1
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A=  list(map(int,input().split()))
now = 0
if K <= N:
    for i in range(K):
        now = A[now]-1
    print(now+1)
else:
    alr = [0]
    alr2 = [False for i in range(N)]
    alr2[0] = True
    now = 0
    for i in range(K):
        now = A[now]-1
        if alr2[now] == False:
            alr.append(now)
            alr2[now] = True
        else:
            loop = alr[alr.index(now):]
            rem = K - i - 1
            break
    ans = loop[rem%len(loop)]+1
    print(ans)

Submission status: Accepted

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


def main():
    N, K = map(int, input().split())
    A = list(map(int, 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])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

shown = [0]*n
shown[0] = 1
cur = 0
cur_idx = 1
len_to_loop = 0
loop_start = 0
while cur_idx<=n:
  nxt = A[cur]
  #print(shown, cur_idx, cur, nxt)
  if shown[nxt]>0:
    cur_idx += 1
    loop_start = nxt
    len_loop = cur_idx - shown[nxt]
    if cur==nxt:
      len_loop += 1
    len_to_loop = shown[nxt]-1
    break
  else:
    cur_idx += 1
    shown[nxt] = cur_idx
    cur = nxt
    

rest = k-len_to_loop
rest = rest%len_loop

if k<=n:
  cur = 0
  for i in range(k):
    nxt = A[cur]
    cur = nxt
else:  
  cur = loop_start
  for i in range(rest):
    nxt = A[cur]
    cur = nxt
  
print(cur+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
order = [-1] * (n+1)
v = [0] * (n+1)
v[0] = 1
order[v[0]] = 0
# iは順番
for i in range(1, n+1):
    v[i] = A[v[i-1] - 1]
    if order[v[i]] != -1:
        old_i = order[v[i]]
        c = i - old_i
        break
    order[v[i]] = i
if k < old_i:
    print(v[k])
else:
    print(v[(k - old_i)%c + old_i])

Submission status: Accepted

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

s = [] # 訪れた頂点をメモ
ord = [-1]*(n+1) # 訪れた順番をメモ

c = 1 # 周期
l = 0 # 例外部分
v = 1 # 現在地

while ord[v] == -1:
    ord[v] = len(s)
    s.append(v)
    v = a[v-1] # ワープさせる

c = len(s) - ord[v]
l = ord[v]

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
p=1
if k<=n:
    for i in range(k):
        p=A[p-1]
    print(p)
else:
    D=[0]+[-1]*(n-1)
    for i in range(n):
        p=A[p-1]
        if D[p-1]==-1:
            D[p-1]=i+1
        else:
            l=D[p-1]
            r=i+1-D[p-1]
            m=(k-l)%r+l
            break
    p=1
    for i in range(m):
        p=A[p-1]
    print(p)

Submission status: Accepted

Solution code:
def LIST():return list(map(int,input().split()))
def MAP():return map(int,input().split())

n,k=MAP()
a=LIST()
a=[0]+a
s=[0]
loca=1
begin=end=0
temp=[-1]*(2*10**5+1)
for i in range(1,n+1):
    s.append(a[loca])
    loca=a[loca]
    if k==i:
        print(s[i])
        exit()
    if temp[loca]==-1:
        temp[loca]=i
    else:
        begin=temp[loca]
        end=i-1
        break

if begin==0:print(s[(k-1)%n+1])
else:
    k=k-(begin-1)
    s=[0]+s[begin:]
    print(s[(k-1)%(end-begin+1)+1])

Submission status: Accepted

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

A = list(map(int, input().split()))
d = {}

d[1] = A[0]

idx = 1
start = 0
count = 0
while True:
  count += 1
  if K == count:
    print(A[idx-1])
    exit()
  d[idx] = A[idx-1]
  idx = A[idx-1]
  if idx in d:
    start = idx
    break


e = {}
l = []
while True:
  e[start] = A[start-1]
  l.append(e[start])
  start = A[start-1]
  if start in e:
    break


amari = ((K-count-len(l)) % len(l))
if amari != 0:
  print(l[amari-1])
else:
  print(l[-1])

Submission status: Accepted

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

visited = [0] * n
i = 0
now = 0
while k > i:
    if visited[now] == 0:
        i += 1
        visited[now] = i
        now = lst[now] 
    else:
        break

lp = (i + 1) - visited[now]
st = i - lp
k_bk = k - st
k_bk = k_bk // lp
lft = k - (k_bk * lp + st)

if lft == 0:
    print(now+1)
else:
    for _ in range(lft):
        now = lst[now]
    print(now+1)

Submission status: Accepted

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

# 訪問順
B = [1]

# 訪問済み
C = [False] * (n + 1)
C[1] = True


while True:
    B.append(A[B[-1]])
    if C[B[-1]]:
        break
    C[B[-1]] = True

s = B.index(B[-1])

if k < s:
    print(B[k])
    exit()

B = B[B.index(B[-1]):-1]
print(B[(k - s) % len(B)])

Submission status: Accepted

Solution code:
import sys

n, k, *aaa = map(int, sys.stdin.buffer.read().split())
aaa = [0] + aaa
p = 1
while k:
    if k & 1:
        p = aaa[p]
    aaa = [aaa[a] for a in aaa]
    k >>= 1
print(p)

Submission status: Accepted

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

l = [A[0]]
s = {A[0]}
a = A[0] - 1
for _ in range(K):
    if A[a] not in s:
        l.append(A[a])
        s.add(A[a])
        a = A[a] - 1
    else:
        a = A[a]
        break
n = len(l)
b = 0
for i in range(n):
    if l[i] == a:
        del l[0:i]
        b = i
        break
T = len(l)
S = (K - b) % T
ans = l[S - 1]

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
visited={}
for i in range(1,n+1):
    visited[i]=-1
l=[1]
visited[1]=0
i=1
while True:
    if visited[a[l[i-1]-1]]==0:
        roop_start=l.index(a[l[i-1]-1])
        break
    visited[a[l[i-1]-1]]=0
    l.append(a[l[i-1]-1])
    i+=1
roop_dif=i-roop_start

if k<roop_start:
    print(l[k])
else:
    k-=roop_start
    k%=roop_dif
    print(l[roop_start+k])

Submission status: Accepted

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

now = 0
route = []
seen = set()
while True:
    if now in seen:
        break
    route.append(now)
    seen.add(now)
    now = A[now]

loop_start = route.index(now)
loop_size = len(route) - loop_start

n_for_loop = min(K, loop_start)
n_in_loop = (K - n_for_loop) % loop_size

print(route[n_for_loop + n_in_loop] + 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    D = 1
    LOG = {}
    PATH = []
    for i in range(N):
        PATH.append(D)
        LOG.setdefault(D,i)

        if LOG[D] == i:
            D = A[D-1]
            # print(PATH,LOG, i)
            continue
        else:
            # print("break",D, i)
            break

    # if i-LOG[D] < K:
    if LOG[D] < K:
        K = (K-i)%(i-LOG[D])
        LAST = PATH[LOG[D]+K]
    else:
        LAST = PATH[K]
    print(LAST)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, K, *A = map(int, open(0).read().split())
    log_k = 0
    k = K
    while k > 0:
        k >>= 1
        log_k += 1
    # print(log_k)

    # level 1
    work = [A[i] for i in range(N)]

    ans = 1
    for k in range(log_k):
        if (K >> k) & 1 == 1:
            ans = work[ans - 1]
        work = [work[work[i] - 1] for i in range(N)]
    print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = 1
c = 0
d = {}
t = []
# 順番をdictで持つ
while not s in d.keys():
    d[s] = c
    t.append(s)
    c += 1
    s = a[s-1]
l = c - d[s]
m = len(d.keys()) - l
if m >= k:
    print(t[k])
else:
    print(t[(k - m) % l + m])

Submission status: Accepted

Solution code:
def main():
    N, K, *A = map(int, open(0).read().split())
    visited = [-1]*N
    pos = A[0]
    visited[0] = 0
    visited[pos - 1] = 1
    step = 2
    order = 0
    start = 0
    step_to_start = 0
    while True:
        pos = A[pos - 1]
        if visited[pos - 1] == -1:
            visited[pos - 1] = step
        else:
            step_to_start = visited[pos - 1]
            order = step - step_to_start
            start = pos
            break
        step += 1
    # print(start, step_to_start, order)

    if K <= step_to_start:
        ans = 1
        for i in range(K):
            ans = A[ans - 1]
        print(ans)
        return
    remain = (K - step_to_start) % order
    ans = start
    for i in range(remain):
        ans = A[ans - 1]
    print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import math

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

n,k = NextInts()
da = NextIntList()
for i in range(n):
    da[i]-=1

dp = [[0 for i in range(n)] for i in range(61)]

dp[0] = da

for i in range(60):
    for j in range(n):
        dp[i+1][j] = dp[i][dp[i][j]]

ans = 0
for i in range(61):
    if k&1:
        ans = dp[i][ans]
    k >>= 1
print(ans+1)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, k = i_map()
    num_list = i_list()

    bin_k = bin(k)[2:]

    len_bin_k = len(bin_k)

    doubling = [[0] * n for i in range(len_bin_k)]

    for i in range(len_bin_k):
        for j in range(n):
            if i == 0:
                doubling[i][j] = num_list[j]
                continue
            doubling[i][j] = doubling[i-1][doubling[i-1][j]-1]

    current_town = 1
    for i, s in enumerate(bin_k):
        if s == '0':
            continue
        current_town = doubling[len_bin_k-i-1][current_town-1]

    print(current_town)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if K <= N:
    p=0
    for i in range(K):
        p = A[p]
        
    print(p+1)
    exit()

p=0
t=[-1]*N
t[0]=0

for i in range(1,N):
    p =A[p]
    if t[p]!=-1:
        break
    t[p]=i
    
d=i-t[p]
K-=i
K%=d


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

Submission status: Accepted

Solution code:
def mapint_inp():
    return map(int, input().split())

def intinp():
    return int(input())

n, k = mapint_inp()
a = list(mapint_inp())

s = []
order_of_teleport = [-1]*(n+1)
cycle = 1
l = 0
v = 1
while order_of_teleport[v] == -1:
    order_of_teleport[v] = len(s)
    s.append(v)
    v = a[v-1]
c = len(s) - order_of_teleport[v] # サイクルの長さ
l = order_of_teleport[v] # 例外部分の長さ

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.read

def dubbling(a:np.array, k:int, MAXk=10**12) -> np.array:
    bl = MAXk.bit_length()
    b = np.empty([bl,len(a)+1], dtype=np.int64)
    b[0] = np.append(a, -1)
    for i in range(1,bl):
        x = b[i-1]
        b[i] = x[x]
    X1 = b[np.array(list(format(k,'0'+str(bl)+'b')), dtype=np.int8).astype(np.bool)[::-1]]
    ret = np.append(np.arange(len(a)), -1)
    for i in X1:
        ret = ret[i]
    return ret

n, k = map(int, input().split())
a = np.array(read().split(), dtype=np.int64)
maxk = 10**18

ans = dubbling(a-1, k, MAXk=maxk)[0] + 1
print(ans)

Submission status: Accepted

Solution code:
import copy
N,K = list(map(int, input().split()))
 
A = list(map(int, input().split()))
 
count = [0]
Check = [0] * N
for i in range(K):
    count.append(A[count[-1]]-1)
#    print(count)
    if(Check[count[-1]-1] == 1):
        break
 
    Check[count[-1]-1] = 1
    i += 1
 
saisyo = count.index(count[-1]) + 1
#print(count,saisyo)
 
if(saisyo == len(count)):
    saisyo = 0
 
loop_kazu = len(count) - saisyo
 
if(K > loop_kazu):
    K_loop = K - saisyo
 
    ans_index = K_loop % loop_kazu
    ans = count[saisyo + ans_index] + 1
 
    print(ans)
 
else:
    print(count[K]+1)

Submission status: Accepted

Solution code:
from collections import deque

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

check = [-1] * N
q = deque([1])
now = A[0]
check[0] = 0

for i in range(K):
    if check[now - 1] != -1:
        break
    check[now - 1] = i + 1
    q.append(now)
    now = A[now - 1]

x = check[now - 1]

if x > K:
    ans = q[K]
else:
    r = list(q)[x:]
    ans = q[(K - x) % len(r) + x]

print(ans)

Submission status: Accepted

Solution code:
def intMap(): return map(int,input().split())
def intList(): return list(map(int, input().split()))

n,k = intMap()
a = intList()
for i in range(n): a[i] -= 1 # 0-base にしておく

moveUntilLoop = 0
loopStart = 0
loopSize = 0

def getLoopInfo(): # ループまでの手数、ループのスタート位置、ループのサイズを得る
    global moveUntilLoop
    global loopStart
    global loopSize
    visited = [0]*n # 訪れた事がある場合は最初に訪れるまでの手数
    moveTime = 0
    pos = 0 # 現在の位置
    
    #ループのスタート位置と、そこまでの手数
    while 1:
        if visited[pos]: break # 過去に訪れた事があれば検索中止
        visited[pos] = moveTime # visited[] に、ここまでの手数を入れる
        moveTime += 1
        pos = a[pos]
    loopStart = pos
    moveUntilLoop = visited[loopStart]

    #ループの長さ
    while 1:
        pos = a[pos]
        loopSize += 1
        if pos == loopStart: break

# k が n より小さい -> 10^5 以下の場合は、実際にやってみる
if k <= n:
    pos = 0
    for i in range(k): pos = a[pos]
    print(pos+1) # 0-base にしたので print 時に戻しておく
    exit()
    
# k > n の場合
getLoopInfo()

# k > n なので k > (loopStart + loopSize)
k -= moveUntilLoop
goal = k % loopSize
pos = loopStart
for _ in range(goal): pos = a[pos]

print(pos+1) # 0-base にしたので print 時に戻しておく

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
tele = list(map(int, input().split()))
	
city = 1
visited_cities = []
foo = [0]*n
while foo[city - 1] < 1 and k > 0:
	visited_cities.append(city)
	foo[city - 1] += 1
	city = tele[city - 1]
	k -= 1
	
if k == 0:
	print (city)
else:
	visited_cities = visited_cities[visited_cities.index(city):]	
	print (visited_cities[k % len(visited_cities)])

Submission status: Accepted

Solution code:
#167
#d
n,k = map(int, input().split())
ln = list(map(int, input().split()))# まちi にいるとき次に町ln[i-1]へいく

# n,k = 10*4,10**18
# ln = list(range(2,n+1))
# ln.append(1)

visit = [0]*n 
now= 1 # 街iにいる
before =[] # ループに入る前（1回めのループ含む）
roop =[] #　ループ内
while visit[now -1] != 2:
    if visit[now -1] ==  0:
        before.append(now)
    elif visit [now-1] == 1:
        roop.append(now)
    
    visit[now -1]+= 1
    now = ln[now-1]


if k < len(before):
    print(before[k])
else :
    print(roop[((k-len(before))%len(roop)) ])

Submission status: Accepted

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

#訪れた町
visited = [0]*n
visited[0]=1
root=[0]

next=a[0]-1
same=0
cnt=0
while cnt<k:
    if visited[next]==1:

        same=next

        root.append(next)

        index = root.index(same)

        break
    else:
        visited[next]=1
        root.append(next)

    next = a[next]-1
    cnt+=1

# print(visited)
# print(root)
# print(index)
if cnt==k:
    print(root[-1]+1)
    exit(0)

roops=len(root) - index -1 

if roops!=0:
    moves = index + ( (k-index)%roops )
else:
    moves= index

now=0

for i in range(moves):
    now=a[now]-1

print(now+1)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = 0
visit = [0] * N
move = []
roop = []
while visit[pos]!=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos] += 1
    pos = A[pos] - 1
if len(move)>K:
    print(move[K]+1)
else:
    print(roop[(K-(len(move)-len(roop)))%len(roop)]+1)

Submission status: Accepted

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

N, K=map(int, input().split())
A = list(map(int,input().split()))
now=0
rireki=[0]*N
isou=1
hazimete=0
for i in range(4*N):
    if rireki[now]==0:
        rireki[now]=1
        startnum=i
        start=now
    else:
        if hazimete==1:
            startnum=i
            start=now
        hazimte=1
        if rireki[now]==1:
            rireki[now]=2
        else:
            if rireki[now]==2:
                rireki[now]=3
                isou=i-startnum-1
                break
    #print("{}".format(now))
    now=A[now]-1

#print("{}".format(isou))
amari=(K-startnum-1)%isou

for i in range(amari):
    now=A[now]-1
#print("{}".format(amari))
if K>startnum:
    print("{}".format(now+1))
else:
    now=0
    for i in range(K):
        now=A[now]-1
    print("{}".format(now+1))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [1]+a
flg = [0] * (n + 1)
 
now = 0
i = 1
flg2 = 1
loop = 0
while (i < k+1):
    if (flg2 and flg[a[now]] != 0):
        flg2 = 0
        loop = i-flg[a[now]]
        i += ((k - i) // loop - 1) * loop
    now = a[now]
    flg[now] = i
    i += 1
print(a[now])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    A = list(map(lambda x: int(x)-1, input().split()))
    now = 0
    dict_ = {}
    stack = []
    for i in range(N):
        if now not in dict_:
            dict_[now] = A[now]
            stack.append(now)
            now = A[now]
        else:
            idx = stack.index(now)
            mod = i - idx
            break
    idx = idx + (K-idx) % mod
    idx = min(K, idx)
    print(stack[idx]+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

now = 0
route = []
seen = [False]*N
while True:
    route.append(now)
    seen[now] = True
    to = A[now] - 1
    if seen[to]:
        break
    else:
        now = to
loop_start = route.index(to)
loop_size = len(route) - loop_start

n_for_loop = min(K, loop_start)
K -= n_for_loop
n_in_loop = K%loop_size

print(route[n_for_loop + n_in_loop] + 1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split())) 
 
x=[0]*(n)
before = 0
now = 0
while x[now] == 0:
    x[now]=1+x[before]
    before=now
    now = a[now]-1
    
y=x[now]-x[0]
z=x[before]-y
if k>y:
    l=(k-y)%z+1
else :
    l=k-y+1
for i in range(n):
    if x[i] == l+y:
        print(1+i)
        break

Submission status: Accepted

Solution code:
def read_int():
    return int(input())

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

def read_lines(N):
    return [input() for i in range(N)]

def main():
    N, K = read_ints()
    towns = [int(t) -1  for t in input().split() ]
    #print(N, K , towns)

    loop = []
    loop_set = set()
    next_town = towns[0]
    while next_town not in loop_set:
        #print(f"next_t={next_town}")
        loop.append(next_town)
        loop_set.add(next_town)
        next_town = towns[next_town]

    i = loop.index(next_town)
    all_loop = loop
    pre_loop = loop[:i]
    loop = loop[i:]
    pre_length = len(pre_loop)
    loop_length = len(loop)

    """
    for k in range(1, 10):
        if k - 1  < len(all_loop):
            print(f"k={k}", all_loop[k-1] + 1)
        else:
            i = ((k -1 - len(pre_loop)) % loop_length)
            print(i, pre_loop, loop)
            print(f"k={k}", loop[i]+1)
    """

    #print(pre_loop, loop)
    if K - 1  < len(all_loop):
        print(all_loop[K-1] + 1)
    else:
        i = ((K -1 - pre_length) % loop_length)
        #print(i, pre_loop, loop)
        print(loop[i]+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #ここにコード
    #input
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    #output
    #ループしたらそのループの周期でKを割る。

    loop = {i:-1 for i in range(N)}
    loop[0] = 0
    position = 0

    for i in range(N+1):
        position = A[position] - 1
        if loop[position] != -1:
            ini = loop[position]
            cycle = i+1 - ini
            break
        else:
            loop[position] = i+1

    M = (K-ini) % cycle

    answer = 0
    root = min(K, M+ini)
    for j in range(root):
        answer = A[answer] -1

    answer += 1
    print(answer)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
a = [i - 1 for i in list(map(int, input().split()))]
logk = k.bit_length()
doubling = [[-1 for _ in range(n)] for _ in range(logk)]
for i in range(n):
    doubling[0][i] = a[i]
for i in range(1, logk):
    for j in range(n):
        doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]
index = 0
k_bin = list(map(int, [list(bin(k))[-i]
                       for i in range(1, logk + 1)]))
for i in range(logk):
    if k_bin[i]:
        index = doubling[i][index]
print(index + 1)