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 defaultdict

N,K = map(int,input().split())
A = list(map(int,input().split()))
position = 1
past_path = defaultdict(lambda : -1)
loop_pos = -1

def move(position):
	return A[position-1]

for i in range(1,K+1):
	if(past_path[position] != -1):
		loop_pos = past_path[position]
		break
	past_path[position] = i-1
	position = move(position)

new_past_path = defaultdict(lambda : -1)
for k,v in past_path.items():
	if v >= loop_pos:
		new_past_path[v-loop_pos] = k

if loop_pos != -1:
	print(new_past_path[(K-loop_pos)%len(new_past_path)])
else:
	print(position)

Submission status: Accepted

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

s=[]
ordn=[]
for i in range(n+1):
    ordn.append(-1)

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    n,k = map(int,input().split())
    l = list(map(int,input().split()))
    roop = [1]
    stayed = [0]*n
    for i in range(n):
        next_city = l[roop[-1]-1]
        if stayed[next_city-1]:
            endindex = i
            for j,r in enumerate(roop):
                if r == next_city:
                    startindex = j
            break
        else:
            roop.append(next_city)
            stayed[next_city-1] = 1

    if k < startindex:
        print(roop[k])
    else:
        dis = endindex - startindex + 1
        a = (k - startindex) % dis
        print(roop[a + startindex])
main()

Submission status: Accepted

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

roop = [1]
count = [0 for i in range(n)]
count[0] += 1

#start_index = 0
#end_index = n-1
for i in range(n):
    next_city = lis[roop[-1] - 1]
    if count[next_city-1]: #if already visit "next_city", "next_city" is start city of roop, roop[i] is end city of roop
        end_index = i
        for j, city in enumerate(roop):
            if city == next_city:
                start_index = j
        break
    else:
        roop.append(next_city)
        count[next_city-1] += 1

if k <= start_index:
    print(roop[k])
else:
    roop_len = end_index - start_index + 1 #length of roop
    distance = (k - start_index) % roop_len #distance betoween start_index and destination
    print(roop[start_index + distance])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000000)
s = 0 
def main():
    n, k = map(int, readline().split())
    a = [int(i)-1 for i in readline().split()]
    done = [0 for _ in range(n)] 
    cycle = []
    def dfs(x):
        global s
        if done[x] == 1:
            s = x
            return
        nx = a[x]
        done[x] = 1
        cycle.append(x)
        dfs(nx)

    dfs(0)
    start_idx = cycle.index(s)
    ln = len(cycle)
    if k < ln: 
        print(cycle[k]+1)
    else:
        k -= start_idx
        idx = start_idx+(k%(ln-start_idx))
        print(cycle[idx]+1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getans(v,K):
    k=0
    now=v
    while K>0:
        if K&1:
            now=doubling[k][now]
        K=K>>1
        k+=1
    return now

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

doubling=[[-1]*N for i in range(61)]
for i in range(N):
    doubling[0][i]=A[i]-1
for k in range(1,61):
    for i in range(N):
        doubling[k][i]=doubling[k-1][doubling[k-1][i]]
print(getans(0,K)+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
visited = [-1 for _ in range(n)]
visited[0] = 0
l = [0]
for i in range(k):
    nex = a[l[i]]
    if visited[nex] != -1:
        res = visited[nex]
        cyc = i + 1 - visited[nex]
        break
    else:
        l += [nex]
        visited[nex] = i + 1
else:
    res = k + 1
print(l[res + (k - res) % cyc] + 1 if k > res else l[k] + 1)

Submission status: Accepted

Solution code:
## coding: UTF-8

#ダブリングを利用した実装

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

#2**59 < 10**18< 2**60より2**60まで格納する
l = [0] * (N*61)

for j in range(N):
    l[j] = A[j]


for i in range(1,61):
#for i in range(1, 4):
    for j in range(N):
        p = l[(i-1)*N+j] #一段上を参照(2**(i-1)回移動した時の移動先)
        q = l[(i-1)*N+(p-1)] #pから2**(i-1)回移動した時の移動先を参照　＝　2**i 回移動した時の移動先
        l[i*N+(j)] = q
    #print(l)
#print(l)

bin_str = format(K, 'b')
#print(bin_str)
s = bin_str[::-1]
#print(s)
now = 1 #start地点
for i in range(len(s)):
    if(s[i] == '1'):
        now = l[(i)*N + (now-1)]
        #print(now)

        '''
        next_index = i*N + l[i*N + (now-1)]-1
        nex = l[next_index]
        now = nex
        print(now)
        '''
print(now)

Submission status: Accepted

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

s=1
ans=0
v={}
for j in range(len(a)):
	if(ans==k):
		print(s)
		exit()
	if(s-1 in v):
		break
	else:
		v.update({s-1:ans})
		s=a[s-1]
		ans+=1
lens=ans-v[s-1]
k=(k-ans)%lens
for j in range(k):
	s=a[s-1]
print(s)

Submission status: Accepted

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

stack = [0]
visited = {0}

now = 0
while A[now] not in visited:
    now = A[now]
    stack.append(now)
    visited.add(now)

roop_start = A[now]

roop = []
while stack[-1] != roop_start:
    roop.append(stack.pop())
roop.append(roop_start)
roop = roop[::-1]
roop_size = len(roop)

now = 0
while now != roop_start and K:
    now = A[now]
    K -= 1

if K == 0:
    print(now + 1)
else:
    print(roop[K % roop_size] + 1)

Submission status: Accepted

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

d = {i:[] for i in range(1, N+1)}
for i, j in enumerate(A, start=1):
    d[i].append(j)

dist[1] = 0
q = [1]
cycle = 0
ls = 0
while q:
    a = q.pop()
    for b in d[a]:
        if dist[b]==-1:
            dist[b] = dist[a] + 1
            q.append(b)
        elif dist[b]==0 or dist[b]:
            cycle = dist[a] + 1 - dist[b]
            ls = b
            break

b = (K-dist[ls])%cycle if K>dist[ls] else K
c = dist[ls]+b if K>dist[ls] else K
for i, j in enumerate(dist):
    if j==c:
        print(i)
        break

Submission status: Accepted

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

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

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

moved = {}
now_city = 1
next_city = A[0]
i=0

while i < N:
    moved[now_city] = i
    if next_city in moved:
        break
    now_city = next_city
    next_city = A[now_city-1]
    i += 1

# i 回目の試行で、now_city から next_city に移ろうとしている

mod = i - moved[next_city]

moved_list = [x for x in moved.keys()]

loop_list = moved_list[moved[next_city]:i+1]
loop = len(loop_list)

if K < moved[next_city]:
    print(moved_list[K])
else:
    print(loop_list[(K-moved[next_city])%loop])


# print(f"{next_city=} {i=}")
# print(f"{loop_list=}")
# print(f"{moved_list=}")
# print(f"{K-moved[next_city]=}")
# print(f"{loop=}")

# ans = 5
# 6 10
# 2 3 4 5 4 6

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
from collections import deque

def resolve():
    n, k = map(int, input().split())

    a_s = list(map(int, input().split()))
    # 添え字は0始まり、町番号は1始まりなので、添え字0を足し込んで値を合わせる
    a_s.insert(0, 0)

    # 到達済みフラグ(添え字0は使わないので+1
    # arrived = [False for i in range[n+1]]

    # 町1からの距離(添え字0は使わないので+1
    distance = [-1 for i in range(n+1)]
    # 初期値：町1は町1との距離0
    distance[1] = 0

    # queを作成
    que = deque()
    que.append(1) # 初期値：町1

    # 答えを求めるために必要な情報を種痘
    while len(que) is not 0:

        now = que.pop()
        next = a_s[now]
        if distance[next] is not -1:
            # 循環が発生
            # 町1からループが発生する町までの距離
            # 例：1->6->2->5->3->2->5->2->5->3 ・・・というパターンの場合は「2」。2->5->3->2がループなので。
            no_loop = distance[next]
            # ループが発生する町(ループ始点)からループが発生する町(ループ終点)までの距離
            loop = distance[now] - distance[next]

        else:
            # 新しい街に到達した場合
            # 町1からの距離を設定
            distance[next] = distance[now] + 1
            # 次のとび先をキューに追加
            que.append(next)

    # 答えを出力(方程式の信頼性はトレース.xlsxを見ると良い。多分問題ない・・!
    if k <= no_loop:
        print(distance.index(k))
    else:
        print(distance.index((k - no_loop) % (loop + 1) + no_loop))

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
#     def test_入力例_1(self):
#         input = """4 5
# 3 2 4 1"""
#         output = """4"""
#         self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 727202214173249351
6 5 2 5 3 2"""
        output = """2"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

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

    visited = [-1 for _ in range(N)]
    roop_As = [0]
    now_i = 0
    visited[now_i] = 0
    for _ in range(K):
        now_i = As[now_i]
        if visited[now_i] >= 0:
            break
        roop_As.append(now_i)
        visited[now_i] = len(roop_As) - 1

    if K < len(roop_As):
        print(roop_As[-1] + 1)
    else:
        roop_As = roop_As[visited[now_i]:]
        print(roop_As[(K - visited[now_i]) % len(roop_As)] + 1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

A.insert(0,-1)
root = [1]

for _ in range(N-1):
    root.append(A[root[-1]])

if K > N:
    start = root.index(root[-1])
    index = (K - start) % (len(root) - start - 1) + start
    ans = root[index]
else:
    ans = root[K]

print(ans)

Submission status: Accepted

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

visited = [0] * n

r = k
p = 0
detected = False
loop_length = None
while r > 0:
    visited[p] += 1
    if visited[p] >= 3 and not detected:
        detected = True
        loop_length = sum(1 for v in visited if v >= 2)
        #print('loop is found; length = ', loop_length, ' seqs=', [i+1 for i,v in enumerate(visited) if v >= 2])
        #print('shorten p={}, r={}, r_next={}'.format(p+1, r, r % loop_length))
        r %= loop_length
    else:
        p = an[p]
        r -= 1

print(p + 1)

Submission status: Accepted

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

d = {}
d_n = {}
first_d_n = {}
for i in range(N):
  d[i+1] = a[i]
  if i+1 == 1:
    d_n[i+1] = 1
  else:
    d_n[i+1] = 0

m = 1
k = 0 # 累計移動回数
first_d_n[1] = 0

while m:
  m = d[m]
  d_n[m] += 1
  k += 1
  if d_n[m] == 1:
    first_d_n[m] = k
  
  if d_n[m] == 2:
    break
    
first_n = first_d_n[m] # loopの起点に入ったとき

if K - first_n >= 0:
  loop_mod = (K - first_n) % (k - first_n)
  #print(loop_mod)

  if loop_mod == 0:
    print(m)
  else:  
    for l in range(loop_mod):
      m = d[m]
    print(m)

  # print(first_d_n[loop_mod - 
else:
  m = 1
  for l in range(K):
    m = d[m]
  print(m)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
l=[-1]*(n+1)
tmp=[]
pos=1
cnt=0
while 1:
  if l[pos]!=-1:
    t=cnt-l[pos]
    if k<cnt:
      print(tmp[k])
    else:
      print(tmp[l[pos]+(k-cnt)%t])
    break
  l[pos]=cnt
  cnt+=1
  tmp.append(pos)
  pos=arr[pos-1]

Submission status: Accepted

Solution code:
def resolve():
	n, k = map(int, input().split())
	a = list(map(int, input().split()))
	rec = [True]*(n+2)
	now = 0
	stp = [1]

	while rec[now]:
		rec[now] = False
		now = a[now] - 1
		stp.append(now+1)
	before_loop = stp.index(now+1)
	loop = stp[before_loop:-1]
	if k <= (before_loop):
		print(stp[k])
	else:
		r = (k - before_loop) % len(loop)
		print(loop[r])
resolve()

Submission status: Accepted

Solution code:
def resolve():
	n, k = map(int, input().split())
	a = list(map(int, input().split()))
	rec = [True]*(n+2)
	now = 0
	stp = [1]

	while rec[now]:
		rec[now] = False
		now = a[now] - 1
		stp.append(now+1)
	before_loop = stp.index(now+1)
	loop = stp[before_loop:-1]
	if k <= (before_loop + 1):
		print(stp[k])
	else:
		r = (k - before_loop) % len(loop)
		print(loop[r])
resolve()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
visited = []
search = set()
now = 1#最初の街にいる
next_town = A[now-1]
count = 1
while(count<=N):
    if next_town in search:#もし次の街が訪れたことがある場合
        break#ループするので抜け出す
    visited.append(now)#今いる街は訪れたこととなるので記録する
    search.add(now)
    next_town = A[now-1]#次に行く街を探す
    now = next_town#次の街に着いたこととして変数を代入
    count += 1

first_roop_city = A[visited[-1]-1]#最初にループした街
first_roop_city_index = visited.index(first_roop_city)#何回目のテレポートにループが始まったか
if K < len(visited):
    print(visited[K])
else:
    visited = visited[first_roop_city_index:]
    L = len(visited)
    print(visited[(K-first_roop_city_index)%L])

Submission status: Accepted

Solution code:
import sys
N, K = map(int, input().split())
A = list(map(int, sys.stdin.readline().split()))
visited = [0] * N
visited[0] = 1
ikisaki = 0
c = 1
while c < N:
    ikisaki = A[ikisaki] - 1
    c += 1
    if visited[ikisaki]:
        loop = c - visited[ikisaki]
        c = N
    else:
        visited[ikisaki] = c

if K - (visited[ikisaki] - 1) >= 0:
    amari = (K - (visited[ikisaki] - 1)) % loop
else:
    amari = K - (visited[ikisaki] - 1)
new = [i - visited[ikisaki] for i in visited]
print(new.index(amari) + 1)

Submission status: Accepted

Solution code:
N,K = (int(i) for i in input().split()) 
A = [int(i) for i in input().split()] 
A_done = [0]*N
A_route = []
point = 1
end_point = 0
while A_done[point-1]==0:
  A_done[point-1] = 1
  A_route.append(point)
  point = A[point-1]
  if A_done[point-1]==1:
    end_point = point
cal = K%len(A_route)
roop = A_route.index(end_point)
f_len = len(A_route[:roop])
roop_len = len(A_route[roop:])
A_roop = A_route[roop:]
if K >= f_len + roop_len:
  cal = (K-f_len)%(len(A_roop))
  #print(cal)
  print(A_roop[cal])
else:
  print(A_route[K])

Submission status: Accepted

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

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

l = [-1]*n #list for order of teleportation
l[0] = 0
ct = 0 #current town
od = 1 #order of teleportation

while True:
    k -= 1
    ct = a[ct]
    if k == 0:
        break
    if l[ct] == -1:
        l[ct] = od
        od += 1
    else:
        cycle = od - l[ct]
        k %= cycle
        od += 1

print(ct + 1)

Submission status: Accepted

Solution code:
def solve(n, k, a):
    S = set()
    x = 1
    S.add(x)
    loop_start = -1
    d = -1
    for i in range(n):
        x = a[x-1]
        if x in S:
            loop_start = x
            d = i+1
            break
        S.add(x)
    in_loop = False
    x, T = 1, 0
    for i in range(n):
        if x == loop_start:
            if in_loop:
                break
            in_loop = True
        if in_loop:
            T += 1
        x = a[x-1]
    if k > n:
        k = (k - d) % T + d
    x = 1
    for i in range(k):
        x = a[x-1]
    return x

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

Submission status: Accepted

Solution code:
import numpy as np

def check_num_of_remaining_teleport(num_of_teleport, i):
    if num_of_teleport == 0:
        print(i)
        exit()

num_of_town, num_of_teleport = map(int, input().split())
town = np.array(list(map(int, input().split())))

# 香り高い町の探索
i = 1
# テレポートの移動ルールに合わせて1始まりにする
fragranttown_index = 1
fragrants = [0] * num_of_town
fragrants[0] = 1
for _ in range(num_of_town):
    i = town[i - 1]
    num_of_teleport = num_of_teleport - 1

    # 移動回数が終了した場合
    check_num_of_remaining_teleport(num_of_teleport, i)

    # すでに通った町か
    if fragrants[i - 1] != 1:
        fragrants[i - 1] = 1
    else:
        fragranttown_index = i
        break

# 香り高い町への再訪までの回数探索
# 再訪までの回数
revisit = 0
j = fragranttown_index
for _ in range(num_of_town):
    j = town[j - 1]
    revisit = revisit + 1
    num_of_teleport = num_of_teleport - 1

    # 移動回数が終了した場合
    check_num_of_remaining_teleport(num_of_teleport, j)

    # テレポート先が香り高い町なら
    if fragranttown_index == j:
        break

# 香り高い町からの最終移動
num_of_last_teleport = num_of_teleport % revisit
k = fragranttown_index
# rangeの中は一時変数にした方が高速
for _ in range(num_of_last_teleport):
    k = town[k - 1]
    
print(k)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

sys.setrecursionlimit(10**6)
def search(n, step, rec, seq, k):
	if rec[n] != -1:
		c = step - rec[n]
		sim = (k - rec[n]) % c
		v = n
		for i in range(sim):
			v = seq[v-1]
		print(v)
		return
	rec[n] = step
	if step == k:
		print(n)
		return
	search(seq[n-1], step + 1, rec, seq, k)
def resolve():
	n, k = map(int, input().split())
	seq = list(map(int, input().split()))
	rec = [-1]*(n+1)
	search(1, 0, rec, seq, k)

resolve()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(lambda x:int(x)-1,input().split()))
lst=[0]
now=0
memo=0
town=[0]*n
town[0]=1
b=0
for i in range(k):
	now=a[now]
	if town[now]==1:
		memo=now
		b=1
		break
	lst.append(now)
	town[now]=1
if b==1:
	i=lst.index(memo)
	l=len(lst)
	if memo!=0:
		lst=lst[i:]
		l-=len(lst)
		print(lst[(k-l)%len(lst)]+1)
	else:
		print(lst[k%l]+1)
else:
	print(now+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[1]
di={}
di[1]=1
for i in a:
    b=a[l[-1]-1]
    if b in di:
        x=b
        break
    l.append(b)
    di[b]=1
t1=0
for j in l:
    if j==x:
        break
    else:
        t1+=1
t2=len(l)-t1
if k<=t1:
    print(l[k])
else:
    num=(k-t1)%t2
    print(l[t1+num])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
pos = 1
path = [1]
TF = [False] + [True] * (n-1)
for i in range(k):
    pos = a[pos - 1]
    if TF[pos - 1]:
        path.append(pos)
        TF[pos - 1] = False
    else:
        break
first = path.index(pos)
ans = (k - first) % (len(path) - first) + first
print(path[ans])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
pos = 1
path = [1]
flag = [True] * n
flag[0] = False
for i in range(k):
    pos = a[pos - 1]
    if flag[pos - 1]:
        path.append(pos)
        flag[pos - 1] = False
    else:
        break
d = path.index(pos)
ans = (k-d) % (len(path) - d) + d
print(path[ans])

Submission status: Accepted

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

A = [a - 1 for a in A]

now = 0
while K:
    if K % 2: now = A[now]
    A = [A[a] for a in A]
    K //= 2

print(now + 1)

Submission status: Accepted

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

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

Visited = [-1]*N
now = 1
Order = [0]*N

loopcount = 1
Order[0] = 1
Visited[0] = 1
for i in range(1,N):
    nt = Map[now-1]
    Order[i] = nt
    loopcount += 1
    if Visited[nt-1] == -1:
        Visited[nt-1] = loopcount
    else:
        break
    now = nt
    

ns = Visited[nt-1]
period = loopcount - ns

if period == 0:
    period = loopcount
    ns = 0

Kmod = K - ns
if Kmod > 0:
    Kmod %= period

print(Order[ns+Kmod])

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    As = [int(x) for x in stdin.readline().rstrip().split()]

    done = [0] * N
    step = -1
    start = 0
    current = 1
    between = 0

    while True:
        if done[current - 1] > 0:
            start = done[current - 1] - 1
            between = step - done[current - 1] + 1
            break
        step += 1
        done[current - 1] = step
        current = As[current - 1]

    if K <= step:
        print(done.index(K) + 1)
    else:
        res = (K - start) % between
        if res == 0:
            res = between
        print(done.index(res + start) + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
lambda_1=lambda s:int(s)-1
a=list(map(lambda_1, input().split()))
#print(a)
r=[-1]*n
b=[]
c=0
while True:
	if len(b)==k-1:
		print(a[c]+1)
		exit()
	if r[a[c]]!=-1:
		a0=b.index(a[c])
		k0=(k-1-a0)%(len(b)-a0)+a0
		"""print(k,len(b),a0)
		print("b",b,a[c])
		print("r",r)
		print(a0,k0)"""
		print(b[k0]+1)
		exit()
	b.append(a[c])
	r[a[c]]=c
	c=a[c]

Submission status: Accepted

Solution code:
def main():
    DOUBLING_ROWS = 60  # 2**60 > 10**18
    n, k = [int(x) for x in input().split()]
    table = []  # [start][teleporting]
    table_append = table.append
    table_append([int(x) - 1 for x in input().split()])  # 2**0 teleport
    for _ in range(DOUBLING_ROWS):
        pre = table[-1]
        table_append([pre[x] for x in pre])
    now = 0
    for i, row in enumerate(table):
        if ((1 << i) & k) > 0:
            now = row[now]
    return now + 1


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

Submission status: Accepted

Solution code:
#import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N,K = LI()
A = LI()

#方針
#ループ検知でmod演算に移行
hist = []
now = 0
chk = [-1] * N
while True:
	hist.append(now+1)
	if chk[now] != -1:
		# ループ検知
		break
	chk[now] = len(hist)-1
	now = A[now]-1
#print("histpos[town]:",chk)
#print("hist:",hist)
loopstart = chk[hist[len(hist)-1]-1]+1
if K >= len(hist):
	K-=loopstart
	K%=len(hist)-loopstart
	print(hist[loopstart+K])
else:
	print(hist[K])

Submission status: Accepted

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


visited = [0] * N

idx = 0

town = 0

if K <= N:
    for i in range(K):
        idx = t[idx] -1
    print(idx+1)
else:
    for i in range(K):
        if visited[idx]:
            cycle = i - visited[idx]
            rem_step = (K - i) % cycle
            town = visited.index(visited[idx] + rem_step)
            break


        visited[idx] = i
        idx = t[idx] - 1


    print(town+1)

Submission status: Accepted

Solution code:
n,k = (int(x) for x in input().split())
to = [int(x) for x in input().split()]
st = [True] * n
root = []

now = 1
while(k > 0 and st[now - 1]):
    root.append(now)
    #print(now,"->",end="")
    st[now - 1] = False
    now = to[now - 1]
    k -=1

if k > 0:
    value = root.index(now)
    k %= len(root[value:])
    #print("k = ",k)
    for i in range(k):
        now = to[now-1]
    print(now)
else:
    print(now)

Submission status: Accepted

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

memo = {}
p = 0
for i in range(k):
  if p in memo:
    itvl = i - memo[p]
    rest = (k-i-1)%itvl
    for j in range(rest+1):
      p=A[p]
    print(p+1)
    exit()
  else:
    memo[p]=i
  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()))
    path = [-1] * N * 2
    idx = 0
    visited = [False] * N
    cur = 0
    loop = -1
    while K:
        K -= 1
        if loop == -1 and visited[cur]:
            loop = idx - path.index(cur)
            K %= loop
        path[idx] = cur
        visited[cur] = True
        cur = A[cur] - 1
        idx += 1
    print(cur + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
N, K = map(int, input().split())
As = [0] + list(map(int, input().split()))
# print(As)
d = [-1]*(N+1)
i = 1
step = 1
while step <= K:
	# print("step: {}, idx: {}".format(step,i))
	next_i = As[i]
	if d[next_i] != -1:
		freq = step - d[next_i]
		step = step + ((K - step) // freq)*freq
	d[next_i] = step
	step += 1
	i = next_i
 
print(i)

Submission status: Accepted

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

loc = 0
visited_bkt = [-1 for _ in range(2 * 10 ** 5 + 1)]
count = 0
loop_len = -1
while True:
    visited_bkt[loc + 1] = count
    loc = a[loc]
    count += 1
    if visited_bkt[loc + 1] >= 0:
        loop_len = count - visited_bkt[loc + 1]
        break
start_len = count - loop_len
print(visited_bkt.index(start_len + (k - start_len) % loop_len) if k >= count else visited_bkt.index(k))

Submission status: Accepted

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

array = input().split()
for i in range(len(array)):
    array[i] = int(array[i])

now = 1

history = []
sethistory = set()
start_number = -1

for i in range(K):
    history.append(now)
    sethistory.add(now)
    now = array[now - 1]
    if(now in sethistory):
        start_number = now
        break

if not(start_number == -1):
    start_ind = history.index(start_number)
    length = len(history) - start_ind
    mod = (K - start_ind) % length
    now = history[start_ind + mod]

print(now)

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:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, k = map(int, input().split())
    b = list(map(lambda x : int(x) - 1, input().split()))

    now = 0
    while k:
        if k & 1: now = b[now]
        b = [b[b[i]] for i in range(n)]
        k >>= 1
    print(now + 1)
resolve()

Submission status: Accepted

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

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

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

order = 0
now = 0

while k > 0:
    k -= 1
    now = a[now]
    order += 1
    if l[now] == -1:
        l[now] = order
    else:
        loop = order - l[now]
        k %= loop
        break

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

print(now + 1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
done=[-1 for _ in range(N)]
done[0]=0
n=0
now=0
init=0
loop=N
log=[0]

while n<N:
    log.append(A[log[-1]]-1)
    n+=1
    if done[log[-1]]>-1:
        init=done[log[-1]]
        loop=n-done[log[-1]]
        break
    done[log[-1]]=n

if K<init:
    print(log[K]+1)
else:
    num=init+(K-init)%loop
    print(log[num]+1)

Submission status: Accepted

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

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

now = 0
d = {}
if N < K:
    for i in range(0,N):
        if now in d:
            K -= d[now]
            K %= i-d[now]
            for j in range(K):
                now = A[now]
            break
        else:
            d[now] = i

        now = A[now]
else:
    for j in range(K):
        now = A[now]
        
print(now+1)

Submission status: Accepted

Solution code:
import sys

def machi(k,W):
    visited = set()
    t = 0
    time = 0
    result = []
    while not t in visited:
        if time > k:
            return -1, result
        visited.add(t)
        result.append(t)
        t = W[t] - 1
        time += 1
    bp = result.index(t)
    return bp,result

        

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')


n,k = nm()
a = nl()
bp,roop = machi(k,a)
if bp == -1:
    print(roop[-1]+1)
    exit()

l_dist = len(roop[bp:])
f_dist = bp
fs = k - f_dist
arp = f_dist + (fs % l_dist)
print(roop[arp]+1)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
a=[0]+a
ans=1
while k:
  if k&1:
    ans=a[ans]
  a=[a[i] for i in a]
  k>>=1
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    citys_num, k = map(int, input().split())
    cities = list(map(int, input().split()))

    visited = set()
    route = []
    isAgain = False
    currectCity = 1
    while not isAgain:
        if currectCity in visited:
            route.append(currectCity)

            isAgain = True
        else:
            visited.add(currectCity)
            route.append(currectCity)

            currectCity = cities[currectCity - 1]
    if len(route) > k:
        print(route[k])
        return
    loopstart = route.index(route[-1])
    loop = route[loopstart:-1]

    k = k - loopstart
    k = k % len(loop)

    print(loop[k])
resolve()

Submission status: Accepted

Solution code:
def main():

  N, K = map(int, input().split())   
  A = [0] + list(map(int, input().split()))
  cur = 1
  visited = [-1] * (N + 1)
  visited[cur] = 0
  for i in range(1, K + 1):
    next_cur = A[cur]
    if next_cur == cur:
      print(next_cur)
      return
    elif visited[next_cur] != -1:
      mod = i - visited[next_cur]
      start = visited[next_cur]
      break
    else:
      visited[next_cur] = visited[cur] + 1
      cur = next_cur
  else:
    print(next_cur)
    return
  K = (K - start) % mod
  print(visited.index(K+start))
  
  
if __name__ == "__main__":
  main()