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:
def main():
    n, k = map(int, input().split())
    a = [int(i) - 1 for i in input().split()]
    s = 0
    m, l = 0, 0
    p = []
    h = set()
    for _ in range(n):
        p.append(s)
        h.add(s)
        s = a[s]
        if s in h:
            m = p.index(s)
            l = len(h) - m
            break
    if k <= m:
        print(p[k] + 1)
    else:
        print(p[(k - m) % l + m] + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
N towns
teleporter each town
teleporter at town i -> town A_i
k-times teleporter after starting at town 1
"""

from collections import deque

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

visited = [0] * n
path = deque()
cur = 0

while not visited[cur]:
    visited[cur] = 1
    path.append(cur)
    cur = a[cur]

while path[0] != cur and k > 0:
    k -= 1
    path.popleft()

#print(path)
if k == 0:
    print(path[0] + 1)
else:
    print((path[k % len(path)]) + 1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
#n, k = 200000, 100
#a = [i+2 for i in range(n-1)] + [2]
move = [a[i] - 1 for i in range(n)]
#print(move)
d = [-1 for _ in range(n)]
d[0] = 0
cur = 0
for _ in range(300000):
    to = move[cur]
    if d[to] == -1:
        d[to] = d[cur] + 1
    else:
        rou = d[cur] + 1 - d[to]
        rou_start = to
        break
    cur = to
#print(rou_start, rou)
#print(d)
if k < d[rou_start]:
    x = k
    rou_start = 0
else:
    x = (k - d[rou_start]) % rou
cur = rou_start
for _ in range(x):
    cur = move[cur]


print(cur + 1)

Submission status: Accepted

Solution code:
inf = 10**15
mod = 10**9+7

n,k = map(int, input().split())
a = list(map(int, input().split()))
firstkouho = []
roopkouho = []
visited = [False for i in range(n)]
tmp = 0
while visited[tmp] == False:
    visited[tmp] = True
    tmp2 = a[tmp] - 1
    tmp = tmp2
roopstart = tmp


tmp = 0
countstart = 0
while tmp != roopstart:
    firstkouho.append(tmp)
    tmp2 = a[tmp]-1
    tmp = tmp2
    countstart += 1

length = 1
roopkouho.append(roopstart)
if a[roopstart]-1 != roopstart:
    tmp = a[roopstart]-1
    while tmp != roopstart:
        roopkouho.append(tmp)
        length += 1
        tmp2 = a[tmp] - 1
        tmp = tmp2



if k < countstart:
    if countstart != 0:
        print(firstkouho[k]+1)
    else:
        print(1)
else:
    r = k-countstart
    print(roopkouho[r%length]+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
teleporter = list(map(int, input().split()))
loop = [0]
checked = [False] * n
checked[0] = True
next_teleporter = teleporter[0] - 1

while not checked[next_teleporter]:
    checked[next_teleporter] = True
    loop.append(next_teleporter)
    next_teleporter = teleporter[next_teleporter] - 1

if next_teleporter == loop[0] - 1:
    index = k % len(loop)
    print(loop[index] + 1)
else:
    for i in range(len(loop)):
        if next_teleporter == loop[i]:
            s = i
            break
    if s > k:
        print(loop[k] + 1)
    else:
        loop = loop[s:]
        index = (k - s) % len(loop)
        print(loop[index] + 1)

Submission status: Accepted

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

visited = [-1 for _ in range(N + 1)]
visited[1] = 0
cur = 1
precur = 0

cnt = 0
while cnt < K:
    precur = cur
    cur = A[cur]
    cnt += 1
    if visited[cur] > -1:
        break
    else:
        visited[cur] = cnt

if cnt == K:
    print(cur)
    exit()

ite = cnt - visited[cur]
x = (K - cnt + 1) % ite
cur = precur

cnt = 0
while cnt < x:
    cur = A[cur]
    cnt += 1
print(cur)
exit()

Submission status: Accepted

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

c = [None] * 200000
cc = set()
p = 0
st = 0
ed = 0
i = 0
while True:
    c[i] = p
    cc.add(p)
    i += 1
    p = a[p]
    if p in cc:
        st = c.index(p)
        ed = i
        break
if k < ed:
    print(c[k] + 1)
else:
    k -= st
    k %= ed - st
    print(c[st + k] + 1)

Submission status: Accepted

Solution code:
list=input().split(" ")
N=int(list[0])
K=int(list[1])
move_list=input().split(" ")
for i in range(N):
    move_list[i]=int(move_list[i])
move_list.insert(0,0)
list_count=[0 for i in range(N+1)]
find_loop=[]

now=1
count=0
flag=0
while(count<K):
    if list_count[now]==1:
        find_loop.append(now)
    elif list_count[now]==2:
        flag=1 #ループ省略する場合フラッグを立てる
        break
    list_count[now]+=1
    now=move_list[now]
    count+=1

if flag==0:
    now=1
    for i in range(K):
        now=move_list[now]
    print(now)
    
else:
    tmp=(K-count)%len(find_loop)
    print(find_loop[tmp])

Submission status: Accepted

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

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

memo = [0]*(n+1)

for i in range(n):
    memo[i+1] = t[i]

move = 1

count = 0

check = [0]*(n+1)

while check[move] == 0 and count < k-1:
    check[move] += 1
    move=memo[move]
    count += 1

if k == count:
    print(memo[move])
else:
    count2 = 0
    check = [0]*(n+1)
    move_log = []
    while check[move] == 0:
        move_log.append(move)
        check[move] += 1
        move=memo[move]
        count2 += 1
    print(move_log[(k-count)%count2])

Submission status: Accepted

Solution code:
import sys

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

#各頂点が白(0)か黒(1)か
flag = [-1 for _ in range(n)]

#dfsで色を塗っていく
#頂点の数をN、辺の数をMとすると、O(N+M)で解ける
stack = [a[0]-1]
flag[0] = 0
count = 0
while stack:
	u = stack.pop()
	if flag[u] == -1:
		stack.append(a[u] - 1)
		count += 1
		if count == k:
			print(u+1)
			sys.exit()
		flag[u] = count
	else:
		loop = count - flag[u] + 1
		#print(count,flag[u],loop)
		num = (k - flag[u]) % loop
		#print(num)
		break

if num == 0:
	print(u + 1)
else:
	ans = a[u]
	for i in range(num-1):
		ans = a[ans-1]
	print(ans)

Submission status: Accepted

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

go = dict()
res = []

go[0] = True
res = [0]

now = a[0]
while True:
    if now in go:
        break
    res.append(now)
    go[now] = True
    now = a[now]

# 1
# [0, 1, 2, 3]
# (5 - 1) % (xunhuan)
amari = res.index(now)
xunhuan = res[amari:]
#print(res, xunhuan, amari)

if k <= amari:
    print(res[k] + 1)
else:
    print(xunhuan[ (k - amari) % len(xunhuan)] + 1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
dists = list(map(int, input().split()))
 
import sys
n = N - 1
idists = [d - 1 for d in dists]
visits = [-1] * N
 
# 手レポーターがループしてる部分を探す
now = 0
count = 0
while True:
#     print(now, visits)
    if visits[now] >= 0:
        break
    visits[now] = count
    now = idists[now]
    count += 1
    if count == K:#早く着いちゃった
        print(now + 1)
        sys.exit()
 
# ループを端折る
cycle = count - visits[now]
rest = (K - count) % cycle
for _ in range(rest):
#     print(" ", now)
    now = idists[now]
print(now + 1)

Submission status: Accepted

Solution code:
import sys;input=lambda:sys.stdin.readline().rstrip();ints=lambda:list(map(int,input().split()))

def main():
    n,k=ints()
    a=ints()
    passed=[]
    flg,p=0,0
    while flg==0:
        if a[p] == 'p':
            flg=1
            s=passed.index(p)
            break
        else:
            passed.append(p)
            pp=p
            p=a[pp]-1
            a[pp]='p'
    l=len(passed)
    print(passed[k]+1) if k<l else print(passed[(k-s)%(l-s)+s]+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
li = list(map(int,input().split()))
ans = [1]
nex = 1
f = [1]+[0]*(n-1)

for i in range(n):
    now = nex #今の場所
    nex = li[now-1] #テレポート先の場所
    #print(now,nex)
    if f[nex-1] == 1: #循環判定
        a = ans.index(nex) #開始点
        b = ans.index(now)-a+1 #循環周期
        break
    f[now-1] = 1
    ans.append(li[now-1])

#print(ans)
#print(f)
if k <= a:
    print(ans[k])
else:
    x = (k-a)%b
    print(ans[a+x])

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
tel = [int(i) for i in input().split()]
been = [0 for _ in range(n)]
been[0] = 1

next = tel[0]
loop = [1]
for i in range(n):
	loop.append(next)
	if been[next-1] == 1:
		break
	been[next-1] = 1
	next = tel[next-1]

loop_begin = loop.index(tel[next-1])
loop_num = i - loop_begin + 2
if loop_begin >= k:
	ans = loop[k]
else:
	loop_remain = (k-loop_begin) % loop_num
	ans = loop[loop_begin+loop_remain]

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
T = [1]
c = [0]*N

k = 1
st = 0
c[0] = 1
cc = 1
for i in range(N):
    k = A[k-1]
    if c[k-1] == 1:
        st = T.index(k)
        f = T[:st]
        r = T[st:]
        break

    T.append(k)
    c[k-1] += 1
    cc += 1

ff = len(f)
if K < ff:
    print(f[K])
else:
    print(r[(K-ff)%(cc-ff)])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(list)

p = 1
root = []

#s, e = 0, 0

for i in range(K):
    d[p].append(i)
    root.append(p)
    if len(d[p]) == 2:
        s = d[p][0]
        e = i
        n = (K - s) % (e - s)
        p = root[s + n]
        break
    p = A[p - 1]
#print(s, e)

#print(root)

#n = (K - s) % (e - s)
print(p)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

N, K = MII_split()
As = LII_split()

# search loop
visited = [False for _ in range(N)]
start = 1
visited[0] = True
loop = [start]
cur = start
for _ in range(N):
    nex = As[cur - 1]
    # print(cur)
    if not visited[nex - 1]:
        loop.append(nex)
        visited[nex - 1] = True
        cur = nex
    else:
        start_idx = loop.index(nex)
        before_num = start_idx
        befores = loop[:start_idx + 1]
        loop = loop[start_idx:]

        break

# print(loop)
# return
# print(befores)
# print(K)
# return
if K < before_num:
    print(befores[K])
else:
    K -= before_num
    idx = K % len(loop)
    print(loop[idx])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
G = [0]*N
src = list(map(int, input().split()))
for i,a in enumerate(src):
    G[i] = a-1
D = [-1]*N
D[0] = 0
cur = 0
dis = 0
while True:
    dis = dis+1
    cur = G[cur]
    if dis == K:
        print(cur+1)
        exit()
    if D[cur] == -1:
        D[cur] = dis
    else:
        cycle = dis - D[cur]
        K -= D[cur]
        target = K%cycle
        #print(cur, dis, D[cur], D, target)
        dis = 0
        if dis == target:
            print(cur+1)
            exit()
        while True:
            dis = dis+1
            cur = G[cur]
            if dis == target:
                print(cur+1)
                exit()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

# ループがあるか見つけ、ループのサイズを見つける
# ループしている場合、残りのｋをループで割ったあまりに置き換える
INF = 10**12
cnt = [-1 for _ in range(n)]
cur = 0
size = INF
idx = 0

for i in range(k):
    if cnt[cur] != -1:
        size = i - cnt[cur]
        idx = i
        for j in range((k - idx) % size):
            next_idx = a[cur] - 1
            cur = next_idx
        print(cur + 1)
        exit()
    cnt[cur] = i
    next_idx = a[cur] - 1
    cur = next_idx
print(cur + 1)

Submission status: Accepted

Solution code:
a = input().split(" ")
N = eval(a[0])
K = eval(a[1])
dic = {}
b = input().split(" ")
n_lst = [-1]
for i in range(1, N + 1):
    dic[i] = eval(b[i - 1])
    n_lst.append(-1)
ans = 1
lst = []
length = 0
while K > 0:
    if n_lst[ans] != -1:
        left = n_lst[ans]
        zq = length - left
        K = K % zq
        if K == 0:
            break
    else:
        n_lst[ans] = length
        length += 1
    ans = dic[ans]
    K -= 1

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
"""
閉路をmodを取って出力
閉路になっていない(回帰するなら)ならそこを出力
"""
n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))


visited = [-1]*n #modを取った時にそこにたどり着く
visited[0] = 0
now = 0
count = 1
mod = -1
lim = -1
while True:
    now = lst1[now] -1
    if visited[now] != -1: #閉路
        mod = count - visited[now]
        lim = visited[now]
        break
    visited[now] = count

    count += 1
    
if k <= lim:
    for i in range(n):
        if visited[i] == k:
            print(i+1)
            exit()
else:
    res = (k-lim)%mod
    for i in range(n):
        if visited[i]-lim == res:
            print(i+1)
            exit()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    def int_0(num):
        return int(num) - 1

    N, K = map(int, input().split())
    A = tuple(map(int_0, input().split()))
    
    # dfs
    INF = 10 ** 18
    visited = [False] * N
    dist = [INF] * N
    info  = {}
    def dfs(s):
        stack = deque()
        stack.append(s)
        visited[s] = True
        dist[s] = 0
        while stack:
            now = stack.pop()
            visited[now] = True
            nv = A[now]
            if visited[nv] == True:
                info["start"] = nv
                info["length"] = dist[now] - dist[nv] + 1
                info["f"] = dist[nv]
                break
            else:
                dist[nv] = dist[now] + 1
                stack.append(nv)
    dfs(0)

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

    K -= info["f"]
    K %= info["length"]

    now = info["start"]
    for _ in range(K):
        now = A[now]
    print(now+1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve(a, k):
    cycle = []
    visited = set()
    curr = 0
    while curr not in visited:
        visited.add(curr)
        cycle.append(curr)
        curr = a[curr]
    if k < len(visited):
        return cycle[k]
    cycle_start = cycle.index(curr)
    k -= cycle_start
    cycle = cycle[cycle_start:]
    return cycle[k % len(cycle)]


if __name__ == "__main__":
    n, k = map(int, input().split())
    a = [int(x) - 1 for x in input().split()]
    print(solve(a, k) + 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A, INF = 10**8):
    counts = [0 for i in range(N)]
    a = 1
    loop_init = -1
    loop_count = -1
    while True:
        counts[a-1] += 1
        if counts[a-1] == 2 and loop_count < 0:
            loop_count = 0
        elif counts[a-1] == 3:
            loop_count += 1
            break
        elif loop_count >= 0:
            loop_count += 1
        a = A[a-1]
    loop_init = sum([c == 1 for c in counts])

    a = 1
    if loop_init > K:
        for i in range(K):
            a = A[a-1]
    else:
        loop_k = (K - loop_init) % loop_count
        for i in range(loop_init + loop_k):
            a = A[a-1]
    return a


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
a = list(map(int,input().split()))
li = [[] for i in range(n)]
step = 0
li[0].append(step)
pos = 1
noLoop = True

while k > 0:
    pos = a[pos - 1]
    k -= 1
    if noLoop:
        step += 1
        li[pos - 1].append(step)
        if len(li[pos - 1]) == 2:
            loop = li[pos - 1][1] - li[pos - 1][0]
            k %= loop
            noLoop = False
print(pos)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

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

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

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

ls = [-1]*n

ls[0] = 0
s = 0
for i in range(n):
    if (i+1)==k:
        s = a[s] - 1
        print(s+1)
        exit()
    else:
        s = a[s] - 1
        if ls[s]<0:
            ls[s] = i + 1
            # print(ls)
        else:
            b = ls[s]
            w = (i+1) - b
            c = (k-b)%w
            g = ls.index(c+b) + 1
            # print(w,c,b)
            print(g)
            exit()

Submission status: Accepted

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

machi = 1
toutatu = []
pypyosoi = set()
while not machi in pypyosoi:
	toutatu.append(machi)
	pypyosoi.add(machi)
	machi = a[machi-1]

saigo = machi
num = toutatu.index(saigo)
unchi = toutatu[num:]
cnt = len(unchi)

if num > k:
	print(toutatu[k])
else:
	print(unchi[(k-num)%cnt])

#pypyが遅いのは自分のコードが悪いだけごめんねpypyちゃん

Submission status: Accepted

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

root = [1]

for i in range(n):
    t = a[root[i]-1]
    if (t == 0):
        break
    a[root[i]-1] = 0
    root.append(t)
x =  root.index(root[-1])
bef = root[0:x]
#print(bef)
loop = root[x:-1]
#print(loop)
#print(root)

if (k < len(bef)):
    print(bef[k])
else:
    p = ((k - len(bef)) % len(loop))
    #print(p)
    print(loop[p])

Submission status: Accepted

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

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

cnt, town = 0, 1
l, s = [], set()
while True:
    town = a[town - 1]
    cnt += 1
    if cnt == k:
        print(town)
        exit()
    if town in s:
        loop_start = town
        break
    l.append(town)
    s.add(town)


loop_cnt = l.index(loop_start)
loop = l[loop_cnt:]
loop_len = len(loop)
k -= loop_cnt
print(l[loop_cnt:][k%loop_len-1])

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import itertools
import math
n,k = ma()
A  = list(map(lambda x:int(x)-1,input().split()))
vis = [False]*n
cnt = [0]*n
vis[0] = 1
st = 0
c = 0
cyc = 0
l = 0
while True:
    c+=1
    nex = A[st]
    if c==k:
        print(nex+1)
        exit()
    if vis[nex]:
        cyc = cnt[st] - cnt[nex] +1
        l = cnt[st]+1
        break
    cnt[nex] = c
    vis[nex]=True
    st = nex
k = (k-l)%cyc
st = nex
while k>0:
    nex = A[st]
    st = nex
    k-=1
print(nex+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
graph = [set() for i in range(N)]
for i, a in enumerate(A):
    graph[i].add(a - 1)

queue = [0]
seen = {0}
path = []
while queue:
    new = []
    for cur in queue:
        path.append(cur)
        for nei in graph[cur]:
            if nei not in seen:
                new.append(nei)
                seen.add(nei)
    queue = new

if 0 in graph[path[-1]]:
    rest = K % len(path)
    print(path[rest] + 1)
else:
    if K < len(path):
        print(path[K] + 1)
    else:
        start = graph[path[-1]].pop()
        index = path.index(start)
        rest = (K - len(path[:index])) % len(path[index:])
        print(path[index:][rest] + 1)

Submission status: Accepted

Solution code:
import sys
l = sys.stdin.readline().strip()
N, K = map(int, l.split())
l = sys.stdin.readline().strip()
A = [0] + list(map(int, l.split())) 
visited = [-1] * (len(A)+1)

remain = K
crt = 1
entrance = -1
while remain > 0:
    remain -= 1
    # check visited
    if visited[crt] == -1:
        visited[crt] = K - remain
        crt = A[crt]
    else:
        entrance = crt
        crt = A[crt]
        break
#print(entrance, remain)

if entrance == -1:
    print(crt)
else:
    loop = (K-remain) - visited[entrance] 
 
    later = remain % loop
    for i in range(later):
        crt = A[crt]
    print(crt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, k = map(int, input().split())
a = list(map(int, input().split()))

length = [-1] * n
path = [-1, []]
route = []


def func(now, depth):
    global path, length, a, route
    route.append(now)
    if length[now] == -1:
        length[now] = depth
        func(a[now]-1, depth+1)
    else:
        path = [length[now], route[length[now]:depth]]


func(0, 0)

if (k < path[0]):
    print(route[k] + 1)
else:
    tmp = k - path[0]
    tmp %= len(path[1])
    print(path[1][tmp] + 1)

Submission status: Accepted

Solution code:
import sys
from _collections import deque
N,K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(len(A)):
    A[i] = A[i]-1
used = [0]*N
m = 0
c = 0
used[m] = 1

while(True):
    m = A[m]
    c += 1
    if c == K:
        print(m+1)
        sys.exit()
    if used[m] == 1:
        break
    else:
        used[m] = 1

loop = m
h = K-c
ans = deque([loop])
c = 0
p = loop
while(True):
    p = A[p]
    c += 1
    if p == loop:
        break
    ans.append(p)

print(ans[h%c]+1)

Submission status: Accepted

Solution code:
from collections import Counter

n, k = map(int, input().split())
a = list(map(int, input().split()))
check = [0] * n
# for i, val in enumerate(a):
#　１回でも行ったことのある場所へ行けば、ループになる

target = 0
for i in range(k):
    if (check[target] == 2):  #
        #print('A', i)
        count = Counter(check)
        num_2 = count[2]
        #print(num_2)
        temp = k - (i)
        mod = temp % num_2
        for j in range(mod):
            aaa = a[target]
            target = aaa - 1

        ans = target + 1
        break

    else:
        check[target] += 1
        aaa = a[target]
        target = aaa - 1

        ans = target + 1

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
teleps = list(map(int, input().split()))
teleps.insert(0, 0)
current = 1
routes = []
memory = set([])
roop_count = 0
for _ in range(K):
    # ループ検知する
    if current not in memory:
        memory.add(current)
    else:
        # ループ発見
        index = routes.index(current)
        roop_count = len(routes) - index
        di = (K - index) % roop_count
        current = routes[index+di]
        break
    routes.append(current)
    current = teleps[current]
print(current)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
s = 1
B = [0]*(10**6)
B[0] = 1
C = [0]*(10**6)
C[1] = 1 
for i in range(K):
    s -= 1
    s = A[s]
    B[i + 1] = s
    C[s] += 1
    if C[s] > 1:
        k = B.index(s)
        l = i + 1 - k
        s = 10**10
        break
if s < 10**10:
    print(s)
else:
    B1 = B[k:k+l]
    r = (K - k)%l
    print(B1[r])

Submission status: Accepted

Solution code:
def main():
    _, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    history = [1]
    # 場所: index
    history_dict = {1:0}
    last_city = -1
    for x in range(K):
        now = A[history[-1]-1]
        # print(now)
        if now in history_dict:
            last_city = now
            break
        history.append(now)
        history_dict[now] = x+1

    if last_city == -1:
        print(history[-1])
    
    else:
        index = history_dict[last_city]
        mod = (K - index) % (len(history) - index)
        # print(index, len(history) - index, mod)
        print(history[index + mod]) 

if __name__ == "__main__":
    main()

Submission status: Accepted

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

num = [0]*(N+1)
inv = []

p = 1
count = 1
while num[p] == 0:
    num[p] = count
    inv.append(p)
    p = A[p]
    count += 1

m = max(num)

###
#print(p)
#print(num)
#print(inv)
#print((K-(num[p]-1))%(m-(num[p]-1))+num[p])
###

if K >= num[p]:
    print(inv[(K-(num[p]-1))%(m-(num[p]-1))+num[p]-1])
else:
    print(inv[K])

Submission status: Accepted

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

path = [0]*N
a = 0

for j in range(N+1):
    count = j
    a = A[a]-1
    if path[a]!= 0:
        b = path[a]
        c = j+1-path[a]
        break
    else:
        path[a] = j+1

mod = (K-b)%c

if count > K:
    print(path.index(K)+1)
else:
    print(path.index(mod+b)+1)

Submission status: Accepted

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

def solve() :
  global K
  visited = [-1] * N
  visited[0] = 0

  cur = 0
  while True :
    nex = A[cur]
    if visited[cur] == K - 1 :
      return nex + 1
      
    if visited[nex] == -1 :
      visited[nex] = visited[cur] + 1
      cur = nex
    else :
      # 一回目
      i = visited[nex]
      # 二回目
      j = visited[cur] + 1
      K -= i
      K %= (j - i)
      cur = nex
      break
      
  while K > 0 :
    cur = A[cur]
    K -= 1
    
  return cur + 1
    
print(solve())

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,K = map(int,input().split())
A = list(map(int,input().split()))
if K <= 3 * N:
    cur = 1
    for i in range(K):
        cur = A[cur-1]
    print(cur)
else:
    d = defaultdict(int)
    cur = 1
    for i in range(3*N):
        cur = A[cur-1]
        d[cur] += 1
    if d[1] != 0:
        cur = 1
        for i in range(1,N+1):
            cur = A[cur-1]
            if cur == 1:
                f = i
        num = K % f
        if num == 0:
            print(1)
        else:
            cur = 1
            for i in range(num):
                cur = A[cur-1]
            print(cur)
    else:
        cnt = 0
        for i in range(1,N+1):
            if d[i] == 1:
                cnt += 1
        cur = 1
        for i in range(cnt+1):
            cur = A[cur-1]
        start = cur
        for i in range(1,N+1):
            cur = A[cur-1]
            if cur == start:
                f = i
                break
        K = K - cnt -1
        num = K % f
        if num == 0:
            print(start)
        else:
            cur = start
            for i in range(num):
                cur = A[cur-1]
            print(cur)

Submission status: Accepted

Solution code:
import sys;input=lambda:sys.stdin.readline().rstrip();aint=lambda:int(input());ints=lambda:list(map(int,input().split()))
import math;floor,ceil=lambda x:int(math.floor(x)),lambda x:int(math.ceil(x))
from functools import reduce;gcd=lambda*x:reduce(math.gcd,x);lcm=lambda*x:reduce(lambda x,y:(x*y)//gcd(x,y),x,1)
from collections import deque
import bisect
Yes=lambda b:print("Yes"if b else"No");YES=lambda b:print("YES"if b else"NO")
is_even=lambda x:True if x%2==0 else False

def main():
    n,k=ints()
    a=ints()
    passed=[]
    flg=0
    p=0
    while flg==0:
        if a[p] == 'passed':
            flg=1
            s=passed.index(p)
            break
        else:
            passed.append(p)
            pp=p
            p=a[pp]-1
            a[pp]='passed'
    l=len(passed)
    if k<l:
        print(passed[k]+1)
    else:
        print(passed[(k-s)%(l-s)+s]+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

vst = [False for i in range(N)]
plc = [0]

for i in range(N):
    mm = plc[-1]
    mm2 = A[mm]-1
    if vst[mm2]:
        break
    vst[mm] = True
    plc.append(A[mm]-1)

li = []
flg = False
for i in range(len(plc)):
    if plc[i]==mm2:
        flg = True

    if not(flg):
        continue

    li.append(plc[i])

# for i in A:
#     print(i-1," ",end="")


ans = (K-len(plc))%len(li)
if (K-len(plc)) >=0:
    print(li[ans]+1)
else:
    print(plc[K]+1)

Submission status: Accepted

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

F=[-1]*N
l=0
prev=0
while True:
  if F[prev]!=-1:
    break
  
  if l==K:
    print(prev+1);exit()
  F[prev]=l
  l+=1
  prev=A[prev]-1
  #print(l,prev)
l = (K-F[prev])%(l-F[prev])
#print(l)
for i in range(l):
  prev=A[prev]-1
print(prev+1)