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:
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 numpy as np
n, k = map(int, input().strip().split())
as_ = np.array(list(map(int, input().strip().split())))
as_ -= 1


first_visited = [-1] * n

now = 0
num_teleport = 0
while True:
    if first_visited[now] == -1:
        first_visited[now] = num_teleport
    else:
        # ループを発見した
        loop_length = num_teleport - first_visited[now]
        loop_start_point = now
        time_to_start_point = first_visited[now]
        break

    now = as_[now]
    num_teleport += 1


now2 = 0
if k > time_to_start_point:
    k -= time_to_start_point
    k %= loop_length
    now2 = loop_start_point

for i in range(k):
    now2 = as_[now2]

print(now2 + 1)

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()))

check = [False for _ in range(n + 1)]
route = [1]
check[1] = True
now = a[0]
cnt = 1
while (1):
    # roup += 1
    # route.append(now)
    if cnt == k:
        print(now)
        exit()

    if check[now]:
        break
    else:
        check[now] = True
        route.append(now)
        cnt += 1
        now = a[now - 1]

indexnow = route.index(now)
roop_length = len(route) - indexnow
new_route = route[indexnow:]
# print(indexnow)
# print(new_route)
# print(roop_length)
# print(route)

print(new_route[(k - indexnow) % roop_length])

Submission status: Accepted

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

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

def main():
    n,k = readInt()
    a = readInt()
    pos = 0
    visit = [0] * n
    move = []
    roop = []
    while visit[pos]!=2:
        if visit[pos]==0:
            move.append(pos)
        else:
            roop.append(pos)
        visit[pos] += 1
        pos = a[pos] - 1
    num = 0
    if len(move)>k:
        print(move[k]+1)
    else:
        num = (k - (len(move)-len(roop))) % len(roop)
        print(roop[num]+1)
    return

if __name__=='__main__':
    main()

Submission status: Accepted

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

    v = [False] * N
    c = 0

    while True:
        if K == 0:
            print(c+1)
            return
        if v[c]:
            break
        v[c] = True
        c = A_i[c]
        K -= 1

    x = c
    y = 0
    while True:
        if K == 0:
            print(c+1)
            return
        c = A_i[c]
        K -= 1
        y += 1
        if x == c:
            break

    K = K % y
    while True:
        if K == 0:
            print(c+1)
            return
        c = A_i[c]
        K -= 1


main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
route = [1]
dest = A[0]
check = {i: False for i in range(n)}
while not check[dest - 1]:
    check[dest - 1] = True
    route.append(dest)
    dest = A[dest - 1]
ind = route.index(dest)
cycle = route[ind:]
if k >= ind:
    ans = (k - ind) % len(cycle)
    print(cycle[ans])
else:
    print(route[k])

Submission status: Accepted

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

move = [-1] * N
point = 0
count = 0
L = [0]
while True:
    if move[point] != -1:
        break
    move[point] = A[point] - 1
    point = move[point]
    L.append(point)
    count += 1
loop_start = L.index(move[point])
loop_L = L[loop_start:]

if K <= count:
    print(L[K] + 1)
    exit()
print(loop_L[(K - count - 1) % len(loop_L)] + 1)

Submission status: Accepted

Solution code:
# import numpy as np
# import queue
# import heapq


def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    f_loop = [1]
    passed = set(f_loop)

    next_idx = 1
    while True:
        next_town = As[next_idx-1]
        if next_town in passed:
            idx_head = f_loop.index(next_town)
            n_loop = len(f_loop) - idx_head
            break

        passed.add(next_town)
        f_loop.append(next_town)
        next_idx = next_town

    if idx_head + n_loop <= K:
        target = idx_head + (K - idx_head - n_loop) % n_loop
    else:
        target = K

    print(f_loop[target])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, K = lr()
    A = lr()
    vis = [-1]*(N+1)
    dis = [0]*(N+1)
    v = 1
    cnt = 0
    while vis[v] == -1:
        dis[cnt] = v
        vis[v] = cnt
        v = A[v-1]
        cnt += 1
    if K <= vis[v]:
        print(dis[K])
    else:
        print(dis[(K-vis[v])%(cnt-vis[v])+vis[v]])
resolve()

Submission status: Accepted

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

cnt = 1
v = 0
checked = [-1]*N
checked[0] = 0
while True:
    v = As[v]
    if checked[v]!=-1:
        loop = cnt-checked[v]
        road = checked[v]
        break
    cnt += 1
    checked[v] = cnt-1

ite = K if K<=road else road+((K-road)%loop)

v = 0
for i in range(ite):
    v = As[v]

print(v+1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, K = map(int, rl().split())
    A = list(map(int, rl().split()))
    
    pos = dict()
    for idx, ai in enumerate(A):
        pos[ai] = idx + 1
    
    roop = 0
    u_set = set()
    u_set.add(1)
    counter = dict()
    counter[1] = 0
    ca = A[0]
    cnt = 1
    roop_s = 0
    b = 0
    while 1:
        if ca in u_set:
            if ca == roop_s:
                roop = cnt - counter[ca]
                break
            elif roop_s == 0:
                counter[ca] = cnt
                roop_s = ca
                b = cnt
        u_set.add(ca)
        ca = A[ca - 1]
        cnt += 1
    
    ans = 0
    if K < b:
        ca = A[0]
        cnt = 1
        while 1:
            if cnt == K:
                ans = ca
                break
            ca = A[ca - 1]
            cnt += 1
    else:
        m = (K - b) % roop
        ca = A[pos[roop_s] - 1]
        cnt = 0
        while 1:
            if cnt == m:
                ans = ca
                break
            ca = A[ca - 1]
            cnt += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
from collections import defaultdict
d = defaultdict(int)
n=0
d[0]=1
i=2
while d[A[n]-1]==0:
  d[A[n]-1]+=i
  if i-1==K:
    print(A[n])
    exit(0)
  i+=1
  n=A[n]-1
K-=d[A[n]-1]-1
X=d[n]-d[A[n]-1]+1
n=A[n]-1
for i in range(K%X):
  n=A[n]-1
print(n+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def input_one_number():
    return int(input())

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

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


N,K = input_multiple_number()
A = input_multiple_number_as_list()

isVisit = [-1]*N

orgK = K
now = 1
cnt = 0
looper = 0
while K > 0:
	if isVisit[now-1] >= 0:
		looper = cnt - isVisit[now-1]
		break

	isVisit[now-1] = cnt
	now = A[now-1]
	cnt += 1

K -= cnt
if K <= 0:
	now = 1
	K = orgK
else:
	K %= looper

for i in range(K):
	now = A[now-1]

print(now)

Submission status: Accepted

Solution code:
n,d=map(int,input().split())
x=[0]+list(map(int,input().split()))
N=n+1
y=list(range(N))
#print(x)
#print(y)
while d:
  if d&1:
    y=[x[y[i]] for i in range(N)]
  x=[x[x[i]] for i in range(N)]
  d>>=1
res=[0]*N
#print(x)
print(y[1])

Submission status: Accepted

Solution code:

import math

def input_num():
	ls = input().strip().split(" ")
	return [int(e) for e in ls]

n,k = input_num()
a_ls = input_num()

d = {}
now = 1
result_ls = [now]
cnt = 0
while True:
	d[now] = cnt
	now = a_ls[now-1]
	if now in d:
		bun = d[now]
		break
	result_ls.append(now)
	cnt += 1


if k < bun:
	print(result_ls[k])
else:
	jun = len(result_ls) - bun
	idx = bun + (k-bun)%jun
	print(result_ls[idx])

Submission status: Accepted

Solution code:
# @author 

import sys

class DTeleporter:
    def solve(self, tc=0):
        n, k = [int(_) for _ in input().split()]
        a = [int(_) - 1 for _ in input().split()]
        done = dict()
        cur = 0
        steps = 0
        while cur not in done and steps < k:
            done[cur] = steps
            cur = a[cur]
            steps += 1
        
        if steps == k:
            print(cur + 1)
            return

        d = steps - done[cur]
        steps = steps + ((k - steps) // d) * d

        while steps < k:
            cur = a[cur]
            steps += 1

        print(cur + 1)


solver = DTeleporter()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

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

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n, k = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	here = 1
	patarrn = []
	dist = [0]*n
	while 1:
		here = a[here-1]
		if dist[here-1]:
			break
		dist[here-1] = 1
		patarrn.append(here-1)
	log.print(here, patarrn)
	b = patarrn.index(here-1)
	if k <= len(patarrn):
		print(patarrn[k-1]+1)
		exit()
	patarrn = patarrn[b:]
	log.print(patarrn, b, patarrn[(k-b) % len(patarrn) - 1])
	print(patarrn[(k-b) % len(patarrn) - 1]+1)


main()

Submission status: Accepted

Solution code:
import itertools
import numpy as np

def main():
  n, k = [int(i) for i in input().split()]
  A = [None] + [int(i) for i in input().split()]

  slow = fast = 1

  for i in range(k):
    slow = A[slow]
    fast = A[A[fast]]
    if slow == fast:
      break
    if i == k-1:
      return slow

  slow = 1
  count = 0
  while slow != fast:
    slow = A[slow]
    fast = A[fast]
    count += 1

  branch = fast
  branch_num = count
  count = 1
  node = A[branch]
  while node != branch:
    node = A[node]
    count += 1
  
  idx = (k - branch_num) % count + branch_num
  ret = 1
  for _ in range(idx):
    ret = A[ret]
  return ret

print(main())

Submission status: Accepted

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

t = 0
now = 1
memo = [0]*(N+1)
memo[1]=1
jun = [1]
flag = 0
while t < K:
    t += 1
    next = A[now-1]
    if memo[next]>0:
        flag = 1
        break
    memo[next]=t+1
    jun.append(next)
    now = next
if flag ==0:
    print(now)
else:
    S = (t+1)-memo[next]
    for i in range(len(jun)):
        if jun[i]==next:
            start = i
            break
    K += -1*start
    amari = K%S
    print(jun[start+amari])

Submission status: Accepted

Solution code:
import sys

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + a

visited = set([])
hist = [-1 for _ in range(n+1)]
cur = 1
cnt = 0
d = 0

while True:
    if cnt == k:
        print(cur)
        sys.exit()
    if hist[cur] != -1:
        d = cnt - hist[cur]
        break
    hist[cur] = cnt
    cur = a[cur]
    cnt += 1

k -= hist[cur]
index = hist[cur] + k % d
# print(hist)

for i, histi in enumerate(hist):
    if index == histi:
        print(i)
        sys.exit()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 10 20:54:33 2020

@author: Kanaru Sato
"""

n,k = list(map(int,input().split()))
_ = list(map(int,input().split()))
np = [0]+_

cp = 1
dic = {"1":0}
kaisu = 0

while True:
    kaisu += 1
    cp = np[cp]
    if cp in dic:
        break
    else:
        dic[cp] = kaisu

loopstart = cp
looplength = kaisu-dic[loopstart]

if k <= dic[loopstart]:
    ans = [i for i, v in dic.items() if v == k]
    print(ans[0])
else:
    k = k-dic[loopstart]
    k = k%looplength
    ans = [i for i, v in dic.items() if v == dic[loopstart]+k]
    print(ans[0])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    cnt = 0
    used = [-1] * N
    used[0] = 0
    cur = 0
    loop_cnt = 0
    start = 0
    for i in range(1, N+1):
        cur = A[cur] - 1
        if i == K:
            print(cur+1)
            sys.exit() 
        if used[cur] == -1:
            used[cur] = i
            continue
        else:
            loop_cnt = i
            start = cur
            break
    K -= loop_cnt
    loop_cnt -= used[start]
    x = K % loop_cnt
    for i in range(N):
        if used[i]-used[start] == x:
            print(i+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


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


def llmi(n):
    return [lmi() for _ in range(n)]


def main():
    N, K = lmi()
    A = lmi()
    c = [-1] * N
    current = 0
    d = dict()
    d[0] = 0
    c[0] = 0
    count = 0
    loop_start = -1
    for count in range(1,2 * N+2):
        _next = A[current] - 1
        c[_next] = count
        d[count] = _next
        current = _next
    for i in reversed(range(N)):
        if d[i] == d[N]:
            loop_size = N- i
            break
    if K <= 2*N:
        print(d[K] + 1)
    else:
        print(d[(K - N) % loop_size + N] + 1)
    # print(loop_size,loop_start)
    # print(c, d, loop_size, loop_start, loop_size)
    # print(d[K % loop_size] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,k = mi()
alis = li()
for i in range(n):
    alis[i] -= 1

dp = [0]*(n+1)
dp2 = [0]*(n+1)

ima = 0
for i in range(n):
    ima = alis[ima]
    if dp[ima] == 0:
        dp[ima] = i+1
    else:
        ragu = i+1
        dp2[ima] = i+1
        break
for i in range(1,n+1):
    ima = alis[ima]
    if dp2[ima] == 0:
        dp2[ima] = i + ragu
    else:
        ragu2 = ragu + i
        break

if k < ragu:
    for i in range(0,n):
        if dp[i] == k:
            print(i+1)
            exit()

else:
    delta = ragu2 - ragu
    for i in range(n):
        if dp2[i] == 0:
            continue
        else:
            tmp = k - dp2[i]
            if tmp % delta == 0:
                print(i+1)
                exit()

Submission status: Accepted

Solution code:
import collections

N,K = map(int,(input().split()))
a = list(map(int,(input().split())))
a.insert(0,-1)

now = 1
visit = [1]
again = collections.defaultdict(lambda:-1)
again[1] = 0
c = 0

for step in range(1,N+1):
    visit.append(a[now])
    if again[ a[now] ] == -1:
        again[ a[now] ] = step
    else:
        c += 1
        if c == 1:
            loop = a[now]
            loop_step = step
    now = a[now]

re = loop_step - again[loop]

if K <= again[loop]:
    print(visit[K])
else:
    tmp = again[loop]
    for key in again.keys():
        again[key] -= tmp
    amari = (K-tmp)%re
    for key in again.keys():
        if again[key] == amari:
            print(key)

"""
print(visit)
print(again[loop])
print(loop)
print(again)
print(loop_step)
print(re)
"""

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

if K <= 2 * 10 ** 5 + 2:
    ans = 1
    for i in range(K):
        ans = A[ans - 1]
    print(ans)
    exit()


cnt = [0] * (N + 1)
p = A[0]
c = 1

while 1:
    if cnt[p] == 0:
        cnt[p] = c
    else:
        c1 = cnt[p]
        c2 = c
        break
    p = A[p - 1]
    c += 1

#print(c2- c1)

B = [0, A[0]]
for _ in range(3 * 10 ** 5):
    B.append(A[B[-1] - 1])

BN = len(B)

for i in range(BN - 1, -1, -1):
    if i % (c2 - c1) == K % (c2 - c1):
        print(B[i])
        exit()

Submission status: Accepted

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

l = [1]
kanryou_town = [0]*(N+1)
kanryou_town[1] = 1
now_town = 1
loop_town = 0
for i in range(N):
    now_town = A[now_town-1]
    if kanryou_town[now_town] == 1:
        loop_town = l.index(now_town)
        break
    else:
        kanryou_town[now_town] = 1
        l.append(now_town)

loop_num = len(l)-loop_town
if K > loop_town:
    num = (K - loop_town)%loop_num + loop_town
else:
    num = K
#
# num = (K+1)%len(l)
# print(l)

print(l[num])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
    A[i] -= 1
L = [0]
t = 0
F = [-1 for _ in range(N)]
F[0] = 0
c = 1
while F[A[t]] == -1:
    t = A[t]
    F[t] = c
    c += 1
    L.append(t)
loop = c - F[A[t]]
buffer = c - loop
if K < buffer:
    print(L[K] + 1)
else:
    NL = L[buffer:]
    amari = (K - buffer) % loop
    print(NL[amari] + 1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
r=[0]
z=[True]*N
x=[-1]*N
x[0]=0
z[0]=False
n=A[0]-1
i=0
while z[n] and i<K:
    i+=1
    r.append(n)
    x[n]=i
    z[n]=False
    p=n
    n=A[n]-1
if i==K:
    print(p+1)
else:
    s=x[n]
    r=r[s:]
    l=len(r)
    t=(K-s)%l
    print(r[t]+1)

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():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    visited = [0]
    visited_set = set()
    now = 0
    for k in range(K):
        now = A[now] - 1
        if now in visited_set:
            start = visited.index(now)
            shuki = k + 1 - start
            print(visited[start:][(K - start) % shuki] + 1)
            return
        visited.append(now)
        visited_set.add(now)
    print(visited[-1] + 1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = [int(x) for x in input().split()]
a = [int(x)-1 for x in input().split()]
loop = []
seen = [0]*n
num = 0
flag = 0
while k>0:
    if seen[num]==1:
        flag = 1
        break
    seen[num]=1
    loop.append(num)
    num = a[num]
    k-=1
if flag:
    index = loop.index(num)
    loop = loop[index:]
    print(loop[(k%len(loop))]+1)
else:
    print(num+1)

Submission status: Accepted

Solution code:
def main():
    N, K = (int(_) for _ in input().split())
    A = [int(_)-1 for _ in input().split()]
    visited = [-1] * N
    now = cc = 0
    while True:
        if visited[now] == -1:
            visited[now] = cc
            cc += 1
            now = A[now]
        else:
            T = cc - visited[now]
            break
    if K < visited[now]:
        for i in range(N):
            if visited[i] == K:
                print(i+1)
                break
    else:
        K -= visited[now]
        for i in range(N):
            if visited[i] == K%T + visited[now]:
                print(i+1)
                break
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
d=dict()
for i,a in enumerate(A):
    d[i+1] = a
p=1
li = set()
li.add(1)
for i in range(k):
    #print(p,li)
    p = d[p]
    #print(p,li)
    if p in li:
        cyc =  i + 1
        q = 1
        st=0
        while q != p:
            q = d[q]
            st+=1
        cyc -=st
        k = (k-st) % cyc + st
        r = 1
        #print(k)
        for _ in range(k):
            #print(r)
            r = d[r]
        print(r)
        sys.exit()
    li.add(p)
else:
    print(p)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
    A[i] = A[i] -1
G = 0
lis = [0]*N
lis[0] = 1
roop = []
cnt = 0
while True:
    G = A[G]
    cnt +=1
    lis[G] += 1
    if lis[G] == 2:
        roop.append(G)
    elif lis[G] == 3:
        break

roop_cn = len(roop)
diff = cnt - roop_cn*2
if K < roop_cn + diff:
    G = 0
    for i in range(K):
        G = A[G]
    print(G + 1)
    exit()

K_n = K - diff
amari = K_n % roop_cn
print(roop[amari]+1)

Submission status: Accepted

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

    now = 1
    n_move = 0
    graph = []
    visited = set()
    while True:
        graph.append(now)
        visited.add(now)
        now = A[now-1]
        n_move += 1
        if now in visited:
            break

    loop_start = now
    to_loop_start = 0
    for i in range(len(graph)):
        if graph[i] == loop_start:
            to_loop_start = i
    
    per_loop = n_move - to_loop_start
    
    if K <= to_loop_start:
        print(graph[K])
    else:
        print(graph[to_loop_start + (K-to_loop_start) % per_loop])

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,k = inpm()
    a = inpl()
    past = [0 for _ in range(n)]
    past[0] = 1
    root = [0]
    pre = 0
    while True:
        Next = a[pre]-1
        if past[Next]:
            break
        root.append(Next)
        pre = Next
        past[Next] = 1
    rev = []
    i = 0
    while root[len(root)-1-i] != Next:
        rev.append(root[len(root)-1-i])
        i += 1
    rev.reverse()
    rever = [Next]
    for i in range(len(rev)):
        rever.append(rev[i])
    n1 = len(root)
    n2 = len(rever)
    if n1-1 >= k:
        print(root[k]+1)
        return
    if rever[0] != 0:
        k -= n1-n2
    print(rever[(k)%n2]+1)
    
if __name__ == "__main__":
    main()

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

v = 0
li = [v]
set_ = {v}
while True:
    nxt_v = a[v]
    if nxt_v not in set_:
        li.append(nxt_v)
        set_.add(nxt_v)
        v = nxt_v
    else:
        start = nxt_v
        break

for i in range(len(li)):
    if li[i] == start:
        ratio = li[i:]
        syoko = li[0:i]

if k < len(syoko):
    print(syoko[k] + 1)

else:
    k -= len(syoko)
    print(ratio[k % len(ratio)] + 1)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N, K = map(int, input().split())
    g = {}
    for i, a in enumerate(list(map(int, input().split()))):
        g[i + 1] = a

    rs = [1, g[1]]
    pos = g[1]
    used = [False for _ in range(N)]
    used[0] = True
    roop_i = None
    while 1:
        rs.append(g[pos])
        used[pos - 1] = True
        pos = g[pos]
        if used[pos - 1] is True:
            roop_i = pos
            break

    idx1 = rs.index(roop_i)

    d1 = idx1
    d2 = len(rs) - idx1 - 1

    if K <= d1:
        print(rs[K])
    else:
        print(rs[(K - d1) % d2 + d1])

Submission status: Accepted

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

rep_check = 0
now = 1
place = dict()
place2 = []

if now == a[1]:
    print(1)
    exit()

while now not in place:
    place[now] = 1
    place2.append(now)
    now = a[now]
    rep_check += 1
    if rep_check == k:
        print(now)
        exit()

rep_start = 0
for i in enumerate(place):
    if i[1] == now:
        rep_start = i[0]
        break

k -= rep_start
rep_cnt = len(place) - rep_start

place2 = place2[rep_start:]
k %= rep_cnt
print(place2[k])

Submission status: Accepted

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

history = []
visited = set()
cur = 0
for i in range(k):
    if cur in visited:
        x = history.index(cur)
        y = len(history) - x
        print(history[x+(k-x)%y] + 1)
        exit()

    visited.add(cur)
    history.append(cur)
    cur = a[cur]

print(a[history[k-1]]+1)

Submission status: Accepted

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

path = []
passed = set([])
p = 0
while 1:
  if k ==0:
    print(p+1)
    exit()
  if p not in passed:
    path.append(p)
    passed.add(p)
    p = A[p]
    k -= 1
  else:
    break
path = path[path.index(p):]
term = len(path)
k %= term
print(path[k]+1)

Submission status: Accepted

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


def answer():
    path = [1]
    visited = set([1])
    now = 1
    t = 0

    while True:
        if now == a[now - 1]:
            return now

        now = a[now - 1]
        t += 1

        if t == k:
            return now

        if now in visited:
            ti = path.index(now)
            tc = t - ti
            cycle = path[ti:]
            break
        else:
            path.append(now)
            visited.add(now)

    return cycle[(k - t) % tc]


print(answer())

Submission status: Accepted

Solution code:
from collections import defaultdict
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))

#　町iを尋ねた回数
check = {}
check[1] = 0

# cnt[i] i回目に行った町
cnt = [1]

# 回数
i = 0

# 現在地
now = 1
while True:
    cnt.append(a[now])
    i += 1
    now = cnt[-1]
    if now in check.keys():
        ans = (k-i) % (i - check[now])
        print(cnt[check[now]+ans])
        break
    else:
        check[now] = i
    if i == k:
        print(now)
        break

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
dic = {1:1}
his=[1]
p=1
s=0
g=0
step=1
for i in range(k):
    t=a[p-1]
    if (t in dic and dic[t]==1):
        s=t
        g=a[t-1]
        break
    else:
        dic[t]=1
    step+=1
    his.append(t)
    p=t
x=his.index(t)
o=step-x
lp=his[x:]
k-=x
#print(x,o,his,lp)
#print(dic)
print(lp[k%o])

Submission status: Accepted

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

if N > K:
    ans = 0
    while K > 0:
        ans = A[ans] -1
        K -= 1
    print(ans+1)
else:
    count = 0
    a = 0
    # visited = [0]
    is_visited = [0 for _ in range(N)]
    is_visited[0] = 1
    while True:
        a = A[a]-1
        count += 1
        if is_visited[a] > 0:
            before_roop = is_visited[a]-1
            cycle = count - before_roop
            break
        is_visited[a] = count+1
        # if a in visited:
        #     break
        # visited.append(a)
    # before_roop = visited.index(a)
    # cycle = len(visited) - before_roop
    mod = (K - before_roop)%cycle
    # print(visited[before_roop + mod] +1)
    print(is_visited.index(is_visited[a] +mod) +1)

Submission status: Accepted

Solution code:
import sys
from typing import Callable, List, NoReturn, Tuple


def main() -> NoReturn:
    scan: Callable[[], str] = sys.stdin.readline

    n, k = map(int, scan().rstrip().split())
    a: Tuple[int] = tuple(int(a_i) - 1 for a_i in scan().rstrip().split())

    flag: List[bool] = [False] * n
    path: List[int] = []

    current_city: int = 0
    prev_city: int = -1

    while not flag[current_city]:
        flag[current_city] = True
        path.append(current_city)
        prev_city = current_city
        current_city = a[current_city]

    start_loop_index: int = path.index(current_city)

    if k < len(path):
        print(path[k] + 1)
    else:
        index_in_loop: int = (k - start_loop_index) % (len(path) - start_loop_index)
        print((path[start_loop_index:])[index_in_loop] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 何回で１周するのか
N, K = lr()
A = [0] + lr()
if A[1] == 1:
    print(1); exit()
lap = 1
cur = A[1]
nex = [1, A[1]]
been = set([A[1]])
while cur != 1:
    if lap == K:
        print(cur); exit()
    cur = A[cur]
    lap += 1
    nex.append(cur)
    if cur in been:
        lap2 = 1
        cur2 = A[cur]
        while cur2 != cur:
            if lap + lap2 == K:
                print(cur2)
            cur2 = A[cur2]
            lap2 += 1
        K -= lap
        K %= lap2
        for _ in range(K):
            cur2 = A[cur2]
        print(cur2); exit()
    been.add(cur)

# lap回で１周
K %= lap
answer = nex[K]
print(answer)