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:
from collections import deque
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.insert(0, 0)
    J = [-1] * (N + 1)
    T = []
    que = deque([1])
    count = 0
    l = 0
    while que:
        i = que.popleft()
        if J[i] != -1:
            l = J[i]
            break
        J[i] = count
        count += 1
        T.append(i)
        que.append(A[i])
    if K < l:
        return T[K]
    else:
        return T[(K-l)%(len(T)-l) + l]
print(main())

Submission status: Accepted

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

A={k+1:P[k] for k in range(N)}


U=list()
S=set()
x=1
k=0

while (x not in S) and (k<=K):
    U.append(x)
    S.add(x)
    
    x=A[x]
    k+=1

if k>K:
    print(U[-1])
else:
    d=U.index(x)
    V=U[d:]
    print(V[(K-d)%len(V)])

Submission status: Accepted

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

def solve():
    import sys

    N, K = list(map(int, sys.stdin.readline().split()))
    As = [-1] + list(map(int, sys.stdin.readline().split()))

    now = 1
    dic = {1:0}
    turns = [1]
    for i in range(1, N+1):
        nx = As[now]
        turns.append(nx)

        if not nx in dic:
            dic[nx] = i
            now = nx

            if i == K:
                print(now)
                return

            continue
        else:
            # サイクルが存在している
            cycle_num = i - dic[nx]  # 再度同じところに戻ってくるのにかかるテレポーテーションの回数
            k = (K-i)%cycle_num
            cycle_turns = turns[dic[nx]:i]
            print(cycle_turns[k])
            return


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

is_warped = [ False ] * n
is_warped[0] = True

x = 0
cycle = 0

while not is_warped[warping[x]]:
    x = warping[x]
    is_warped[x] = True

    cycle += 1

    if cycle == k:
        print(x + 1)
        exit(0)

x = warping[x]
cycle += 1

y = 0
cnt = 0

while warping[y] != x:
    y = warping[y]
    cnt += 1

y = warping[y]
cnt += 1

cycle -= cnt

mod = (k - cnt) % (cycle if cycle != 0 else cnt)

while mod:
    y = warping[y]

    mod -= 1

print(y + 1)

Submission status: Accepted

Solution code:
#N,K入力
N,K= map(int,input().split())
#街のテレポート先入力
A = [int(i)-1 for i in input().split()]
judge = [-1] * N
judge[0] = 0
#初期位置
a = 0
#移動回数
step = 1

while step != K +1:
    #移動する街を決める
    a = A[a]
    if judge[a] > -1:
        break
    #何回目の移動なのか加える
    judge[a] = step
    step = step + 1

if step == K +1:
    print(a+1)
    # プログラム終了
else:
    width = step - judge[a]
    s =(K - judge[a]) % width
    print(judge.index(judge[a]+s)+1)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
p = 1
p_hist = []
p_hist_set = set()
p_hist_index = [-1] * (N+1)
while p not in p_hist_set:
    p_hist_index[p] = len(p_hist)
    p_hist.append(p)
    p_hist_set.add(p)
    p = A[p-1]
end_loop = p_hist[-1]
end_loop_idx = p_hist_index[end_loop]
start_loop = A[end_loop - 1]
start_loop_idx = p_hist_index[start_loop]
if K < start_loop_idx:
    print(p_hist[K])
else:
    print(p_hist[(K-start_loop_idx)%(end_loop_idx-start_loop_idx+1)+start_loop_idx])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
idx = 1
S = [idx]
ed = set([idx])

for i in range(1, K+1):
    idx = A[idx-1]
    if idx in ed:
        start = S.index(idx)
        end = len(S)
        n = start + (K - start) % (end - start)
        print(S[n])
        break
    else:
        S.append(idx)
        ed.add(idx)
        continue
else:
    print(idx)

Submission status: Accepted

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

n = 0
visit = {0}
ls = [0]
for _ in range(K):
    n = A[n]
    if n not in visit:
        visit.add(n)
        ls += [n]
    else:
        loop_start = 0
        loop_length = 0
        flag = False
        m = 0
        for _ in range(N):
            if n == m:
                if flag:
                    break
                else:
                    flag = True
            if flag:
                loop_length += 1
            else:
                loop_start += 1
            m = A[m]

        print(ls[loop_start + ((K-loop_start) % loop_length)]+1)
        break
else:
    print(n+1)

Submission status: Accepted

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

city = a[1]
array = [1, a[1]]
checked = [False for _ in range(n+1)]
checked[1] = True
while True:
  tmp = a[city]
  city = tmp
  if checked[city]:
    break
  else:
    checked[city] = True
    array.append(tmp)
p = array.index(city)
q = len(array) - p
if k > p:
  print(array[p+(k-p)%q])
else:
  print(array[k])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

rem=k
nxt=1
visit=[]
visit_set=set([])
for i in range(k):
    visit.append(nxt)
    visit_set.add(nxt)
    nxt=a[nxt-1]
    # この判定をやめる
    if nxt in visit_set:
        break
    rem-=1

if rem==0:
    print(nxt)
else:
#    print('-'*60)
#    print('nxt=', nxt)
#    print('rem=', rem)
#    print('visit=', visit)
    
    loops=visit[visit.index(nxt):]
    print(loops[(rem-1)%len(loops)])    
    
#    print('-'*60)
#    print('loops=', loops)

Submission status: Accepted

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

chk = [0]*(N+1)
town = 1
rt = []
roop = 0

while True:
    if chk[town] == 1:
        break
    rt.append(town)
    chk[town] = 1
    town = A[town-1]

if K <= rt.index(town):
    print(rt[K])
else:
    roop = (K-rt.index(town)) % (len(rt)-rt.index(town))
    print(rt[rt.index(town)+roop])

Submission status: Accepted

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

location = 1
k = 0
visit = {1:0}

while k < K:
    k += 1
    location = A[location - 1]
    #print(k, location)
    if location in visit:
        #print(k - visit[location])
        k += ((K - k) // (k - visit[location])) * (k - visit[location])
        #print(k)
    else:
        visit[location] = k

print(location)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[int(x)-1 for x in input().split()]
b=[0]*n
b[0]=1
p=0
for c in range(k):
    p=a[p]
    if b[p]==1:
        break
    b[p]=1
if c==k-1:
    print(p+1)
else:
    q=p
    for d in range(n):
        q=a[q]
        if p==q:
            break
    m=(k-c-1)%(d+1)
    for e in range(m):
        p=a[p]
    print(p+1)

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())
A = list(map(int, input().split()))

seen = {1: 0}
a = 1

for i in range(1, n+1):
  if seen.setdefault(a:=A[a-1], i) != i:
    break

p = seen[a]         # cycle offset
q = i - seen[a]     # cycle length

assert q > 0
# print(f'{p = }, {q = }, {i = }, {seen = }')

if k >= p+q:
  k = (k - p) % q + p

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

print(a)

Submission status: Accepted

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

seen = {1: 0}
a = 1

for i in range(1, n+1):
  if seen.setdefault(a:=A[a-1], i) != i:
    break

p = seen[a]
q = i - seen[a]

if k >= p+q:
  k = (k - p) % q + p

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

print(a)

Submission status: Accepted

Solution code:
def solve(string):
    n, k, *a = map(int, string.split())
    a, t, p = [_a - 1 for _a in a], [0] * n, 0
    for i, _ in enumerate(a, 1):
        t[a[p]] = i
        p = a[p]
        if i == k:
            return str(p + 1)
    k = (k - t[a[p]] + 1) % (t[p] - t[a[p]] + 1)
    for _ in range(k):
        p = a[p]
    return str(p + 1)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
            
import sys
stdin=sys.stdin

ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))

N,K=nm()
A=nl()

city_l=[0]
city_l.append(1)
city_c=[0]*(N+1)
city_c[1]+=1
n_city=A[0]
flag=True
r_start=-1
r_end=-1
while(flag):
    city_c[n_city]+=1
    city_l.append(n_city)
    if(city_c[n_city]>1):
        r_start=city_l.index(n_city)
        r_end=len(city_l)-1
        city_l.append(A[n_city-1])
        flag=False
    n_city=A[n_city-1]

if(K<=r_end):
    print(A[city_l[K]-1])


else:
    K2=K-r_end+1
    K2=K2%(r_end-r_start)
    if(K2==0):
       print(city_l[r_end])
    else:
       print(city_l[r_start+K2])

Submission status: Accepted

Solution code:
def solve(string):
    n, k, *a = map(int, string.split())
    a, t = [_a - 1 for _a in a], [0] * n
    p = c = 0
    while not t[a[p]]:
        c += 1
        t[a[p]] = c
        p = a[p]
        if c == k:
            return str(p + 1)
    k = (k - t[a[p]] + 1) % (t[p] - t[a[p]] + 1)
    for _ in (range(k)):
        p = a[p]
    return str(p + 1)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys,pprint,readline

av = {}
passed = set()

(N,K) = [int(x) for x in input().split(" ")]

arrivalary = list(map(int,input().split(" ")))

'''
N =  200000
K = 12345678901234567
arrivalary = []
for i in range(1,N):
    arrivalary.append(i+1)
arrivalary.append(1)
'''

i = 0
loopflg = 0
pos = 1
nextpos = 0
loopstartpos = 0
loopstartnum = 0
loopcount = 0
while i < K:
    passed.add(pos)
    nextpos = arrivalary[pos-1]
    #print(i,pos,nextpos,loopflg,loopstartnum,loopstartpos,loopcount,file=sys.stderr)
    if loopflg == 0 and nextpos in passed:
        loopflg = 1
        loopstartpos = nextpos
        loopstartnum = i
        loopcount = 1
    elif loopflg == 1 and nextpos == loopstartpos:
        left = (K-loopstartnum) % loopcount
        #print("left=",left,file=sys.stderr)
        i = K-left
        if i == K:
            break
    elif loopflg == 1:
        loopcount += 1
    pos = nextpos
    i += 1

print(pos)

Submission status: Accepted

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

p = 1
points = [p]
visited = set([p])

for _ in range(N):
    p = A[p]
    if p in visited:
        break
    points.append(p)
    visited.add(p)

idx = points.index(p)

if idx > K:
    print(points[K])
    exit()

cycle = points[idx:]

print(cycle[(K - idx) % len(cycle)])

Submission status: Accepted

Solution code:
N,K = list(map(int, input().split()))
A = list(map(int, input().split()))
firstT = [-1] * N
firstT[0] = 0
now = 0
secondT, secondi = -1, -1
for i in range(1,N*2):
  now = A[now] - 1
  ## loopする前にKに到着した時
  if i == K:
    print(now+1)
    exit(0)
  if firstT[now] == -1:
    firstT[now] = i
  else:
    secondT = i
    secondi = now
    break

K = K - firstT[secondi]
K = K % (secondT - firstT[secondi])

#print(firstT)
#print(secondT, secondi)

now = secondi
for i in range(0,N):
  if i == K:
    print(now+1)
    exit(0)
  now = A[now] - 1

Submission status: Accepted

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

visited = set([1])
loop = [1]
now = 1

for _ in range(N):
    now = A[now]
    if now in visited:
        break
    else:
        loop.append(now)
        visited.add(now)

x = loop.index(now)

if K < x:
    print(loop[K])
else:
    K -= x
    loop = loop[x:]
    K %= len(loop)
    print(loop[K])

Submission status: Accepted

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

visited = [0]
visited_flg = [0 for _ in range(N)]
visited_flg[0] = 1
now_city = 0

next_city = A[0]
# visited.append(A[0])

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


while True:
    next_city = A[now_city] 
    if visited_flg[next_city]:
        break
    
    now_city = next_city
    visited.append(now_city)
    visited_flg[now_city] = 1
    

loop_start = next_city
loop_city =  visited[visited.index(loop_start):]
k =  (K- len(visited)) % len(loop_city)
print(loop_city[k]+1)

Submission status: Accepted

Solution code:
# Problem D - Teleporter

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

# initialization
visit_list = [0] * N
pos = a_list[0]
visit_list[pos-1] = 1
visit_count = 1
remain = K - 1
is_ok = True
ans = 0

# count
while remain>0 and is_ok:
    pos = a_list[pos-1]
    remain -= 1
    visit_count += 1
    if pos==1 or not visit_list[pos-1]==0:
        tmp_1 = visit_count - visit_list[pos-1]
        tmp_2 = remain % tmp_1
        for t in range(tmp_2):
            pos = a_list[pos-1]
        is_ok = False
        break
    else:
        if not pos==1 and visit_list[pos-1]==0:
            visit_list[pos-1] = visit_count

# output
print(pos)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
town=[0]*n
town[0]+=1
next=a[0]
for i in range(n):
  if town[next-1]==0:
    town[next-1]+=1
    next=a[next-1]
  else:
    break
re=next
next=a[re-1]
t2=0
for i in range(n):
  t2+=1
  if a[next-1]==re:
    t2+=1
    break
  else:
    next=a[next-1]
t1=0
next=a[0]
for i in range(n):
  t1+=1
  if a[next-1]==re:
    t1+=1
    break
  else:
    next=a[next-1]
if k<=t1:
  next=a[0]
  for i in range(k-1):
    next=a[next-1]
  print(next)
else:
  k-=t1
  k%=t2
  next=re
  for i in range(k):
    next=a[next-1]
  print(next)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    warp_idx = [-1] * (len(A) + 1)
    ans_list = []

    c = 1
    i = 0
    while warp_idx[c] == -1:
        warp_idx[c] = i
        ans_list.append(c)
        c = A[c - 1]
        i += 1
    start = warp_idx[c]
    loop = i - start
    if K <= start:
        print(ans_list[K])
    else:
        step = K - start
        step %= loop
        print(ans_list[start+step])


if __name__ == '__main__':
    main()

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:
import math

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

    state = 1
    chklist = [0] * (N + 1)
    chklist_flag = [False] * (N + 1)
 
    chkmod = 0
    chkrem = K

    chklist_flag[0] = True

    for i in range(1, K + 1):
        state = A[state - 1]
        if chklist_flag[state - 1]:
            chkmod = (K - chklist[state - 1]) % (i - chklist[state - 1]) 
            chkrem = chklist[state - 1]
            break
        chklist[state - 1] = i 
        chklist_flag[state - 1] = True
    
    state = 1

    for i in range(chkrem + chkmod):
        state = A[state - 1]
    
    print(state)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
if __name__ == '__main__':

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

    root = [] # 訪れた頂点をメモ
    already = [-1] * (n+1) # rootのindexのメモ　と　すでに訪れたか

    c = 1# 周期
    l = 0# 例外部分のながさ

    v = 1#頂点は1 ここから遷移
    while(already[v] == -1): # すでに書いてあれば訪れている。かつ周期の起点となる場所
        already[v] = len(root) #訪れたら何回目かを記述
        root.append(v)
        v = a[v-1]

    c = len(root) - already[v]
    l = already[v]

    if k < l:#例外部分のながさ
        ans = root[k]
    else:# 周期にいるなら
        k -= l
        ans = root[k%c+l]

    print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':

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

    root = [] # 訪れた頂点をメモ
    already = [-1] * (n+1) # rootのindexのメモ　と　すでに訪れたか

    c = 1# 周期
    l = 0# 例外部分のながさ
    """
    周期は　書き換えようとした時の　書き換えたかった数 - すでに書いてある数
    """

    v = 1#頂点は1 ここから遷移
    while(already[v] == -1): # すでに書いてあれば訪れている。かつ周期の起点となる場所
        already[v] = len(root) #訪れたら何回目かを記述
        root.append(v)
        v = a[v-1]

    c = len(root) - already[v]
    l = already[v]

    if k < l:#例外部分のながさ
        ans = root[k]
    else:# 周期にいるなら
        k -= l
        ans = root[k%c+l]

    print(ans)

Submission status: Accepted

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

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

t_sort = sorted(t)
for i in range(n):
    if t_sort[i] == t_sort[i + 1]:
        b = t_sort[i]
        break

count = 0
for i in range(n):
    if t[i] == b:
        if count == 0:
            count += 1
            s_first = i
        else:
            s_second = i
            break
s = s_second - s_first

for i in range(n - s + 1):
    if t[i] == t[i + s]:
        break

if k < i:
    print(t[k])
else:
    print(t[(k - i) % s + i])

Submission status: Accepted

Solution code:
import math

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

fk = k
crnt = 1
st = set()
wl = []
key = crnt
cy = 0
mg = 0

for i in range(n):
    if crnt in st:
        key = crnt
        cy = i - wl.index(crnt)
        mg = wl.index(crnt)
        break
    st.add(crnt)
    wl.append(crnt)
    crnt = li[crnt - 1]

k -= mg
if cy != 0:
    k %= cy
crnt = key
if n > fk:
    k = fk
    crnt = 1
for i in range(k):
    crnt = li[crnt - 1]

print(crnt)

Submission status: Accepted

Solution code:
n,k = (int(x) for x in input().split())
a = tuple([int(x) for x in input().split()])
 
c = [0] + [-1]*(n)
l = [1]
now = 1
dupl = -1

for i in range(k):
  now = a[now - 1]
  c[now - 1] += 1
   
  if c[now - 1] == 1:
    dupl = now
    break
  else:
    l.append(now)
    
if dupl == -1:
  print(now)
  exit()
       
notloop = l.index(dupl)
length = len(l)-notloop
print(l[(k-notloop)%length+notloop])

Submission status: Accepted

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

loop_li = []
loop_set = set([])
a = 1 

while a not in loop_set:
    loop_li.append(a)
    loop_set.add(a)
    a = a_li[a-1]

length = len(loop_li)
if k<length:
    print(loop_li[k])
else:
    bp = a_li[loop_li[-1]-1] # back point
    bp_idx = loop_li.index(bp)
    t = length - bp_idx
    amari = (k-bp_idx)%t
    print(loop_li[bp_idx+amari])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = input().split()
b = [0]*n
d = {}
ind = 1
num = 0
loop = 1
sup =0

while num != k:
  if b[ind-1] == 0:
    b[ind-1] = -1
    d[ind] = num
    num += 1
    ind = int(a[ind-1])
  else:
    loop = num-d[ind]
    sup = d[ind]
    break

if k-sup >=0:
  for i in range((k-sup)%loop):
    ind = int(a[ind-1])

print(ind)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
tel = list(map(int, input().split()))
log = [1]
record = [0] * n
while(True):
    log.append(tel[log[-1] - 1])
    if(record[log[-1] - 1] == 1):
        break
    record[log[-1] - 1] += 1
for i in range(len(log) - 1):
    if(log[i] == log[-1]):
        star = i
        mod = len(log) - star - 1
        break
if(k < len(log)):
    print(log[k])
else:
    print(log[(k - star) % mod + star])

Submission status: Accepted

Solution code:
n,m = map(int,input().split(" "))
ar = [int(i) - 1 for i in input().split(" ")]
if n >= m:
    a = 0
    for i in range(m):
        a = ar[a] 
    print(a + 1)
    exit()
a = 0
br = [-1] * n
br[0] = 0
for i in range(1,n):
    a = ar[a]
    if br[a] != -1:
        break
    br[a] = i
b = i - br[a]
m -= i
m %= b
for i in range(m):
    a = ar[a]
print(a+1)

Submission status: Accepted

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

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

n = 1
visited = [1]
visitedbit = [0] * (N+1) 
visitedbit[1] = 1
k = 0
flag = True
while True:
    
    k += 1
    #A[n]はテレポート先
    if k == K:
        print(A[n])
        flag = False
        break
    if visitedbit[A[n]]  == 0:
        visited.append(A[n])
        visitedbit[A[n]] = 1
        n = A[n]
    else:
        hazime = visited.index(A[n])
        break

if flag == True:
    # print(visited)
    loop = visited[hazime:]
    # print(loop)
    # print(hazime)
    print(loop[ (K-hazime)%(len(loop)) ])

Submission status: Accepted

Solution code:
def main():

    N_machi, K_teleport = map(int, input().split())
    to_teleport = list(map(int, input().split()))

    visited_city = [1]
    order = [-1 for i in range(N_machi + 1)]
    order[1] = 0
    next_city = 1
    
    for i in range(N_machi):
        next_city = to_teleport[next_city - 1]
        tmp = order[next_city]
        
        if (tmp == -1):
            visited_city.append(next_city)
            order[next_city] = i + 1
        else:
            break
    
    first = order[next_city]
    len_loop = len(visited_city) - first
    
    if (K_teleport < first):
        ans = visited_city[K_teleport]
    else:
        mod = (K_teleport - first) % len_loop
        ans = visited_city[first + mod]
    
    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

if K <= N:
    p = 0
    for _ 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 main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    cal=0
    time=[0]*N
    town=[]
    roop=[]

    while time[cal]!=2:
        if time[cal]==0:
            town.append(cal)

        else :
            roop.append(cal)

        time[cal]+=1
        cal=A[cal]-1

    if len(town)>K:
        print(town[K]+1)
        return

    else :
        print(roop[(K-(len(town)-len(roop)))%len(roop)]+1)
        return
main()

Submission status: Accepted

Solution code:
(N, K), A = [[*map(int, line.split())] for line in open(0)]

kiseki = [0] * N
now = 0
for i in range(N):
    kiseki[i] = now
    now = A[now] - 1

p = kiseki.index(now)
ans = p + (K - p) % (N - p) if p < K else K
print(kiseki[ans] + 1)

Submission status: Accepted

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

pl = [0]
for i in range(2*n+1000):
    nxt = tel[pl[-1]]
    pl.append(nxt)

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

loop_end = n
loop_start = n-1
while pl[loop_start] != pl[loop_end]:
    loop_start -= 1

#pl[loop_start] == pl[loop_end]
period = loop_end - loop_start

k %= period

while k < n:
    k += period

print(pl[k]+1)

Submission status: Accepted

Solution code:
N,K=list(map(int,input().split()))
l=list(map(int,input().split()))
roop=[1]
s=set([1])
now=l[0]
while now not in s:
   roop.append(now)
   s.add(now)
   now=l[now-1]
start=roop.index(now)
if len(roop) <= K:
   K-=start
   K=K%(len(roop)-start)
   print(roop[start+K])
else:
   print(roop[K])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import math


def get_input() -> tuple:
    """
    標準入力の取得

    Returns:\n
        tuple: 標準入力
    """
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    return N, K, A


def main(N: int, K: int, A: list) -> None:
    """
    求解処理.

    Args:
        N (int): 町の数
        K (int): テレポーターの使用回数
        A (list): テレポーターの転送先
    """
    # タブリング表の作成
    to = [A]
    for i in range(math.ceil(math.log2(K))):
        to_i = to[i]
        to_next = []
        for j in range(N):
            to_next.append(to_i[to_i[j]-1])

        to.append(to_next)

    result = 1
    for i in range(math.ceil(math.log2(K))):
        if ((K >> i) & 1):
            result = to[i][result-1]

    print(result)


if __name__ == "__main__":
    N, K, A = get_input()
    main(N, K, A)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
town = 1
record = [1]
record2 = [0]*N
for i in range(N):
    town = A[town-1]
    if record2[town-1]==1:
        break
    record.append(town)
    record2[town-1] += 1
    
newrecord = record[record.index(town):]
roop = len(newrecord)
newK = K-(len(record)-roop)
if newK>=0:
    answer = newrecord[newK%roop]
else:
    answer = record[K]

print(answer)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
lis = list(map(int, input().split()))
rt = [-1]*n
cnt = 0
idx = 0
rt[idx] = cnt
while True:
    if cnt==k:
        print(idx+1)
        exit()
    idx = lis[idx] - 1
    cnt += 1
    if rt[idx] == -1:
        rt[idx]=cnt
    else:
        can_jump=(k-cnt)//(cnt-rt[idx])
        if can_jump:
            cnt+=can_jump*(cnt-rt[idx])

Submission status: Accepted

Solution code:
import numpy as np
n, k=map(int,input().split())

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

 
s = list()
ord = np.full(n+1, -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:
a, b = list(map(int, input().split()))
c = list(map(int, input().split()))
itta2 = set([])
mati = 1
i = 0
itta = []
while True:
    if mati in itta2:
        saisyo = mati
        break
    else:
        itta2.add(mati)
        itta.append(mati)
        mati = c[mati-1]
        i += 1
risuto2 = set([])
risuto = []

while True:
    if mati in risuto2:
        break
    else:
        risuto2.add(mati)
        risuto.append(mati)
        mati = c[mati-1]
if b <= i-1:
    print(itta[b])
else:
    print(risuto[(b-i) % len(risuto)])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
visited=[False]*(n+1)
visited[1]=True
l=[1]
i=a[0]

for x in range(n):
    if visited[i]:break
    visited[i]=True
    l.append(i)
    i=a[i-1]

d=-1
for x in range(n):
    if l[x]==i:
        d=x
        break

f=l[:d]
b=l[d:]

if len(f)==0:
    print(b[k%len(b)])
    exit()
 
if len(b)==0:
    print(f[k%len(f)])
    exit()

if k<=d:
    print(l[k])
    exit()
 
k-=len(f)
print(b[k%len(b)])

Submission status: Accepted

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


c = [0]*(N+1)
i = 1
cnt = 0
f = True

while cnt < K:
    if f and (c[A[i]] or A[i]==1):
        loop = cnt-c[A[i]]+1
        cnt += (K-cnt-1)//loop*loop
        f = False

    cnt += 1
    i = A[i]
    c[i] = cnt

print(i)

Submission status: Accepted

Solution code:
import sys
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
p = 1
B = [-1]*N
B[0] = 0
count = 1
while K >= count:
	p = A[p-1]
	if B[p-1] != -1:
		break
	B[p-1] = count
	count += 1
if K < count:
	print(p)
	sys.exit()
K -= count
K = K % (count-B[p-1])
for i in range(K):
	p = A[p-1]
print(p)

Submission status: Accepted

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

n=[-1]*(N+2)
n[1]=0
i=0 #カウンター
place_now=1 #いる場所

while True:
  
  i+=1 #何回飛んだか
  place_now=A[place_now-1] #飛んだ時の場所
  
  
  if n[place_now] != -1:
    a=n[place_now] #ループの開始点
    loop=i-a #ループする長さ
    break
  
  n[place_now]=i #その場所につくのに何回飛んだか
  
if a>=K:
  print(n.index(K))
elif a<K:
  k_remain=(K-a)%loop+a
  print(n.index(k_remain))

Submission status: Accepted

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

city = [0] * (2 * N + 3)
city[0] = 1
arriedCity = {1}
secondArrivedCity = set()

hantei = False
roopHazimari = 0
cnt = 0
for i in range(1, len(city)):
    if i == K:
        city[i] = A[city[i - 1] - 1]
        hantei = True
        break

    if A[city[i - 1] - 1] in arriedCity:
        if cnt == 0:
            roopHazimari = i
        if A[city[i - 1] - 1] in secondArrivedCity:
            city[i] = A[city[i - 1] - 1]
            break
        cnt += 1
        secondArrivedCity.add(A[city[i - 1] - 1])
        city[i] = A[city[i - 1] - 1]
    else:
        city[i] = A[city[i - 1] - 1]
        arriedCity.add(A[city[i - 1] - 1])
# print(city)
if hantei:
    print(city[K])
else:
    temp = (K - roopHazimari) % cnt
    print(city[roopHazimari + temp])

Submission status: Accepted

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

logk=k.bit_length()
to=[[0]*n for i in range(logk)]

for i in range(n):
  to[0][i]=a[i]

for i in range(logk-1):
  for j in range(n):
    to[i+1][j]=to[i][to[i][j]]

v=0
for i in range(logk,-1,-1):
  l=2**i
  if l<=k:
    v=to[i][v]
    k-=l

print(v+1)

Submission status: Accepted

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

visit = []
step = [-1] * (n + 1)
v = 1
while step[v] == -1:
    step[v] = len(visit)
    visit.append(v)
    v = a[v - 1]
cycle = len(visit) - step[v]
nonCycle = step[v]

if k < nonCycle:
    print(visit[k])
else:
    k -= nonCycle
    k %= cycle
    print(visit[nonCycle + k])

Submission status: Accepted

Solution code:
#そのまま処理すると時間超過するので、ループを探索する

N, K = map(int, input().split())
A = list(map(int, input().split()))
 
#町の数だけ-1のチェックを生成する

flag = [-1] * N

#１番目の町は必ず踏むので、０にする

flag[0] = 0

#今いる町の位置i、初期値はリスト番号0

i = 0

#移動回数の初期値

num = 0
 
while True:

#移動回数を加算する

    num += 1

#町を移動する、リスト上では-1する必要がある

    i = A[i] - 1

#-1でない場合は、一度到達しているのでループを終了する

    if flag[i] != -1:

#flag[i]には何手目で到達したかが入っているので、ループに突入するまでの処理数としてiniに登録する

        ini = flag[i]
        break

    flag[i] = num

#loopに必要な数を求める、まずはループに突入するまでの処理数iniを引く
 
loop = num - ini
 
#loopに突入するまでの処理数よりも、与えられた処理数が多いとき

if K > ini:

#loopに突入するまでにかかる数を引く

    K -= ini

#ループに入るスタート位置＋ループ後の余の位置＋１
    
    t = flag.index(ini + K % loop) + 1

    print(t)

#それ以外の時、先に-1しているので+1して補正する

else:
    t = flag.index(K) + 1
    print(t)