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 = list(map(int, input().split()))
a = list(map(int, input().split()))
memo = []
memo_cir = []
visited = [False] * n
index = 0
flag = True
while flag:
    if visited[index]:
        flag = False
    else:
        memo.append(index)
        visited[index] = True
        index = a[index] - 1
flag = False
for i_ in memo:
    if i_ == index:
        flag = True
    if flag:
        memo_cir.append(i_)
if k + 1 >= (len(memo) - len(memo_cir)):
    k -= (len(memo) - len(memo_cir) - 1)
    print(memo_cir[(k % len(memo_cir)) - 1] + 1)
else:
    print(memo[k] + 1)

Submission status: Accepted

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

s = [True] * n
c = [1]
now = 0
while s[now]:
    s[now] = False
    now = a[now] - 1
    c.append(now+1)

start_cycle = c.index(c[-1])
loop = c[start_cycle:-1]
cycle = len(loop)

if k < start_cycle:
    print(c[k])
else:
    k -= start_cycle
    k %= cycle
    print(loop[k])

Submission status: Accepted

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

s = [False] * n
c = [1]
now = 0
while not s[now]:
    s[now] = True
    now = a[now] - 1
    c.append(now+1)

start_cycle = c.index(c[-1])
loop = c[start_cycle:-1]
cycle = len(loop)

if k < start_cycle:
    print(c[k])
else:
    k -= start_cycle
    k %= cycle
    print(loop[k])

Submission status: Accepted

Solution code:
from collections import defaultdict


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


N, K = inpl()
aa = inpl()

s = 1

route = [s]
ed = set([s])

for i in range(1, K + 1):
    s = aa[s - 1]
    if s in ed:
        Li = route.index(s)
        Ri = len(route)
        idx = Li + (K - Li) % (Ri - Li)
        print(route[idx])
        break
    else:
        route.append(s)
        ed.add(s)
        continue
else:
    print(s)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = list(map(int,input().split()))
s.insert(0,0)

visited = [0]*(n+1)
visited[1] = 1
q = [1]

def dp(town):
    if visited[town] == 1:
        ans = k%(len(q))
        print(q[ans])
        exit()
    else:
        visited[town] += 1
        q.append(town)

i = 1
next_town = s[1]
while True:
    if i == k:
        print(next_town)
        exit()
    if visited[next_town] == 1:
        break
    else:
        visited[next_town] += 1
        q.append(next_town)
        next_town = s[next_town]
        i += 1
    
index = q.index(next_town)
q = q[index:]
ans = (k-i)%len(q)
print(q[ans])

Submission status: Accepted

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

s = [-1] * n
c = [1]
t = 0
now = 0
while s[now] == -1:
    s[now] = t
    now = a[now] - 1
    c.append(now+1)
    t += 1

start_cycle = c.index(c[-1])
loop = c[start_cycle:-1]
cycle = len(loop)

if k < start_cycle:
    print(c[k])
else:
    k -= start_cycle
    k %= cycle
    print(loop[k])

Submission status: Accepted

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

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

if k < n:
    print(visited[k])
else:
    first = visited.index(visited[-1])
    loop = visited[::-1][1:].index(visited[-1])+1
    last = (k-first)%loop
    print(visited[first+last])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[int(i)-1 for i in input().split()]
p=0
visited=[0]*n
first=[]
roop=[]
while visited[p]!=2:#二回通っていたらやめる
    if visited[p]==0:#初めて通った
        first.append(p)
    else:#一回通った
        roop.append(p)
    visited[p]+=1#通った跡をつける
    p=a[p]#テレポート
if len(first)>k:#一回もループしていないのなら
    print(first[k]+1)#最初のk番目
else:
    print(roop[(k-(len(first)-len(roop)))%len(roop)]+1)#そうでなければkから一回目のループと二回目のループを引いて二回目のループの回数の余剰

Submission status: Accepted

Solution code:
import sys

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

visited = [False] * (N+1)
s = 1

while not visited[s]:
    visited[s] = True
    s = A[s]

a = 1

while a != s:
    K -= 1
    a = A[a]
    if K == 0: 
        print(a)
        sys.exit()

visited = [False] * (N+1)
length = 0
while not visited[s]:
    visited[s] = True
    s = A[s]
    length += 1
    
k = K % length
while k:
    s = A[s]
    k -= 1
    
print(s)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
 
n, k = map(int, input().split())
a = [int(item) - 1 for item in input().split()]
visited = [0] * n
 
v = 0
visited[0] = 1
pre = [0]
loop = []
start = False
while True:
    v = a[v]
    if visited[v] == 1:
        start = True
    if visited[v] == 2:
        break
    if not start:
        pre.append(v)
    else:
        loop.append(v)
    visited[v] += 1 
 
if k < len(pre):
    print(pre[k] + 1)
    exit()
k -= len(pre)
print(loop[k % len(loop)] + 1)

Submission status: Accepted

Solution code:
n,k = (int(x) for x in input().split())
town = [int(i) for i in input().split()]
warp  = [1]
checklist = [0]+[-1]*n
i = 0
j = 1
s = 0
while j<=n:
    warp.append(town[i])
    if checklist[town[i]-1]!=-1:
        s = checklist[town[i]-1]
        loop = warp[s:j]
        break
    checklist[town[i]-1] = j
    i = town[i]-1
    j += 1
if k>=s:
    m = len(loop)
    print(loop[(k-s)%m])
else:
    print(warp[k])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [x-1 for x in a]
nxt = [[x for _ in range(60)] for x in a]
for j in range(1, 60):
	for i in range(n):
		nxt[i][j] = nxt[nxt[i][j-1]][j-1]

cur = 0
for j in range(59, -1, -1):
	if (k>>j)&1:
		cur = nxt[cur][j]
print(cur+1)

Submission status: Accepted

Solution code:
import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=qb
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1


n,k = readInts()
a = readInts()

now = [1]
check = [0]*n
check[0] = 1
l = 1

while check[l-1]<2:
	l = a[l-1]
	check[l-1]+=1
	now.append(l)

zen = now.index(now[-1])
kou = len(now)-zen

if k<zen:
	print(now[k])
else:
	x = (k-zen)%(kou-1)
	print(now[zen:][x])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int,input().split()))
def inpm():
    return map(int,input().split())

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

a=[1] + inpl()
b=[-1] * (n+1); b[1] = 0
place = 1
turn = 0

while b[a[place]] == -1:
    place = a[place]
    turn += 1
    b[place] = turn
r = (k - turn) % (b[place] - b[a[place]] + 1)

if k < turn:
    print(b.index(k))
else:
    for _ in range(r):
        place = a[place]
    print(place)

Submission status: Accepted

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


lst = []
visit_now = 1
visit_list = [-1] * (n + 1)
cnt = 0

while visit_list[visit_now - 1] == -1:
    visit_list[visit_now - 1] = cnt
    lst.append(visit_now)
    visit_now = a[visit_now - 1]
    cnt += 1

start = visit_list[visit_now - 1]
loop_num = cnt - start

if k <= start:
    ans = lst[k]
else:
    k -= start
    k %= loop_num
    ans = lst[start + k]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
r=lambda : list(map(int,input().split()))#anonymous function used to take input
n,k=r()
l=r()
d=defaultdict(int) #taking dictionary of each length
d[1]=0
temp=[1]
t=1
loop=-1  
while True:
    t=l[t-1] #jumping based on the value at tth position in the arr
    if t in d: #if t is already in dictionary then we find the array
        loop=d[t] #just take the length of the array
        break    #now break the loop
    d[t]=len(temp)   #t key and value with the length of temp
    temp.append(t)
head=temp[:loop]
rloop=temp[loop:]
if k<loop:
    print(head[k])
else:
    print(rloop[(k-loop)%len(rloop)])

Submission status: Accepted

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    visited = [0] * (N+1)
    seq = []

    step = 0
    current = 1

    n1 = n2 = 0
    while(step<len(A)):
        #print(visited)
        seq.append(current)
        step += 1
        visited[current] = step
        next_pos = A[current-1]
        if visited[next_pos]>0:
            n1 = visited[next_pos]
            n2 = step - n1 + 1
            seq.append(next_pos)
            break
        current = next_pos

    #print(n1, n2)
    #print(n1-1, ((K-(n1-1))%n2))
    #print(seq)
    if n1+n2<=K:
        print(seq[n1-1+((K-(n1-1))%n2)])
    else:
        print(seq[K])

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

cnt = [-1 for _ in range(N + 1)]
cnt[1] = 0

p = A[1]
l = 1

while cnt[p] == -1:
    if l == K:
        print(p)
        exit()

    cnt[p] = l
    p = A[p]
    l += 1

lp = (l - cnt[p])
k = (K - cnt[p]) % lp + cnt[p]

for i, c in enumerate(cnt):
    if k == c:
        print(i)
        break

Submission status: Accepted

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

    # 訪れた頂点のメモ
    s = []
    # sの中のインデックスに対応, 訪れていない点は−１に対応
    order = [-1]*(n+1)
    c = 1 # 周期
    v = 1 # vertex, 1から始める
    while order[v] == -1:
        order[v] = len(s) 
        s.append(v) # 訪れた頂点の記録
        v = a[v-1] # 次の頂点へ


    l = order[v] # 例外部分の長さ
    c = len(s) - l
    if k < l :
        print(s[k])
    else:
        k -= l
        k %= c
        print(s[l+k])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
D = [1]
seen = [0]*n
seen[0] = 1
now = 0
while True:
    now = A[now] - 1
    D.append(now+1)
    if seen[now]:
        break
    seen[now] = 1
f = D.index(D[-1])
if k < f:
    print(D[k])
else:
    cycle = len(D) - f - 1
    k -= f
    print(D[f + k%(cycle)])

Submission status: Accepted

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

journey = [1]

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

end = n
start = n-1

while journey[start] != journey[end]:
    start -= 1

period = end - start
k %= period

while k < n:
    k += period

print(journey[k])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
visited = [0]
for _ in range(n):
    now = a[visited[-1]]-1
    visited.append(now)

if k < n:
    print(visited[k]+1)
else:
    p = visited.index(visited[-1])
    loop = visited[::-1][1:].index(visited[-1])+1
    x = (k-p-1)%loop
    print(visited[p+x+1]+1)

Submission status: Accepted

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

l = []
used = [0 for _ in range(n)]

c = 0
flag = True
while 1:
    if not flag:
        l.append(c)
    if used[c] == 1 and l:
        break
    if not flag:
        used[c] = 1
    c = a[c]
    flag = False

p = 0
length = len(l)
b = []
for i in range(length):
    if l[i] == l[-1]:
        b = l[:i]
        l = l[i:-1]
        p = i
        break


if len(b) >= k:
    print(b[k - 1]+1)
else:
    print(l[(k - p - 1) % len(l)] + 1)

Submission status: Accepted

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

c = 1
l = 0
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:
import sys
import os

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

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

    d=1
    keys=list(range(N))
    li={s:-1 for s in keys}
    li[0]=0

    roop=0
    pre_d=0
    for i in range(1,K+1):
        pre_d=d
        d=A[d-1]
        # print("i:"+str(i)+" "+str(pre_d)+"->"+str(d))
        if li[d-1]!=-1:
            roop=i-li[d-1]
            # print("detect_roop:"+str(i)+"~"+str(li[d-1]))
            break
        else:
            li[d-1]=i

    if roop!=0:
        k=1
        for j in range((K-li[d-1]-1)%roop+li[d-1]+1):
            k=A[k-1]
        print(k)
    else:
        print(d)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

ar=[-1 for i in range(n+1)]
p=1

go=0


for i in range(1,k+1):
    
    
    
    

    ar[p]=i-1
    p=a[p-1]
    
    if ar[p]>0:
        j=ar[p]
        amari=(k-i)%(i-j)
        
        go=1
        break

if go==1:
    p=ar.index(j+amari)
    
    


print(p)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    D = K.bit_length()
    to = [[0] * D for _ in range(N)]

    for i, a in enumerate(map(int, input().split())):
        to[i][0] = a - 1

    for j in range(D - 1):
        for i in range(N):
            to[i][j+1] = to[to[i][j]][j]

    v = 0
    for i in reversed(range(D)):
        if (K >> i) & 1:
            v = to[v][i]

    print(v + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
D = K.bit_length()
to = [[0] * D for _ in range(N)]

for i, a in enumerate(map(int, input().split())):
    to[i][0] = a - 1

for j in range(D - 1):
    for i in range(N):
        to[i][j+1] = to[to[i][j]][j]

v = 0
for i in reversed(range(D)):
    if (K >> i) & 1:
        v = to[v][i]

print(v + 1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
D = K.bit_length()
to = [[0] * D for _ in range(N)]

for i, a in enumerate(map(int, input().split())):
    to[i][0] = a - 1

for j in range(D - 1):
    for i in range(N):
        h = to[i][j]
        to[i][j+1] = to[h][j]

v = 0
for i in reversed(range(D)):
    if (K >> i) & 1:
        v = to[v][i]

print(v + 1)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = [0] + [*map(lambda x:int(x), input().split())]
index = [-1]*(N+1)
path = [1]
while index[path[-1]] < 0:
    index[path[-1]] = len(path)
    path += [A[path[-1]]]
one = index[path[-1]]
loops = len(path) - one
if K < one: print(path[K])
else: print(path[(K-one) % loops + one])

Submission status: Accepted

Solution code:
def d_teleporter():
    N, K = [int(i) for i in input().split()]
    A = [int(i) - 1 for i in input().split()]  # 0-origin

    current_city = 0
    visit_list, visit_dict = [current_city], {current_city: 1}
    for i in range(min(K, N)):  # N 回移動すればループはわかる
        current_city = A[current_city]
        if current_city in visit_dict:  # ループを検出した
            j = visit_list.index(current_city)  # ここからループ
            current_city = visit_list[j + (K - j) % (i - j + 1)]
            break
        else:
            visit_list.append(current_city)
            visit_dict[current_city] = current_city
    return current_city + 1

print(d_teleporter())

Submission status: Accepted

Solution code:

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

    visited = set()  # 探索済み
    path = []  # 探索順番
    now = 0
    while now not in visited:
        path.append(now)
        visited.add(now)
        now = A[now]

    s = path.index(now)
    r = len(path) - s

    if K < s:
        print(path[K] + 1)
    else:
        mod = (K - s) % r
        print(path[mod + s] + 1)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

visited = [0]
visitedSet = {0}
flag = False
loopStart = 0
loopCycle = 0
currentTown = 0

for i in range(n):
    currentTown = a[visited[-1]]-1
    if currentTown in visitedSet:
        flag = True
        loopStart = visited.index(currentTown)
        loopCycle = i + 1 - loopStart
        break
    if i == k - 1:
        print(currentTown+1)
        break

    visited.append(currentTown)
    visitedSet.add(currentTown)

if flag:
    print(visited[loopStart + (k - loopStart) % loopCycle]+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ls=list(map(int,input().split()))
check_ls=[0 for i in range(n)]
ps=[1]
nxt=1
while True:
    idx=nxt-1
    if check_ls[idx]==-1:
        break
    ps.append(ls[idx])
    nxt=ls[idx]
    check_ls[idx]=-1

loop_start_idx = ps.index(ps[-1])
loop_length=len(ps)-loop_start_idx-1
loop_ls=ps[loop_start_idx:-1]
if k<len(ps):
    print(ps[k])
else:
    idx=(k-loop_start_idx)%loop_length
    print(loop_ls[idx])

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt
import fractions
import collections
import itertools
import pprint
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
double=[[-1 for _ in range(N)] for _ in range(60)]

for i in range(N):
    double[0][i]=A[i]-1
#pprint.pprint(double)
for i in range(1,60):
    for j in range(N):
        bef=double[i-1][j]
        double[i][j]=double[i-1][bef]
        #pprint.pprint(double[:10])
        #input()
bit=[0]*60

for i in range(60):
    if (K>>i)&1:
        bit[i]=1
#print(double[:5],bit)
piv=0
for i in range(60):
    if bit[i]==1:
        piv=double[i][piv]
print(piv+1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [0] + list(map(int,input().split())) #1_indexed
tele = [1]
used = [False for i in range(n)]
while True:
    next_number = a[tele[len(tele)-1]]
    if not used[next_number-1]:
        tele.append(next_number)
        used[next_number-1] = True
    else:
        repeat = tele.index(next_number)
        tele_1 = tele[:repeat]
        tele_2 = tele[repeat:]
        break

if k < len(tele_1):
    print(tele_1[k])
else:
    k_new = (k-len(tele_1)+1) % len(tele_2)
    print(tele_2[k_new-1])

Submission status: Accepted

Solution code:
def d_teleporter():
    N, K = [int(i) for i in input().split()]
    A = [int(i) - 1 for i in input().split()]  # 0-origin

    visit_list, visit_dict = list(), dict()
    current_city = 0
    for i in range(min(K, N)):  # N 回移動すればループはわかる
        current_city = A[current_city]
        if current_city in visit_dict:  # ループを検出した
            j = visit_list.index(current_city)  # ここからループ
            current_city = visit_list[j + (K - j - 1) % (i - j)]
            return current_city + 1
        else:
            visit_list.append(current_city)
            visit_dict[current_city] = current_city
    return current_city + 1

print(d_teleporter())

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

rec=[-1]*n
turn=0
current=0

while True:
    if k<=0:
        print(current+1)
        break
    if rec[current]==-1:
        rec[current]=turn
        turn+=1
        current=a[current]
        k-=1
    else:
        loop=turn-rec[current]
        k%=loop
        rec=[-1]*n

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
if a[0]==0:print(1);exit()
c=dict()
visited=[False]*N
visited[0]=True
c[0]=0
cnt=0
dap=0
n=0
b=[0]
while True:
    n=a[n]
    if visited[n]:
        dap=c[n] 
        break
    visited[n]=True
    b.append(n)
    cnt+=1
    c[n]=cnt
l=len(c)
if k<dap:
    print(b[k]+1)
else:
    print(b[(k-dap)%(l-dap)+dap]+1)

Submission status: Accepted

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

table = [[0] * (n + 1) for _ in range(71)]

table[0] = list(map(int, input().split()))
table[0].insert(0, 0)

for i in range(70):
    for j in range(1, n + 1):
        table[i + 1][j] = table[i][table[i][j]]

v = 1

for i in range(70, -1, -1):
    if k >= (1 << i):
        v = table[i][v]
        k -= 1 << i

print(v)

Submission status: Accepted

Solution code:
import sys

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

visit = [-1] * n   #到達しているかどうかを管理

D = [1]  # 循環するもののindexを格納

tmp = A[0]  #初期位置
ct = 1

while visit[tmp - 1] == -1:
    D.append(tmp)
    visit[tmp - 1] = ct  #到達済に変更
    if k == ct:
        print(tmp)
        sys.exit()
    ct += 1
    tmp = A[tmp - 1]

#循環している場合の残りの処理
k -= visit[tmp - 1]
k %= (ct - visit[tmp - 1])
print(D[visit[tmp - 1] + k])

Submission status: Accepted

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

visit = [-1] * n   #到達しているかどうかを管理

D = [1]  # 循環するもののindexを格納

tmp = A[0]  #初期位置
ct = 1

while visit[tmp - 1] == -1:
    D.append(tmp)
    visit[tmp - 1] = ct  #到達済に変更
    if k == ct:
        print(tmp)
        exit()
    ct += 1
    tmp = A[tmp - 1]

#循環している場合の残りの処理
k -= visit[tmp - 1]
k %= (ct - visit[tmp - 1])
print(D[visit[tmp - 1] + k])

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))

def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,K = MI()
A = [0]+LI()
ans_l = []
next = 1
done = [0]*(N+1)
while done[next]==0:
    ans_l.append(next)
    done[next]=1
    next = A[next]
idx = ans_l.index(next)
c = len(ans_l)-idx
if K<idx:
    print(ans_l[K])
else:
    ans_idx = (K-idx)%c+idx
    print(ans_l[ans_idx])

Submission status: Accepted

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

    # ループしているところを見つける
    path = [1]
    dic = [0] * n
    dic[0] = 1
    current = 0
    looping = False
    loop_st = -1
    loop_ed = -1
    for i in range(n):
        _next = a[current]
        if dic[_next-1] == 1:
            loop_st = path.index(_next)
            loop_ed = len(path)
            looping = True
            break
        dic[_next-1] = 1
        # if _next in path:
        #     loop_st = path.index(_next)
        #     loop_ed = len(path)
        #     looping = True
        #     break
        path.append(_next)
        current = _next-1

    if looping:
        if loop_ed - 1 >= k:
            print(path[k])
        else:
            len_loop = loop_ed - loop_st
            z = (k - loop_st) % len_loop
            print(path[loop_st + z])
    else:
        print(path[k])


main()

Submission status: Accepted

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

root = [1]
setroot = set(root)

for i in range(N):
    if A[root[-1]-1] in setroot:
        start = root.index(A[root[-1]-1])
        break
    setroot.add(A[root[-1]-1])
    root.append(A[root[-1]-1])

roop = root[start:]

if K <= start:
    print(root[K])
else:
    print(root[(K-start)%len(roop)+start])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = [-1] * n
f[0] = 0
s1, s2, g1, g2 = 0, 0, 0, 0
j = a[0] - 1
jpre = 0
c = 1
i = 0
while True:
    if i >= k:
        s1, s2 = f[jpre], jpre
        g1, g2 = 0, 0
        break
    if f[j] != -1:
        s1, s2 = f[jpre], jpre
        g1, g2 = f[j], j
        break
    else:
        f[j] = c
        c += 1
        jpre = j
        j = a[j] - 1
    i += 1
ans = (k - g1) % (s1 - g1 + 1) + f[g2]
for i in range(n):
    if f[i] == ans:
        print(i + 1)
        break

Submission status: Accepted

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

s=1
q=[0]*n
q[0]=1
r=[1]
for i in range(k):
  s=l[s-1]
  if q[s-1]==0:
    q[s-1]+=1
    r.append(s)
    if i==k-1:
      print(s)
  else:
    x=r.index(s)
    mod=len(r)-x
    t=(k-x)%mod
    print(r[x+t])
    break

Submission status: Accepted

Solution code:
from collections import deque

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

loop = []
visited = set()
s = set([1])
loop_creating = False
last = 1

while True:
  if loop_creating and len(visited) == 0:
    break
  
  if k == len(s) - 1:
    print(last)
    exit(0)

  nex = a[last - 1]

  if nex in visited:
    visited.remove(nex)
    loop.append(nex)
    loop_creating = True
  elif nex in s:
    visited.add(nex)
  else:
    s.add(nex)

  last = nex

rem = k - len(s)
print(loop[rem % len(loop)])

Submission status: Accepted

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

def main():
    N, K = map(int, readline().rstrip().split())
    A = list(map(int, readline().rstrip().split()))
    if K <= N:
        pre = 1
        for _ in range(K):
            pre = A[pre-1]
        print(pre)
        return

    pre = 1
    visited_set = set([1])
    visited = [1]
    for i in range(N):
        pre = A[pre-1]
        if pre in visited_set:
            break
        visited_set.add(pre)
        visited.append(pre)
    
    loop_start = visited.index(pre)
    loop = i - loop_start + 1

    num_loop = (K - loop_start) // loop
    now = loop_start + num_loop * loop
    for i in range(now+1, K+1):
        pre = A[pre-1]
    
    print(pre)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    N, K = map(int, readline().rstrip().split())
    d = list(map(int, readline().rstrip().split()))
    # d = {i+1: a for i, a in enumerate(A)}
    if K <= N:
        pre = 1
        for _ in range(K):
            pre = d[pre-1]
        print(pre)
        return

    pre = 1
    visited = set([1])
    visited_l = [1]
    for i in range(N):
        pre = d[pre-1]
        if pre in visited:
            break
        visited.add(pre)
        visited_l.append(pre)
    
    loop_start = visited_l.index(pre)
    loop = i - loop_start + 1

    num_loop = (K - loop_start) // loop
    now = loop_start + num_loop * loop
    for i in range(now+1, K+1):
        pre = d[pre-1]
    
    print(pre)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

is_visited = [-1] * (N + 1)  # 未訪の時 -1, 既訪のとき何番目に訪れたか
p = 1
L = 0  # 周期
T = []

while is_visited[p] == -1:
    is_visited[p] = len(T)
    T.append(p)
    p = A[p]
L = len(T) - is_visited[p]
start_loop = is_visited[p]
# print(T, is_visited, p)

if K < start_loop:
    print(T[K])
else:
    K -= start_loop
    K %= L
    print(T[K + start_loop])

Submission status: Accepted

Solution code:
import sys
# sys.stdin = open('input.txt')

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

s = []  #　頂点を訪れた順番に持つ数列
ord = [-1 for i in range(n+1)]  # 訪問済みの頂点の index. 未訪問のときは -1
c = 1  # 周期
l = 0  # 例外部分の長さ

v = 1  # 現在の頂点
while ord[v] == -1:
    ord[v] = len(s)
    s.append(v)
    v = a[v-1]

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

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

L = [0 for i in range(N+1)]
L[1] = 1
x = 1
t = 1
while K>0:
  t += 1
  K -= 1
  x = A[x-1]
  if L[x] != 0:
    p = t - L[x]
    K %= p
    break
  else:
    L[x] = t
    
while K>0:
  x = A[x-1]
  K -= 1
print(x)