Problem:


Score: 400 points

Problem Statement

The Kingdom of Takahashi has N towns, numbered 1 through N.

There is one teleporter in each town. The teleporter in Town i (1 \leq i \leq N) sends you to Town A_i.

Takahashi, the king, loves the positive integer K. The selfish king wonders what town he will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Help the king by writing a program that answers this question.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

1 \leq K \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the integer representing the town the king will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Sample Input 1

4 5
3 2 4 1

Sample Output 1

4

If we start at Town 1 and use the teleporter 5 times, our travel will be as follows: 1 \to 3 \to 4 \to 1 \to 3 \to 4.

Sample Input 2

6 727202214173249351
6 5 2 5 3 2

Sample Output 2

2



Sample input:
4 5
3 2 4 1


Sample output:
4

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
As = list(map(int, input().split()))
tl = [0]
ts = {0}

t = 0
for i in range(N):
    t = As[t]-1
    if t in ts:
        break
    else:
        tl.append(t)
        ts.add(t)

d = tl.index(t)
p = i - d + 1

if K > d:
    idx = (K - d) % p + d
else:
    idx = K

print(tl[idx]+1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
 
t = 1
tl = [1]
ts = {1}
for i in range(len(a)):
 
    t = a[t-1]
    if t in ts:
        break
    else:
        tl.append(t)
        ts.add(t)
 
tl2 = tl[tl.index(t):len(tl)]
 
 
if k < len(tl):
    ans = tl[k]
else:
    k = k - (len(tl) - len(tl2))
    j = k % len(tl2)
    ans = tl2[j]
 
print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    
    N2=(K-1).bit_length()+1
    A=[[0]*N for _ in range(N2)]
    A[0]=LI()
    
    for i in range(N):
        A[0][i]-=1
        
    for i in range(N2-1):
        for j in range(N):
            A[i+1][j]=A[i][A[i][j]]
            
    now=0
    for i in range(N2):
        if (K>>i)&1:
            now=A[i][now]
            
    print(now+1)
        
 
    

main()

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
A = np.zeros(N+1, dtype = np.int)
A[1:] = list(map(int, input().split()))

machis = {1}

now_machi = 1
count = 0

while True:
    next_machi = A[now_machi]
    count += 1
    if next_machi in machis:
        point = next_machi
        break
    machis.add(next_machi)
    now_machi = next_machi

now_machi = point
count2 = 0
while True:
    count2 += 1
    next_machi = A[now_machi]
    if next_machi == point:
        break
    now_machi = next_machi

if K - count > 0:
    times = (K - count) % count2
    now_machi = point
    for t in range(times):
        next_machi = A[now_machi]
        now_machi = next_machi
else:
    now_machi = 1
    for k in range(K):
        next_machi = A[now_machi]
        now_machi = next_machi

print(now_machi)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
now = 1
while K > 0:
    if K&1:
        now = A[now]
    A = [A[i] for i in A]
    K = K >> 1

print(now)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
now = 1
while K > 0:
    if K&1:
        now = A[now]
    a = [A[i] for i in A]
    A = a
    K = K >> 1

print(now)

Submission status: Accepted

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

t = 1
tl = [1]
ts = {1}
for i in range(len(a)):

    t = a[t-1]
    if t in ts:
        break
    else:
        tl.append(t)
        ts.add(t)

tl2 = tl[tl.index(t):len(tl)]


if k < len(tl):
    ans = tl[k]
else:
    k = k - (len(tl) - len(tl2))
    j = k % len(tl2)
    ans = tl2[j]

print(ans)

Submission status: Accepted

Solution code:
class solver :
	def __init__(self) :
		self.n, self.k = map(int, input().split())
		self.initVariables()
		self.a = [int(i) - 1 for i in input().split()]
	
	def initVariables(self) :
		self.vis = [False] * self.n
 
	def solve(self) :
		cur, tot = 0, 0
		travelled = list()
		while tot < self.k and not self.vis[cur] :
			self.vis[cur] = True
			travelled.append(cur)
			cur = self.a[cur]
			tot += 1
		if tot == self.k :
			return cur + 1
		cycle = list()
		for i in travelled :
			if i == cur or len(cycle) > 0:
				cycle.append(i)
		return cycle[(self.k - tot)  % len(cycle)] + 1

print(solver().solve())

Submission status: Accepted

Solution code:
from sys import stdin


def get_result(data):
    N, K = data[0]
    A = data[1]
    trans_num = [0] * N
    curr_pos = 1
    arrival_pos = set()
    for i in range(N):
        trans_num[curr_pos-1] = i
        arrival_pos.add(curr_pos)

        # see next
        next_pos = A[curr_pos-1]
        if next_pos in arrival_pos:
            loop_start = trans_num[next_pos-1]
            loop_trans_num = i + 1 - loop_start
            break

        # update
        curr_pos = next_pos

    # K が loop 開始より小さい可能性を忘れていた
    loop = K if (K - loop_start) < 0 else \
        loop_start + (K - loop_start) % loop_trans_num
    curr_pos = 1
    for _ in range(loop):
        next_pos = A[curr_pos-1]
        curr_pos = next_pos
    return next_pos


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

Submission status: Accepted

Solution code:
from sys import stdin


def get_result(data):
    N, K = data[0]
    A = data[1]
    trans_num = [0] * N
    curr_pos = 1
    arrival_pos = set()
    for i in range(N):
        trans_num[curr_pos-1] = i
        arrival_pos.add(curr_pos)

        # see next
        next_pos = A[curr_pos-1]
        if next_pos in arrival_pos:
            loop_start = trans_num[next_pos-1]
            loop_trans_num = i + 1 - loop_start
            break

        # update
        curr_pos = next_pos

    loop = 0
    # K が loop 開始より小さい可能性を忘れていた
    if (K - loop_start) > 0:
        loop = loop_start + (K - loop_start) % loop_trans_num
    else:
        loop = K
    curr_pos = 1
    for _ in range(loop):
        next_pos = A[curr_pos-1]
        curr_pos = next_pos
    return next_pos


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(lambda x:int(x)-1,input().split()))
ii=0
array=[-1]*n
for i in range(k):
    if array[ii]>=0:
        r=i-array[ii]
        k-=array[ii]
        m=k%r
        print(array.index(m+array[ii])+1)

        exit()
    array[ii]=i
    ii=a[ii]
else:
    print(ii+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
tel = list(map(int, input().split()))
pos = tel[0]
ls = [pos]
for i in range(len(tel)*2):
    pos = tel[pos - 1]
    ls.append(pos)
if k < len(tel) * 2:
    print(ls[k - 1])
else:
    patarn = ls[-len(set(ls[-len(tel):])):]
    destination = patarn[((k-len(ls)) % len(patarn)) - 1]
    print(destination)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
rd = [-1 for _ in range(N)]
rd[0] = 1

def nomal_loop():
    now_town = 1
    for _ in range(K):
        now_town = A[now_town-1]
    print(now_town)

    return 0

def else_loop():
    next_town = A[0]
    count = 1
    K_count = K
    while(1):
        count +=1
        K_count -= 1
        if rd[next_town-1] == -1:
            rd[next_town-1] = count
            next_town = A[next_town-1]
        else:
            warukazu = count - rd[next_town-1]
            result = (K_count+warukazu) % warukazu
            for _ in range(result):
                next_town = A[next_town-1]
            print(next_town)
            break
    return 0

if N > K:
    nomal_loop()
else:
    else_loop()

Submission status: Accepted

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


def main() -> None:
    N, K = rmi()
    A = rmi()
    route = []
    visited = [False] * N
    current = 1
    for n in range(N):
        route.append(current)
        if not visited[current - 1]:
            visited[current - 1] = True
            current = A[current - 1]
        else:
            break
    dup = route[-1]
    dup_index = route.index(dup)
    roop_range = len(route) - dup_index - 1
    if K < dup_index:
        w(route[K])
    else:
        w(route[dup_index:][(K - dup_index) % roop_range])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 9)
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = [0]+list(map(int,input().split()))
visited = [False for _ in range(n+1)]
pos = 1
x = []
flg = False
for i in range(k):
    if visited[pos] == False:
        x.append(pos)
        visited[pos] = True
        pos = A[pos]
    else:
        flg = True
        pre = x.index(pos)
        loop = x[pre:]
        break
if not flg:
    print(pos)
else:
    print(loop[(k-pre)%len(loop)])

Submission status: Accepted

Solution code:
# D - Teleporter
def main():
    N, K, *A = map(int, open(0).read().split())
    A = [0] + A
    last_visit = [-1] * (N + 1)
    last_visit[1] = 0
    cur_pos, i = 1, 1

    while True:
        nxt_pos = A[cur_pos]

        if i == K:
            print(nxt_pos)
            break
        elif (j := last_visit[nxt_pos]) != -1:  # detect a loop
            print(last_visit.index(j + (K - i) % (i - j)))
            break

        cur_pos = nxt_pos
        last_visit[cur_pos] = i
        i += 1


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = [0]+list(map(int,input().split()))
visited = [False for _ in range(n+1)]
pos = 1
x = []
flg = False
for i in range(k):
    if visited[pos] == False:
        x.append(pos)
        visited[pos] = True
        pos = A[pos]
    else:
        flg = True
        pre = x.index(pos)
        loop = x[pre:]
        break
if not flg:
    print(pos)
else:
    print(loop[(k-pre)%len(loop)])

Submission status: Accepted

Solution code:
# D - Teleporter
def main():
    N, K, *A = map(int, open(0).read().split())
    A = [0] + A
    cur_pos = 1
    last_visit = [-1] * (N + 1)
    last_visit[1] = 0
    
    for i in range(1, K + 1):
        nxt_pos = A[cur_pos]
        if (j := last_visit[nxt_pos]) != -1:
            print(last_visit.index(j + (K - i) % (i - j)))
            return
        cur_pos = nxt_pos
        last_visit[cur_pos] = i
    
    print(cur_pos)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [False for _ in range(n+1)]
B[1] = True
C = [1]

for i in range(1,n):
    C.append(A[C[-1]])
    #print(C)
    B[C[-1]] = True
    if B[A[C[-1]]] == True:
        C.append(A[C[-1]])
        break

num = i + 1
s = C.index(C[-1])
N = num - s

if k < s:
    print(C[k])
else:
    C = C[s:-1]
    #print(C)
    print(C[(k-s)%N])

Submission status: Accepted

Solution code:
def main():
    N, K, *A = map(int, open(0).read().split())
    A = [0] + A
    cur_pos = 1
    last_visit = [-1] * (N + 1)
    last_visit[cur_pos] = 0
    for i in range(1, K + 1):
        nxt_pos = A[cur_pos]
        if cur_pos == nxt_pos:
            print(nxt_pos)
            return 
        elif (j := last_visit[nxt_pos]) != -1:
            print(last_visit.index((K - j) % (i - j) + j))
            return 
        else:
            last_visit[nxt_pos] = last_visit[cur_pos] + 1
            cur_pos = nxt_pos
    print(cur_pos)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, K, *A = map(int, open(0).read().split())
    A = [0] + A
    cur = 1
    visited = [-1] * (N + 1)
    visited[cur] = 0
    for i in range(1, K + 1):
        next = A[cur]
        if cur == next:
            print(next)
            return
        elif (j := visited[next]) != -1:
            print(visited.index((K - j) % (i - j) + j))
            break
        else:
            visited[next] = visited[cur] + 1
            cur = next
    else:
        print(next)
        return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
  n,k = [int(x) for x in input().split()]
  a = [int(x)-1 for x in input().split()]
  
  visited_at = [-1] * n
  visited_at[0] = 0
  x = 0
  step = 0
  warped = False
  while k > 0:
    #print("remain", k, "step", step, "at", x+1)
#    if k <= 1:
#      break
    y = a[x]
    step += 1
    k -= 1
    if not warped and visited_at[y] >= 0:
      cycle = step - visited_at[y]
      #print("cycle", cycle)
      step += int(k / cycle)
      k = k % cycle
      x = y
      warped = True
    else:
      visited_at[y] = step
      x = y
  print(x+1)
main()

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
import sys
sys.setrecursionlimit(10**6)
#template
N,K = inputlist()
A = inputlist()
seen = [False]*(N+1)
dic = {n:0 for n in range(1,N+1)}
for i in range(N):
    dic[i+1] = A[i]

def search(i,count):
    seen[i] = True
    next_i = dic[i]
    if seen[next_i]:
        count+=1
        return [next_i,count]
    count+=1
    return search(next_i,count)
key,count_sum = search(1,0)

def find(i,count):
    if i == key:
        return count
    count+=1
    return find(dic[i],count)

tmp = find(1,0)
if K < count_sum:
    ans = 1
    for i in range(K):
        ans = dic[ans]
    print(ans)
    exit()

d = count_sum-tmp
Ka = K-tmp

mod = Ka % d

loop = []
loop.append(key)
def dfs(i):
    next_i = dic[i]
    if next_i == key:
        return False
    loop.append(next_i)
    return dfs(next_i)
dfs(key)

print(loop[mod])

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
def main():
    N, K = map(int, input().split())
    A = [(int(i) - 1) for i in input().split()]
    d = []
    for i in range(N):
        d.append(-1)
    d[0] = 0
    now = 0
    cycle = 0
    ans = -1
    a = 0
    flag = True
    while K > 0:
        if flag:
            if d[A[now]] == -1:
                d[A[now]] = d[now] + 1
            else:
                cycle = (d[now] + 1) - d[A[now]]
                K %= cycle
                flag = False
                if K == 0:
                    break
        K -= 1
        now = A[now]
    print(now + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

idx = a[0]
hist = [1]
passed = [0] * n
flag = 0
for i, _ in enumerate(range(k), start=1):
    if passed[idx-1] == 1:
        hist.append(idx)
        passed[idx-1] = 1
        flag = 1
        break
    hist.append(idx)
    passed[idx-1] = 1
    idx = a[idx-1]
    
    
if flag:
    l_start, l_end = hist.index(idx), i
    surplus = (k - l_start) % (l_end - l_start)
    print(hist[l_start + surplus])
else:
    print(hist[-1])

Submission status: Accepted

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

i = 0
aa = 0
visited = {}
for i in range(k):
    aa = a[aa] - 1
    if aa in visited:
        s, e = visited[aa], i
        loop = e - s
        k = s + (((k-1) - s) % loop)
        print(list(visited.keys())[k] + 1)
        exit(0)
    visited[aa] = i

print(aa+1)

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
a = [int(x) for x in input().split()]
s = [-1]*n
num = k
loc = 1

while(num >= 1):
    loc = a[loc-1]
    num -= 1
    if(s[loc-1] == -1):
        s[loc-1] = num
    else:
        num = num%(s[loc-1] - num)
        while(num >= 1):
            loc = a[loc-1]
            num -= 1
        break
print(loc)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[2*k]*n
while k:n=1-a[-n];d[n]=k=~-k%(d[n]+1-k)
print(1-n)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[2*k]*n
while k:n=-a[-n]+1;d[n]=k=~-k%(d[n]+1-k)
print(1-n)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[2*k]*n
s=0
while k:s=a[s]-1;d[s]=k=~-k%(d[s]+1-k)
print(s+1)

Submission status: Accepted

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

NN = [-1] * N
NN[0] = 0

i = 0
num = 0

while True:
    num += 1
    i = A[i] - 1
    if NN[i] != -1:
        n1 = NN[i]
        break
    NN[i] = num

n_ = num - n1

if K > n1:
    K -= n1
    t = NN.index(n1 + K % n_) + 1
    print(t)
else:
    t = NN.index(K) + 1
    print(t)

Submission status: Accepted

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

def solve(N, K, A):
    result = 0
    cs = [-1] * N
    rs = []
    i = 0
    while i < K:
        if cs[result] != -1:
            l = i - cs[result]
            m = (K - (i + (K - i) // l * l)) 
            result = rs[-l + m]
            break
        cs[result] = i
        rs.append(result)
        result = A[result] - 1
        i += 1

    return result + 1

print(solve(N, K, A))

Submission status: Accepted

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

now = 0
route = []
seen = set()
while not now in seen:
    route.append(now)
    seen.add(now)
    now = A[now]

loop_start = route.index(now)
loop_size = len(route) - loop_start

n_for_loop = min(K, loop_start)
n_in_loop = (K - n_for_loop) % loop_size

print(route[n_for_loop + n_in_loop] + 1)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[0]+[-1]*n
s=0
for i in range(k):
  s=a[s]-1
  if(j:=d[s])>-1:
    exec((k-j)%(i+1-j)*'s=a[s]-1;')
    exit(print(s+1))
  d[s]=i+1
print(s+1)

Submission status: Accepted

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

def main():
    N,K = map(int, readline().split())
    A = [int(i) - 1 for i in readline().split()]

    p = 0
    while K:
        if K & 1:
            p = A[p]
        A = [A[a] for a in A]
        K >>= 1
    
    print(p + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

a=[]

for i in range(N):
    a.append(-1)
#print(a)
b=1
for i in range(N):
    if a[b-1]==-1:
        a[b-1]=i+1
        b=List[b-1]
        
    else:
        c=i
        break
#print(a)
#print(b,c)

num=a[b-1]-1
T=c-num
#print(T)
e=1
if K<num:
    for i in range(K):
        e=List[e-1]
    print(e)
else:
    qw=(K-num)%T
    List_new=[]
    for i in range(T):
        List_new.append(b)
        b=List[b-1]
    print(List_new[qw])

Submission status: Accepted

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

s=[]
d=[-1]*(n+1)

v=1
while(d[v]==-1):
    d[v]=len(s)
    s.append(v)
    v=a[v-1]
c=len(s)-d[v]
l=d[v]

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

Submission status: Accepted

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

for index, item in enumerate(a):
    a[index] -= 1

mp = dict()
now = 0
step = 0
rec = []
while not now in mp:
    mp[now] = step
    rec.append(now)
    step += 1
    now = a[now]

path = rec[mp[now]:step]

if k < mp[now]:
    print(rec[k] + 1)
else:
    k = (k - mp[now]) % len(path)
    print(path[k] + 1)

Submission status: Accepted

Solution code:
def function():
    _N,K = map(int, input().split())
    teleportes = list(map(int, input().split()))

    # ループを見つける
    i,count = 0,0
    visited = [-1] * len(teleportes) # 訪れた街にチェック
    while True :
        if visited[i] == -1: # 最初に訪れた
            visited[i] = count # 何番目に訪れたかを記録
            i = teleportes[i] - 1
            count += 1
        else:
            loops = count - visited[i] # 以前訪れてから何回旅したか
            break
    
    if K <= visited[i]:
        i = 0
    else:
        K -= visited[i]
        K %= loops
    for _k in range(K):
        i = teleportes[i] - 1
    print(i+1)

if __name__ == '__main__':
    function()

Submission status: Accepted

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

    path = [1]
    for _ in range(n-1):
        path.append(a[path[-1]-1])

    if k > n:
        start = path.index(path[-1])
        index = (k - start) % (len(path) - start - 1) + start
        t = path[index]
    else:
        t = path[k]
    return print(t)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    A=tuple(map(int1,input().split()))
    doubling=[[A[i]]*(K.bit_length()+1) for i in range(N)]
    for k in range(K.bit_length()):
        for i in range(N):
            doubling[i][k+1]=doubling[doubling[i][k]][k]
    ans=0
    k=0
    while K>0:
        if K&1:
            ans=doubling[ans][k]
        K>>=1
        k+=1
    print(ans+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())         # n=町の個数 , k=テレポート回数
a_list = list(map(int,input().split()))     # 各町のテレポート先リスト
dum = a_list[0]                        # dum=次のテレポート先
k = k - 1                              # テレポート回数をデクリメント
ans_list = [1]                         # 訪れた町を ans_list に格納
ok = True
check_list = n*[0]
check_list[0] = 1
for i in range(k+1):
    if ok and check_list[dum-1] == 1:
        #print(dum,111)
        ind = ans_list.index(dum)
        loop = ans_list[ind:]
        len_loop = len(loop)
        k = k % len_loop
        ans_list = []
        ok = False
    else:
        check_list[dum-1] = 1

    if k == 0:
        print(int(dum))
        break
    ans_list.append(dum)
    dum = a_list[int(dum)-1]
    k = k - 1

Submission status: Accepted

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

path = [1]
checked = [False] * N
detect_loop = False

current_pos = 1
while not detect_loop:
    current_pos = A[current_pos - 1]

    if checked[current_pos - 1]:
        detect_loop = True

    path.append(current_pos)
    checked[current_pos - 1] = True

loop = path[(idx := path.index(current_pos)):-1]
straight = path[:idx]

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

Submission status: Accepted

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

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

c = 1
l = 0

i = 1

while order[i] == -1:
    order[i] = len(s)
    s.append(i)
    i = a[i-1]

c = len(s) - order[i]
l = order[i]

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

Submission status: Accepted

Solution code:
n,k = map(int ,input().split())
A = tuple(map(int, input().split()))
seen = [-1]*n
tmp = 0
count = 0

while True:
    tmp = A[tmp]-1
    count +=1
    if seen[tmp] != -1:
        seennum = seen.count(1)

        tm = tmp
        se = [-1]*n
        roopmem = []
        while True:

            if se[tm] != -1:
                roop = se.count(1)
                break
            else:
                roopmem.append(tm)
                se[tm] = 1
                tm = A[tm] - 1

        break
    else:
        seen[tmp] = 1

if k<=n:
    no = 0
    for i in range(k):
        no = A[no]-1
    print(no+1)
else:
    tmp = k-seennum
    tmp %= roop
    print(roopmem[tmp-1]+1)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,K = map(int, readline().split())
A = np.int32(read().split())

A -= 1

def mult(A, B):
  return B[A]

def power(A, n):
  if not n:
    return np.arange(N)
  B = power(A, n//2)
  B = mult(B,B)
  return mult(A,B) if n & 1 else B

print(power(A, K)[0] + 1)

Submission status: Accepted

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

path = [1]
chk = {1}
idx = 1
loop_s = 1
loop_e = n

for i in range(1, n + 1):
    if a[idx] not in chk:
        idx = a[idx]
        path.append(idx)
        chk.add(idx)
    else:
        loop_s = path.index(a[idx])
        loop_e = i
        break

if k <= loop_s:
    print(path[k])
else:
    print(path[loop_s + (k - loop_s) % (loop_e - loop_s)])

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    A=LI()
    for i in range(N):
        A[i]-=1
    used=[0]*N
    used[0]=1
    
    now=0
    nxt=0
    cnt=1
    flag=1
    while True:
        nxt=A[now]
        if used[nxt]==0:
            used[nxt]=cnt+1
        else:
            if flag:
                lpath=cnt+1-used[nxt]
                roop=(K-cnt)//lpath
                #print(lpath,roop,cnt)
                cnt+=roop*lpath
                flag=0
        now=nxt
        #print(now,cnt)
        if cnt==K:
            break
        cnt+=1
        
            
    print(now+1)

main()

Submission status: Accepted

Solution code:
_, k = list(map(int, input().split()))
a = list(map(int, input().split()))
l = []
pre = []
d = {0: None}
s = a[0] - 1
while True:
    l.append(s)
    if s in d:
        ind = l.index(s) + 1
        break
    else:
        d[s] = None
        s = a[s] - 1
if ind == len(l):
    pass
else:
    pre = l[: ind]
    l = l[ind:]
if len(pre) < k:
    num = (k - len(pre)) % len(l) - 1
    ans = l[num] + 1 
else:
    ans = pre[k - 1] + 1
print(ans)

Submission status: Accepted

Solution code:
N, K = [int(i) for i in input().split()]
X = [int(i) for i in input().split()]

town = []
dic = {}

i = 0
j = 0

while i not in dic and j < K:
    dic[i] = j
    town.append(i)
    i = X[i] - 1
    j += 1
    
if j == K:
    output = i + 1
    
else : 
    num = dic[i]
    loop = j - num
    output = town[((K-num) % loop) +num] + 1
    
print(output)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
import sys
sys.setrecursionlimit(10**6)
#template
N,K = inputlist()
A = inputlist()
seen = [False]*(N+1)
dic = {n:0 for n in range(1,N+1)}
for i in range(N):
    dic[i+1] = A[i]

def search(i,count):
    seen[i] = True
    next_i = dic[i]
    if seen[next_i]:
        count+=1
        return [next_i,count]
    count+=1
    return search(next_i,count)
key,count_sum = search(1,0)

def find(i,count):
    if i == key:
        return count
    count+=1
    return find(dic[i],count)

tmp = find(1,0)
if K < count_sum:
    ans = 1
    for i in range(K):
        ans = dic[ans]
    print(ans)
    exit()

d = count_sum-tmp
Ka = K-tmp

mod = Ka % d

loop = []
loop.append(key)
def dfs(i):
    next_i = dic[i]
    if next_i == key:
        return False
    loop.append(next_i)
    return dfs(next_i)
dfs(key)

print(loop[mod])

Submission status: Accepted

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

flag = [False] * N
counted = [1]

nextT = A[0]
flag[0] = True
for x in range(N):
    if flag[nextT - 1] is False:
        counted.append(nextT)
        flag[nextT - 1] = True
        nextT = A[nextT - 1]
    else:
        break
before_loop_len = counted.index(nextT)
loop_len = x - before_loop_len + 1

if K <= before_loop_len:
    print(counted[K])
else:
    checkK_prep = K - before_loop_len
    checkK = checkK_prep % loop_len
    print(counted[before_loop_len + checkK])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
now = 1
ss = set([1])
sw = 0
x = 0
for i in range(k):
    now = a[now-1]
    ss.add(now)
    if len(ss) != i+2:
        b = now
        x = i+1
        sw = 1
        break
y = 0
now2 = 1
for j in range(x-1):
    if now2 == b:
        y = j
        break
    now2 = a[now2-1]
if sw == 1:
    L = (k-y)%(x-y)
    for i in range(L):
        now = a[now-1]
print(now)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    history = []
    visited = [False] * n 
    for i in range(n):
        a[i] -= 1
    
    now = 0

    while k > 0 and not visited[now]:
        visited[now] = True
        history.append(now)

        now = a[now]
        k -= 1
    
    if k == 0:
        print(now + 1)
    else:
        index = 0
        while history[index] != now:
            index += 1
        
        size = len(history) - index
        print(history[index + (k % size)] + 1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(x)-1 for x in input().split()]
lis = [None] * n
now = 0
lis[0] = 0
num = 0
rode = [0]
while True:
    now = a[now]
    num += 1
    rode.append(now)
    if num == k:
        print(now + 1)
        break
    if lis[now] == None:
        lis[now] = num
    else:
        print(rode[lis[now] + (k-lis[now]) % (num - lis[now])] + 1)
        break

Submission status: Accepted

Solution code:
import sys


try:
    sys.stdin = open(sys.path[0] + '/input.txt', 'r')
    sys.stdout = open(sys.path[0] + '/output.txt', 'w')
except FileNotFoundError:
    pass


n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))
arr = [i - 1 for i in arr]

p = 0
route = []
seen = set()

while True:
    route.append(p)
    seen.add(p)

    p = arr[p]
    if p in seen:
        break

loop_start = route.index(p)
loop_len = len(route) - loop_start

if k <= loop_start:
    print(route[k] + 1)
else:
    rem = (k - loop_start) % loop_len
    print(route[loop_start + rem] + 1)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
d=[2*k]*-~n
s=1
while k:k-=1;s=a[s-1];k%=d[s]-k;d[s]=k
print(s)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
s = input().split(' ')
p = 1
l = -1
dict = {}
for i in range(K):
	if s[p - 1] in dict:
		x = dict[s[p - 1]]
		l = i
		break
	else:
		dict[s[p - 1]] = i
	p = int(s[p - 1])
if l != -1:
	for i in range((K - (l)) % (l - x)):
		p = int(s[p - 1])
print(p)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
X = list(map(int, input().split()))
town = []
dic = {}
i = 0
j = 0
while i not in dic and j < K:
    dic[i] = j
    town.append(i)
    i = X[i] - 1
    j += 1

if j == K:
    print(i + 1)

else:
    num = dic[i]
    loop = j - num
    print(town[((K - num) % loop) + num] + 1)