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()))
# リストを扱いやすいように変形
def subtraction(x):
    return x - 1
A = list(map(subtraction, A))

# 通ったことのある場所を持っておく
R = [0]*n
R[0] = 1
ROUTE = [0]
t = A[0]
while R[t] == 0:
    ROUTE.append(t)
    R[t] = 1
    t = A[t]

x = ROUTE.index(t) # ループのスタート地点
length = len(ROUTE) - x

if k < x:
    print(ROUTE[k]+1)
else:
    k = k - x
    s = k % length
    print(ROUTE[x + s]+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int,input().split()))
b = [0]*N
next_town = 1
for i in range(N+1):
    if b[next_town-1] != 0:
        start = next_town
        cycle = i - b[next_town-1]
#        print("start: "+str(start))
#        print("cycle: "+str(cycle))
        break
    b[next_town-1] = i
    next_town = A[next_town-1]
    
next_town = 1
if b[start-1] >= K:
    for i in range(K):
        next_town = A[next_town-1]
    print(next_town)
else:
    next_town = start
    for i in range((K-b[start-1])%cycle):
        next_town = A[next_town-1]
    print(next_town)

Submission status: Accepted

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

now = 0
if k <= n:
  for i in range(k):
    now = A[now]
  print(now+1)
  
else:
  V = [-1]*n
  V[0] = 0
  for i in range(1,n):
    now = A[now] 
    if V[now] >= 0:
      break
    V[now] = i 
      
  for j in range( (k-i)%(i-V[now])):
    now = A[now]
    
  print(now+1)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a = [int(i) - 1 for i in input().split()]
    ans = solve(n, k, a)
    print(ans)


def solve(n, k, a):
    #print(f'{n = } {k = }')
    #print(f'{a = }')
    mk = 60
    dp = [[i for i in a] for _ in range(mk)]
    for i in range(1, mk):
        for j in range(n):
            dp[i][j] = dp[i - 1][dp[i - 1][j]]

    #print(*dp, sep = '\n')

    pos = 0
    for b in range(mk):
        if k >> b & 1:
            pos = dp[b][pos]
    return pos + 1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
idx=1
idx_li=[]
ord_=[-1]*n
flag=False
for i in range(k):
    idx_li.append(idx)
    ord_[idx-1]=1
    idx=a[idx-1]
    if ord_[idx-1]==1:
        flag=True
        break
if flag:
    #non_loop=idx_li[:idx_li.index(idx)]
    loop = idx_li[idx_li.index(idx):]
    
    size=len(loop)
    print(loop[(k-(len(idx_li)-len(loop)))%size])
else:
    print(idx)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A_list = [0] + [int(e) for e in input().split()]

used_tele = 0
repeating_flag = False
moving_dict = dict() #key:街番号,value:テレポート回数
moving_dict[1]= 0
now_town = 1

while used_tele<K:
    next_town = A_list[now_town]
    used_tele += 1
    #print(used_tele,":",now_town,"→",next_town)
    
    if next_town in moving_dict:
        repeating_flag = True
        break
        
    moving_dict[next_town] = used_tele
    now_town = next_town
        
if repeating_flag == False:
    print(next_town)
else:
    moving_list = list(moving_dict.keys())
    repeating_start_town_index = moving_list.index(next_town)
    
    #print(moving_list)
    #print(moving_list[0:repeating_start_town_index])
    #print(moving_list[repeating_start_town_index:])
    
    repeating_moving_list = moving_list[repeating_start_town_index:]
    K -= len(moving_list[0:repeating_start_town_index])
    
    print(repeating_moving_list[K%len(repeating_moving_list)])

Submission status: Accepted

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

order = [-1] * (n + 1)

s = []
v = 1
while order[v] == -1:
	order[v] = len(s)
	s.append(v)
	v = a[v - 1]
c = len(s) - order[v]
l = order[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()))
timestamp = [0]*n
position = 1
period = 0
start=0
for i in range(n*2):
  if timestamp[position-1] != 0:
    start = timestamp[position-1]
    period = i-timestamp[position-1]
    break
  timestamp[position-1] =i
  position = a[position-1]
  

if k <=start:
  position = 1
  for i in range(k):
    position = a[position-1]
  print(position)
  
else:
  cycle = (k-start)%period
  for i in range(cycle):
    position = a[position-1]
  print(position)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
L = [1]
S = {1}

while A[L[-1]-1] not in S:
  last = L[-1]-1
  L.append(A[last])
  S |= {A[last]}

a = A[L[-1]-1]
j = L.index(a)
r = len(L)
l = r - j

if k+1 <= j:
    print(L[k])
else:
    print(L[j+(k-j)%l])

Submission status: Accepted

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

n, k = map(int, input().split())
A = list(map(int, input().split()))
L = [1]
S = {1}

def f(L, S):
    last = L[-1]-1
    if A[last] not in S:
        L.append(A[last])
        S |= {A[last]}
        return f(L, S)
    else:
        return L
P = f(L, S)
a = A[P[-1]-1]
j = P.index(a)
r = len(P)
l = r - j

if k+1 <= j:
    print(P[k])
else:
    print(P[j+(k-j)%l])

Submission status: Accepted

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

s=[]
o=[-1]*(n+1)
i=1
c=1
l=0
while o[i] == -1:
    o[i] = len(s)
    s.append(i)
    i = a[i-1]
    
c=len(s) - o[i]
l=o[i]
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 = a[0]
s = a[0]
g = [1]
q = []
for i in range(n+1):
    g.append(p)
    p = a[p-1]
g.reverse()
for i in range(n):
    if g[0] == g[i+1]:
        mod = i+1
        break
g.reverse()
for i in range(len(g)):
    if g[i] == g[i + mod]:
        d = i
        break
if k <= n:
    for i in range(k):
        q.append(s)
        s = a[s-1]
    q.reverse()
    print(q[0])
else:
    print(g[d+(k-d)%mod])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(i - 1 for i in map(int, input().split()))
ans = 0
count = 0
X = [-1] * N
Y = - 1
while count < K:
  if X[ans] == -1:
    X[ans] = count
    ans = A[ans]
    count += 1
  else:
    Y = X[ans] + (K - count) % (count - X[ans])
    break
if Y == -1:
  print(ans + 1)
else:
  print(X.index(Y) + 1)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import combinations, product
#import bisect# lower_bound etc
import numpy as np
def run():
    N,K = map(int, sysread().split())
    A = [0] + list(map(int, sysread().split()))

    seen = [False] * (N+1)
    arr = [1]
    seen[1] = True
    while True:
        next = A[arr[-1]]
        if seen[next]:
            arr.append(next)
            break
        arr.append(next)
        seen[next] = True
    arr = np.array(arr)
    x = int(math.log2(K)) + 1
    dub = np.array([[0] * (N+1) for _ in range(x)])
    dub[0, arr[:-1]] = np.array(arr[1:])
    for d in range(1,x):
        next1 = dub[d-1, arr[:-1]]
        next2 = dub[d-1, next1]
        dub[d, arr[:-1]] = next2

    ret = 1
    while K:
        d = int(math.log2(K))
        K -= 1 << d
        ret = dub[d][ret]
    print(ret)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def f(x,dic,i):
    p=dic1[x]
    if p in dic:
        return [dic,p]
    else:
        dic[p]=i
        return f(p,dic,i+1)

def inv(x,dic):
    for k,v in dic.items():
        if v==x:
            return k

n,k=map(int,input().split())
m=[i for i in range(n)]
l=list(map(int,input().split()))
for i in range(n):
    l[i]-=1
dic1=dict(zip(m,l))
d={0:0}
trace1=f(0,d,1)
u=trace1[0]
i=len(u)
if k<i:
    print(inv(k,u)+1)
else:
    d={trace1[1]:0}
    trace2=f(trace1[1],d,1)
    v=trace2[0]
    j=len(v)
    k=k-i
    k=k%j
    print(inv(k,v)+1)

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 = [0] + list(map(int,input().split()))
turn = [-1] * (N+1) # いつ訪問したかを記録する
c = 1
for k in range(K):
    if turn[c]!=-1:
        T = k - turn[c] # 周期
        bias = turn[c] # バイアス
        break
    turn[c] = k
    c = A[c]
else:
    print (c)
    exit()

K -= bias # Kを減らしてリスタート
K %= T
K += bias
c = 1 
for k in range(K):
    c = A[c]
print (c)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,k=map(int,input().split())
l=list(map(int,input().split()))
d=defaultdict(int)
for i in range(n):
    d[i+1]=l[i]
visited=set()
l=[]
i=1
while True:
    l.append(i)
    if i not in visited:
        visited.add(i)
    else:
        break
    i=d[i]
first=l.index(l[-1])
if k<first:
    print(l[k])
else:
    k=(k-first)%((len(l)-1)-first)
    k+=first
    print(l[k])

Submission status: Accepted

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

dic={}
kaisi=1
for i in range(1,n+1):
  if kaisi in dic:
    st=dic[kaisi]
    gl=i
    break
  else:
    dic[kaisi]=i
  kaisi=a[kaisi-1]

if k<st:
  kaisi=1
  for i in range(0,k):
    kaisi=a[kaisi-1]
  print(kaisi)
else:
  kaisuu=(k-st+1)%(gl-st)+st-1
  kaisi=1
  for i in range(0,kaisuu):
    kaisi=a[kaisi-1]
  print(kaisi)

Submission status: Accepted

Solution code:
def doubling_numpy():
    import numpy as np
    N, K = map(int, input().split())
    D = K.bit_length()
    U = N + 1
    dbl = np.zeros((D, U), dtype=np.int64)
    dbl[0, 1:] = np.array(input().split(), dtype=np.int64)

    for d in range(D - 1):
        dbl[d+1] = dbl[d, dbl[d]]

    v = 1
    for i in reversed(range(D)):
        if K & (1 << i):
            v = dbl[i, v]
    print(v)


if __name__ == "__main__":
    doubling_numpy()

Submission status: Accepted

Solution code:
n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
start,steps=1,0
root=dict()

while start not in root and steps < k:
  root[start]=steps
  steps+=1
  start=A[start-1]

if steps == k:
  print(start)
else:
  pa = steps-root[start]
  ans= root[start] + (k-steps)%pa
  root={v: k for k, v in root.items()}
  print(root[ans])

Submission status: Accepted

Solution code:
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-05-10 21:37
# @url:https://atcoder.jp/contests/abc167/tasks/abc167_d

import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    nk=list(map(int,input().split()))
    n,k=nk[0],nk[1]
    A=list(map(int,input().split()))
    pos=[1]
    cnt=0
    s=set()
    s.add(1)
    while cnt<len(A):
        temp=A[pos[-1]-1]
        pos.append(temp)
        # 注意要使用set来判断集合元素是否存在,
        # 不能使用 in pos的操作，数组的in存在超时的风险
        if temp in s:
            # pos.append(A[pos[-1]-1])
            break
        s.add(temp)
        cnt+=1
    # print (pos)
    index=pos.index(pos[-1])
    if k<index:
        print (pos[k])
    else:
        mod=(k-index)%(len(pos[index:])-1)
        # print (mod)
        print (pos[index+mod])
if __name__ == "__main__":
    main()

Submission status: Accepted

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

already = [False] * N
step = 0
now = 1
count = 0
while(already[now-1] != True):
    already[now - 1] = True
    now = A[now - 1]
    count += 1
    if count == K:
      print(now)
      exit(0)
loop = 0
cycle = 0
if(now == 1):
    step = 0
    cycle = count
    loop = K % cycle
else:
    step = 0
    temp = 1
    while(temp != now):
        temp = A[temp - 1]
        step += 1
    cycle = count - step
    loop= (K - step) % cycle

temp = 1
for i in range(step + loop):
    temp = A[temp - 1]
print(temp)

Submission status: Accepted

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

  # 各indexに対応する町に訪れるために必要な距離をいれる
  o = [-1] * (N+1)

  # 訪問順に並べた町を入れえる
  s = []

  # 現在の町
  v = 1

  # 訪れたところに再訪するまで続ける
  while(o[v] == -1):
    #sの配列長をいれることで、A[0]からA[v-1]番目の街の距離がどのくらいかを保存する
    o[v] = len(s)
    s.append(v)
    v = A[v - 1] # Aは0-indexedだから v-1

  # ループを開始する街までの距離
  l = o[v]
  # 再訪が確認できたら、訪問順を収めた配列長（A[0]からループの終端までの距離）から、ループの開始地点の距離を引くと周期が求まる
  c = len(s) - l

  # 距離Kまでにループが始まっていなければ訪問順のK番目
  if(K < l):
    print(s[K])
  # ループが始まっていたら
  else:
    k = K - l
    k %= c
    print(s[l + k])


if __name__ == "__main__":
  main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

N, K = inp_list()
A = inp_list()
A = list(map(lambda x: x - 1, A)) # 0-indexed



pos = 0 # 現在の位置を表す index
# memo = [[False, 0] for _ in range(N)] # memo[i]: [bool, tel_cnt] , [数えたか、何回移動したか]
# memo[0] = [True, 0]
visited = [False for _ in range(N)]
teleport_count = {}
distance = 0
l_pos = 0
tel_cnt = 0
while True:
    nxt = A[pos]
    # if memo[nxt][0]: # 数えた
    if visited[nxt]:
        # r_pos, l_pos = memo[pos][1], memo[nxt][1]
        r_pos, l_pos = teleport_count[pos], teleport_count[nxt]
        distance = r_pos - l_pos
        break
    tel_cnt += 1
    # memo[nxt][1] = tel_cnt
    teleport_count[nxt] = tel_cnt
    # memo[nxt][0] = True
    visited[nxt] = True
    # index 更新
    pos = nxt

def get_key_from_value(val, d):
    for k, v in d.items():
        if v == val:
            return k
# def find_idx_by_telcnt(tel_cnt):
#     for i in range(N):
#         m = memo[i]
#         if m[1] == tel_cnt:
#             return i

if K <= l_pos:
    # print(find_idx_by_telcnt(K) + 1)
    print(get_key_from_value(K, teleport_count) + 1)
else:
    diff = K - l_pos
    rem = diff % (distance + 1)
    ans_pos = l_pos + rem
    # print(find_idx_by_telcnt(ans_pos) + 1)
    print(get_key_from_value(ans_pos, teleport_count) + 1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
A = [-1] + A
memo = []
loop = []
visit = [0]*n
town = 1
while visit[town-1] < 2:
    if visit[town-1] == 0:
        memo.append(town)
    else:
        loop.append(town)
    visit[town-1] += 1
    town = A[town]
outlier = len(memo) - len(loop) 
T = len(loop)
if k <= outlier:
    print(memo[k])
else:
    print(loop[(k-outlier) % T])

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
a = inpl()
now = 1
r = [1]
fin = set([1])
while True:
    now = a[now-1]
    if now in fin:
        break
    r.append(now)
    fin.add(now)
ln = len(r)
for i in range(ln):
    if now == r[i]:
        fir = r[:i]
        nxx = r[i:]
        break
if k < i:
    print(fir[k])
else:
    k -= i
    m = len(nxx)
    print(nxx[k%m])

Submission status: Accepted

Solution code:
#4問目
import sys
N, K = map(int, input().split())
A = list(map(int, input().split()))

#すでに移動したことのある場所
already = [False] * N
step = 0
now = 1
count = 0
while(already[now-1] != True):
    already[now - 1] = True
    now = A[now - 1]
    count += 1
    if count == K: # ループに入る前にKになったらそれで終了
      print(now)
      exit(0)
# now := ループの開始地点
# count :=  地点 1 から now までの移動数
# step := ループに入るまでにワープする回数
# cycle := ループに含まれる辺の個数
# loop := (K-step) % cycle 
#        （残りの(K-step)回ループの中で回したときに ループしないで終わる回数）  
loop = 0
cycle = 0
if(now == 1):
    step = 0
    cycle = count
    loop = K % cycle
else:
    step = 0
    temp = 1
    while(temp != now):
        temp = A[temp - 1]
        step += 1
    cycle = count - step
    loop= (K - step) % cycle

temp = 1
for i in range(step + loop):
    temp = A[temp - 1]
print(temp)

Submission status: Accepted

Solution code:
import collections
n,k = map(int,input().split())
a = list(map(int,input().split()))
list = [1]
i = 0
num = a[0]
for i in range(3*n):
    list.append(num)
    num = a[num-1]

cnt = collections.Counter(list)
onevalue = [k for k,v in cnt.items() if v == 1]
lstart = len(onevalue)
lroop = len(set(list))-lstart

if k <= lstart:
    num = a[0]
    for i in range(k-1):
        num = a[num-1]
    print(num)
    exit()
elif lstart == 0:
    k = (k-lstart)%lroop
    num = 1
    for i in range(k):
        num = a[num-1]
    print(num)
    exit()
else:
    k = (k-lstart)%lroop
    num = a[0]
    if lstart > 0:
        for i in range(lstart-1):
            num = a[num-1]
    for i in range(k):
        num = a[num-1]
    print(num)
    exit()

Submission status: Accepted

Solution code:
# coding: utf-8
N, K = map(int, input().split())
A = [int(x) for x in input().split()]

# 町Aiを訪れた時刻のリスト (time[Ai] = t_Ai)
time = [-1 for _ in range(N+10)]
# new: 次に訪れる町, t: 現在の時刻
# 初期値 Ai = 1, t = 0
new = 1
t = 0

# 町newが到達済みになるまで時刻を計算
while time[new] == -1:
    time[new] = t
    new = A[new - 1]
    t += 1

# line: ループ前までの時刻, loop: ループ1回の時間
line = time[new]
loop = t - time[new]

# 場合分け
# Kがループ中の時刻なら、line分を引く
if K > line:
    K = (K - line) % loop
    for i in range(N+1):
        time[i] -= line
# Kがループ前までの時刻なら、そのまま (if K <= line:)
for i in range(N+1):
    if time[i] == K:
        print(i)
        break

Submission status: Accepted

Solution code:
#4問目
import sys
N, K = map(int, input().split())
A = list(map(int, input().split()))

#すでに移動したことのある場所
already = [False] * N
step = 0
now = 1
count = 0
while(already[now-1] != True):
    already[now - 1] = True
    now = A[now - 1]
    count += 1
    if count == K:
      print(now)
      exit(0)
# count はstartから2度現れる点までの移動数

#ループに入るまで何回ステップがあったか調べる
# loop := ループに含まれる辺の個数
loop = 0
cycle = 0
if(now == 1):
    step = 0
    cycle = count
    loop = K % cycle
else:
    step = 0
    temp = 1
    while(temp != now):
        temp = A[temp - 1]
        step += 1
    cycle = count - step
    loop= (K - step) % cycle

temp = 1
for i in range(step + loop):
    temp = A[temp - 1]
print(temp)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [i-1 for i in a] # 入力値を添字に合わせる
path = [] # 通った道を記録。通過済みのところに到達したら記録中止
now = 0
visited = [False] * n

while not visited[now]:
    path.append(now)
    visited[now] = True
    now = a[now]

# sはループの開始地点の添字
# whileループが終わった時点のnowには、堂々巡りの開始地点の添字が入っている
s = path.index(now)
length_loop = len(path) - s

if k < s:
    print(path[k]+1)
else:
    print(path[(k-s)%length_loop+s]+1)

Submission status: Accepted

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

stack=[]
done=[0 for i in range(2*(10**5))]
done[0]=0
now=0
dou=[]

while(done[now]<2):
  
  if done[now]==0:
    stack.append(now)
  else:
    dou.append(now)
  done[now]+=1
  now=A[now]-1

if K<len(stack):
  print(stack[K]+1)
else:
  print(dou[(K-len(stack)-len(dou))%len(dou)]+1)

Submission status: Accepted

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

    pos = 0
    while K > 0:
        if K&1:
            pos = a[pos]
        # doubling
        a = [a[a[i]] for i in range(N)]
        K >>= 1
    print(pos+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
l1=[0]*n
l1[0]+=1
c=0 #ループに入る前までの移動回数
now=0#現在位置
ne=a[now]-1 #次の移動位置
while True:
    if c==k:
        print(now+1)
        exit()
    if l1[ne]==0:
        l1[ne]+=1
        now=ne
        ne=a[now]-1
        c+=1
    else:
        now=ne
        ne=a[now]-1
        c+=1
        break

roop_c=0
while True:
    if c+roop_c==k:
        print(now+1)
        exit()
    if l1[ne]==1:
        l1[ne]+=1
        now=ne
        ne=a[now]-1
        roop_c+=1
    else:break

re=(k-c)%roop_c
if re==0:print(now+1)
else:
    for i in range(re):
        if i==re-1:print(ne+1)
        ne+=-ne+a[ne]-1

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
path = []
x = 1
path.append(x)
for i in range(n):
    x = a[x-1]
    path.append(x)
#print(path)
count = [0]*n
loop_st = 0
for town in path:
    count[town-1] += 1
    if count[town-1] == 2:
        loop_st = town
        break
loop_st_idx = path.index(loop_st)
loop_fin_idx = path.index(loop_st, loop_st_idx+1)
#print(loop_st_idx, loop_fin_idx)
if k >= loop_st_idx:
    k_mod = (k - loop_st_idx) % (loop_fin_idx - loop_st_idx)
    print(path[loop_st_idx + k_mod])
else:
    print(path[k])

Submission status: Accepted

Solution code:
import collections

N, K = map(int, input().split())
city_list = list(map(int, input().split()))
th_list = []
n = 0
for i in range(N):
    th_list.append(n)
    n = city_list[n] - 1

c = collections.Counter(th_list)
for i in range(N):
    if c[th_list[i]] > 1:
        break
list = [x for x, l in enumerate(th_list) if l == th_list[i]]

if K > N:
    print(th_list[(K - list[0]) % (list[1] - list[0]) + list[0]] + 1)
else:
    print(th_list[K] + 1)

Submission status: Accepted

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

when = [-1 for _ in range(N+1)]
new = 1
i = 0

while when[new] == -1:
    when[new] = i
    new = A[new - 1]
    i += 1

line = when[new]
roop = i - when[new]

if K > line:
    K = (K - line) % roop
    for j in range(N+1):
        when[j] -= line
    
for j in range(N+1):
    if when[j] == K:
        print(j)
        break

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
path = []
x = 1
path.append(x)
for i in range(n):
    x = a[x-1]
    path.append(x)
#print(path)
count = [0]*n
roop_st = 0
roop_len = 0
for town in path:
    count[town-1] += 1
    if count[town-1] == 2:
        roop_st = town
        break
roop_st_idx = path.index(roop_st)
roop_fin_idx = path.index(roop_st, roop_st_idx+1)
#print(roop_st_idx, roop_fin_idx)
if k >= roop_st_idx:
    k_mod = (k - roop_st_idx) % (roop_fin_idx - roop_st_idx)
    print(path[roop_st_idx + k_mod])
else:
    print(path[k])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, K = MI()
A = LMI()

from math import log2


class Doubling(object):

    def __init__(self, N, K, next0):
        """
        ダブリングのメモ構築 O(NlogK)
        :param N: 解の存在空間の大きさ
        :param K: K個先までのステップを考慮する
        :param next0: i番目の要素の1個先の番号を要素として持つリスト
                      次の要素が存在しない場合には-1を要素として保持する
        """
        next = [[0] * N for _ in range(int(log2(K)) + 1)]
        next[0] = next0
        for k in range(int(log2(K))):
            for i in range(N):
                if next[k][i] == -1:
                    # 2^k個次に要素が無い時、当然2^(k+1)個次にも要素はない
                    next[k + 1][i] = -1
                else:
                    # i番目の要素の2^(k+1)個次の要素 := next[k][i](i番目の要素の2^k個次の要素)の2^k個先
                    next[k + 1][i] = next[k][next[k][i]]
        self.next = next

    def query(self, p, K):
        """
        p番目の要素のK個次の要素を求める O(logK)
        """
        for i in reversed(range(int(log2(K)) + 1)):
            if p == -1:
                break
            if (K >> i) & 1:
                p = self.next[i][p]
        return p


d = Doubling(N, K, [a - 1 for a in A])
print(d.query(0, K) + 1)

Submission status: Accepted

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

history = [-1]*n
ans = []
cur = 0
for i in range(n):
    if history[cur] != -1:
        init_cnt = history[cur]
        loop_cnt = i - history[cur]
        break
    history[cur] = i
    ans.append(cur+1)
    cur = A[cur]

loop = k if k <= init_cnt else init_cnt+((k-init_cnt) % loop_cnt)
print(ans[loop])

Submission status: Accepted

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

history = [-1]*n
cur = 0
for i in range(n):
    if history[cur] != -1:
        init_cnt = history[cur]
        loop_cnt = i - history[cur]
        break
    history[cur] = i
    cur = A[cur]

loop = k if k <= init_cnt else init_cnt+((k-init_cnt) % loop_cnt)
print(history.index(loop)+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:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, K = MI()
A = LMI()

from math import log2

# next[k][i] := i番目の要素の2^k個次の要素
next = [[0] * N for _ in range(int(log2(K)) + 1)]

# 構築 O(NlogK)
next[0] = [a - 1 for a in A]
for k in range(int(log2(K))):
    for i in range(N):
        # i番目の要素の2^(k+1)個次の要素 := next[k][i](i番目の要素の2^k個次の要素)の2^k個先
        next[k + 1][i] = next[k][next[k][i]]

# クエリ O(logK)
# p番目の要素のQ個次の要素を求める
p = 0
for i in reversed(range(int(log2(K)) + 1)):
    if (K >> i) & 1:
        p = next[i][p]
print(p + 1)

Submission status: Accepted

Solution code:
'''
Fuad Ashraful Mehmet
University of Asia Pacific,Bangladesh
Date: 7th May 2020
'''

n,k=map(int,input().split())
a=list(map(int,input().split()))
a=[0]+a
vis=[-1]*(n+5)


turn=k
now=1
c=0
while vis[now]==-1:

    if turn<=0:
        print(now)
        exit()
    vis[now]=c
    c+=1
    now=a[now]
    turn=turn-1

diff =c-vis[now]

lo=1
hi=10**25
cost=vis[now]
while lo<=hi:

    mid=(lo+hi)//2
    t=mid*diff
    if t+cost<=k:
       lo=mid+1
    else:
        hi=mid-1

t=hi*diff+cost


rem=k-t

while rem>0:
    now=a[now]
    rem-=1

print(now)

Submission status: Accepted

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

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


from_ = 1
way = []
way.append(1)
way_set = set([1])

for i in range(K):
    s = A[from_ - 1]
    if(s in way_set):
        way.append(s)
        break
    else:
        way.append(s)
        way_set.add(s)
        from_ = s

key_from = way.index(way[len(way) - 1])
key_to = len(way) - 1



if(K > key_from):
    ans_loop = (K - key_from) % (key_to - key_from)
    ans_num = key_from + ans_loop

    print(way[ans_num])
else:
    print(way[K])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

route = defaultdict(int)
i = 0
loop = []
tail = []

while route[i] < 2:

    if route[i] == 0:
        tail.append(i)
    else:
        loop.append(i)
    
    route[i] += 1
    i = a[i] - 1

if len(tail) > k:
    print(tail[k] + 1)
else:
    temp = len(tail) - len(loop)
    print(loop[(k-temp) % len(loop)] + 1)

Submission status: Accepted

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

visited= [1]
ed = set([1])
for i in range(K):
    next_town  = al[visited[i] - 1]
    if next_town in ed:
        loop_sta = visited.index((next_town)) #　visited_townsにおけるループ開始のインデックス
        loop_end = len(visited) #visited_townsにおけるループの終わりのインデックス
        loop_length = loop_end - loop_sta #繰り返すループの長さ
        amari = (K - loop_sta) % loop_length
        ans = visited[loop_sta + amari]
        print(ans)
        exit()
    else:
        visited.append(next_town)
        ed.add(next_town)
        continue

else:
    print(visited[-1])