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())
A = list(map(int,input().split()))
L = [1]
s = set()
s.add(1)
now = 1
for _ in range(N):
    if A[now - 1] in s:
        K -= L.index(A[now - 1])
        if K >= 0: K %= len(L) - L.index(A[now - 1])
        break
    L.append(A[now - 1])
    s.add(A[now - 1])
    now = A[now - 1]
#print(L)
#print(K)
print(L[K + L.index(A[now - 1])])

Submission status: Accepted

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

visited = [False] * n
dist = [0] * n
v = 0
leng = 0

for i in range(n+10):
    if i == k: print(v+1); exit()
    if visited[v]:
        leng = i - dist[v]
        k -= dist[v]
        break
    visited[v] = True
    dist[v] = i
    v = g[v]

for i in range(k % leng):
    v = g[v]

print(v+1)

Submission status: Accepted

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

order = []
now = 1
count = 0
d = defaultdict(int)


for i in range(n):
    if d[now]!=0:
        s=d[now]-1
        g=i
        break
    order.append(now)
    d[now] = i+1
    now = a[now-1]


if k<=s:
    print(order[k])
else:
    k-=s
    loop = order[s:g]
    print(loop[k%len(loop)])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(v, s):
    global origin, cycle
    path[v] = s
    nv = A[v]
    if path[nv] >= 0:
        origin = nv
        cycle = (s + 1) - path[nv]
    else:
        dfs(nv, s + 1)


N, K = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
origin = 0
cycle = 0
path = [-1] * N
dfs(0, 0)

if K <= path[origin]:
    for i, s in enumerate(path):
        if s == K:
            print(i + 1)
            break
else:
    rest = K - path[origin]
    rest %= cycle
    for i, s in enumerate(path):
        if s == path[origin] + rest:
            print(i + 1)
            break

Submission status: Accepted

Solution code:
import sys
from collections import deque

N, K = map(int, sys.stdin.readline().strip().split())
tmp = list(map(int, sys.stdin.readline().strip().split()))

A = [a-1 for a in tmp]

visited = set()
loop = []

q = deque()
q.append(0)
start = float("inf")
end = float("inf")

count = 0
while q and count <= N:
    s_town = q.popleft()
    # ループを確認
    if s_town in visited:
        start = loop.index(s_town)
        end = len(loop)
        break
    visited.add(s_town)
    loop.append(s_town)
    n_town = A[s_town]
    q.append(n_town)
    count += 1

# print(start, end)
if start >= K:
    print(loop[K]+1)
else:
    res = K - start
    res %= (end - start)
    # print("res", res)
    print(loop[start + res]+1)

Submission status: Accepted

Solution code:
import sys

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

cnt = 0
current = 0
roads = []
reached = [-1 for _ in range(N)]

while True:
    if reached[current] >= 0:
        initial = reached[current]
        mod = cnt - initial
        if K <= initial:
            print(roads[K]+1)
        else:
            k = (K-initial) % mod
            print(roads[initial:][k]+1)
        sys.exit()
    roads.append(current)
    reached[current] = cnt
    cnt += 1
    current = A[current] - 1

Submission status: Accepted

Solution code:
import sys
n, k = list(map(int, input().split()))
nums = [-1] + list(map(int, input().split()))

visited = [0 for _ in range(n + 1)]
path = [1]
cur = 1
visited[1] = 1
for i in range(k):
	cur = nums[cur]
	path.append(cur)
	if visited[cur] == 1:
		for idx, val in enumerate(path):
			if val == cur:
				break
		# print(k, idx, path)
		# print((k - idx) % (len(path) - idx - 1))
		print(path[idx + (k - idx) % ((len(path) - idx - 1))])
		sys.exit()
	else:
		visited[cur] = 1
print(cur)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')
# ----------------------------------------------------------- #

n, k = Is()
A = LI()
A = [-1] + A
# print(A)

B = [1]
visited = {1}
loopstart = -1
def dfs(num):
    global loopstart
    tmp = A[num]
    if tmp in visited:
        loopstart = tmp
    else:
        B.append(tmp)
        visited.add(tmp)
        dfs(tmp)

dfs(1)
# print(loopstart)
# print(B)
# print(visited)

C = []
for i in range(len(B)):
    if B[i] == loopstart:
        C = B[i:]
# print(C)
lb = len(B)
lc = len(C)
if k < lb:
    print(B[k])
else:
    print(C[(k-lb) % lc])

Submission status: Accepted

Solution code:
import collections
n, k = map(int, input().split())
dat = list(map(int, input().split()))
maze = []
initmaze=[]
recurmaze=[]
used = [-1] * (n + 10)
cur = 0
cnt = 0
while True:
    if used[cur] != -1:
        break
    used[cur] = cnt
    maze.append(cur)
    cur = dat[cur] - 1
    cnt += 1

recurpoint = used[cur]
#print("return to ",recurpoint)
initmaze = maze[:recurpoint]
recurmaze = maze[recurpoint:]

#print(maze)
#print(initmaze)
#print(recurmaze)

l = len(maze)
li = len(initmaze)
lr = len(recurmaze)
if k < li:
    print(initmaze[k] + 1)
else:
    k -= li
    print(recurmaze[k%lr] + 1)

Submission status: Accepted

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

def solve(k, A, N):
    p = 0
    k0 = k
    while k:
        if k&1 ==1:
            p = A[p]
        A = [A[A[x]] for x in range(N)]
        k = k >> 1
        #print("k=%d"%k0, "p=%d"%(p+1))
    #print()
    return p + 1

#for k in range(0, K): print(k, "p=%d"%solve(k, A, N))
print(solve(K, A, N))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N, K = mis()
    A = [a-1 for a in mis()]
    B = [None]*N
    now = 0
    B[now] = 0
    for i in range(1, K+1):
        now = A[now]
        K -= 1
        if B[now] is not None:
            K %= (i - B[now])
            break
        B[now] = i
    for _ in range(K):
        now = A[now]
    print(now+1)

main()

Submission status: Accepted

Solution code:
visited=[0]
visited_set=set()
visited_set.add(0)
n,k=map(int,input().split())
a=list(map(int,input().split()))
next1=0
next2=-1
while True:
    next2=a[next1]-1
    next1=next2
    if next2 in visited_set:
        break
    else:
        visited.append(next2)
        visited_set.add(next2)
#print(visited)
if k<len(visited):
    print(visited[k]+1)
else:
    loop_len=(len(visited)-visited.index(next2))
    k-=(len(visited)-loop_len)
    print(visited[k%loop_len+visited.index(next2)]+1)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


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

pos = A[1]
path = [1]
visited = {1}
cycle_start = -1
for _ in range(N):
    if pos in visited:
        cycle_start = pos
        break
    visited.add(pos)
    path.append(pos)
    pos = A[pos]

if cycle_start > 0:
    cycle_start_idx = path.index(cycle_start)
    acyclic_path = path[:cycle_start_idx]
    cyclic_path = path[cycle_start_idx:]
    if K < len(acyclic_path):
        print(acyclic_path[K])
    else:
        print(cyclic_path[(K - len(acyclic_path)) % len(cyclic_path)])
else:
    print(path[K])

Submission status: Accepted

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

check = [-1] * n
i = 0
count = 0
while True:
    if check[i] != -1:
        lsize = count - check[i] 
        tail = count - lsize
        break
    check[i] = count
    count += 1
    i = an[i] - 1

l = k
if k > tail:
    l = ((k - tail) % lsize) + tail

for i in range(n):
    if check[i] == l:
        print(i + 1)
        break

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, K = rl()
A = rl()

edges = {}
for i, a in enumerate(A):
	edges[i] = a-1

mem = {}
k = 0
n = 0
while True:
	if k == K:
		print(n+1)
		exit()
	if n in mem:
		break
	mem[n] = k
	k += 1
	n = edges[n]

p = k-mem[n]
idx = (K - k) % p

for i in range(idx):
	n = edges[n]
print(n+1)

Submission status: Accepted

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

if A[1] == 1:
    print(1)
    exit()

# 訪問順
B = [1]

# 訪問済み
C = [False] * (n + 1)
C[1] = True


while True:
    B.append(A[B[-1]])
    if C[B[-1]]:
        break
    C[B[-1]] = True

# print(B)

s = B.index(B[-1])

# print(B)
# print(len(B))

if k < s:
    print(B[k])
    exit()


B = B[B.index(B[-1]):-1]
print(B[(k - s) % len(B)])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    visited = [False] * N
    cnt = [0] * N
    visited[0] = True
    B = [0]
    def dfs(s):
        tmp = A[s] - 1
        

        if visited[tmp]:
            B[0] = cnt[tmp]
            for i in range(N):
                if i == tmp:
                    continue
                cnt[i] -= cnt[tmp]
            cnt[tmp] = 0
            return
        
        cnt[tmp] = cnt[s] + 1
        visited[tmp] = True
        if cnt[tmp] == K:
            print(tmp + 1)
            exit()
        dfs(tmp)
    dfs(0)
    K -= B[0]
    t = K % (max(cnt)+1)
    for i in range(N):
        if cnt[i] == t:
            print(i+1)
            exit()
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#code
N,K=map(int,input().split())
A=list(map(int,input().split()))
visited=[0 for i in range(N+1)]
p=1
path=[p]
visited[p]=1
p=A[p-1]
while visited[p]==0:
    path.append(p)
    visited[p]=1
    p=A[p-1]
i=path.index(p)
if(K<i):
    print(path[K])
else:
    K-=i
    print(path[i+K%(len(path)-i)])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
A = LI()
now = 0
D = {0:-1}
for i in range(min(k, n)):
    now = A[now] - 1
    if now in D:
        break
    D[now] = i

if k < n:
    print(now + 1)
    exit()

k -= (i + 1)
b = now
c = k % (i - D[now])
for j in range(c):
    b = A[b] - 1

print(b + 1)

Submission status: Accepted

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

for i in range(N):
    now = tour[-1]
    if gone[now]:
        save = now
        break
    gone[now] = 1
    tour.append(A[now])

save_idx = tour.index(save)

if K <= save_idx:
    print(tour[K])
    exit()

loop = tour[save_idx+1:]
K = K - save_idx - 1
print(loop[K % len(loop)])

Submission status: Accepted

Solution code:
import numpy as np
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n,k=INTM()
    a=LIST()
    vst=[0]*n
    vst[0]=1
    loop=[]
    temp=1
    for i in range(k):
        temp=a[temp-1]
        if vst[temp-1]==0:
            vst[temp-1]=1
        elif vst[temp-1]==1:
            loop.append(temp)
            vst[temp-1]=2
        else:
            temp=loop[-1]
            cost=k-i
            break
        if i==k-1:
            cost=0
    if cost!=0:
        print(loop[(cost-1)%len(loop)])
    else:
        print(temp)
                    
                
if __name__ == '__main__':
    do()

Submission status: Accepted

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/input.txt"
exit $?
'''
import sys

def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n, k = _ia()
    a = [ai-1 for ai in _ia()]
    d = [[0]*n for _ in range(60)]
    d[0] = a
    for i in range(59):
        now = d[i+1]
        prev = d[i]
        for j in range(n):
            now[j] = prev[prev[j]]

    now = 0
    for i in range(k.bit_length()):
        if k & 1:
            now = d[i][now]
        k >>= 1

    return now + 1

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

Submission status: Accepted

Solution code:

def solve(N, K, As):
    current = 1
    count = 0
    teleport = {i + 1 : v for i, v in enumerate(As)}
    dist = {}

    while current not in dist:
        dist[current] = count
        count += 1
        current = teleport[current]
        if K == count:
            return current

    loop_size = count - dist[current]
    K -= dist[current]
    K %= loop_size
    K += dist[current]

    current = 1
    while K > 0:
        current = teleport[current]
        K -= 1
    return current

# assert(solve(4, 6, [3, 2, 4, 1]) == 1)
# assert(solve(4, 5, [3, 2, 4, 1]) == 4)
# assert(solve(4, 4, [3, 2, 4, 1]) == 3)
# assert(solve(4, 3, [3, 2, 4, 1]) == 1)
# assert(solve(4, 2, [3, 2, 4, 1]) == 4)
# assert(solve(4, 1, [3, 2, 4, 1]) == 3)
# assert(solve(2, 1, [2, 1]) == 2)
# assert(solve(2, 2, [2, 1]) == 1)
# assert(solve(2, 10**18, [2, 1]) == 1)
# 
# assert(solve(2, 100, [1, 1]) == 1)
# assert(solve(2, 10**18, [1, 1]) == 1)
# 
# assert(solve(3, 10**18, [2, 3, 3]) == 3)
# assert(solve(3, 1, [2, 3, 3]) == 2)
# assert(solve(3, 10**18, [3, 3, 3]) == 3)
# 
# print("OK")

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
visited = [-1 for _ in range(N+1)]
path = [1]
visited[1] = 0
pos = 1
endi = -1
for i in range(1, N+1):
    pos = A[pos]
    if i == K:
        endi = -i
        break
    if visited[pos] > -1:
        endi = i
        break
    visited[pos] = i

if endi < 0:
    print(pos)
else:
    loop = endi - visited[pos]
    ansi = (K-visited[pos])%loop
    for i in range(ansi):
        pos = A[pos]
    print(pos)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ar=list(map(int,input().split()))
vis=[0 for i in range(n+1)]
x=1
seq=[1]
go=0
rep=0
ct=1
while (vis[x]==0):
    vis[x]=ct
    seq.append(ar[x-1])
    x=ar[x-1]
    ct+=1
    if vis[x]!=0:
        rep=ct-vis[x]
        go=vis[x]
if k<=go:
    print(seq[k])
else:
    print(seq[go+(k-go)%rep])

Submission status: Accepted

Solution code:
import sys

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

town = [0] * n
town[0] = 1
track = [1]
now = 1
cnt = 0
while True:
    now = a[now-1]
    town[now-1] += 1
    cnt += 1
    if town[now-1] > 1:
        loop = now
        break
    track.append(now)
    if cnt == k:
        print(now)
        sys.exit()

idx = track.index(loop)
ans = (k - idx) % (cnt - idx)
print(track[idx:][ans])

Submission status: Accepted

Solution code:
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
V = [-1]*N
W = [-1]*N
x = 0
V[0] = 0
W[0] = 0
for i in range(1, K+1):
    x = A[x] - 1
    W[i] = x
    if V[x] == -1:
        V[x] = i
    else:
        x = W[V[x] + (K-i) % (i -V[x])]
        break
print(x+1)

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(1,0),(-1,0),(0,1),(0,-1)];EightNb=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('EWNS',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1

        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][r-(1<<N)])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][r-(1<<N)]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][r-(1<<N)]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])

    def print(self):
        for i in self.table:
            print(*i)


show_flg=False
show_flg=True
ans=0

n,k=LI()
a=[0]+LI()

#show(a)

v=[-1]*n
c=1
for i in range(n):
    k-=1
    c=a[c]
    #print(i,c)
    if k==0:
        ans=c
        print(ans)
        exit()

t=c
loop=0
for i in range(n):
    loop+=1
    k-=1
    c=a[c]
    if c==t:
        ans=c
        break
    if k==0:
        ans=c
        print(ans)
        exit()

k=k%loop
#show('loop',loop,k)
ans=c

for i in range(k):
    
    k-=1
    c=a[c]
    if k==0:
        ans=c
        print(ans)
        exit()



print(ans)

Submission status: Accepted

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

B = [0] * N
C = []

C.append(0)
now = 0
B[0] = 1
for i in range(N):
    now = A[now] - 1
    if B[now] == 1:
        break
    else:
        C.append(now)
        B[now] = 1

mae = 0
for i in range(len(C)):
    if C[i] == now:
        mae = i
        break

ato = len(C) - 1

if K + 1 <= mae:
    print(C[K] + 1)
else:
    print(C[mae + (K - mae) % (ato - mae + 1)] + 1)

Submission status: Accepted

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

used = [False] * (N + 1)
dist = []
dist.append(1)
for i in range(N):
    v = dist[-1]
    if used[v]:
        break
    used[v] = True
    dist.append(A[v - 1])

g = dist[-1]
s = dist.index(g)

if K <= s:
    print(dist[K])
else:
    k = K - s
    index = k % (len(dist) - s - 1)
    print(dist[s + index])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
l=[-1]*N
l[0]=0
i=1
t=0
while 1:
    t=A[t]-1
    if l[t]!=-1:
        s=i-l[t]
        break
    l[t]=i
    i+=1
if K<i:
    print(l.index(K)+1)
else:
    k=K%s
    if (i//s)*s+k in l:
        print(l.index((i//s)*s+k)+1)
    else:
        print(l.index((i//s-1)*s+k)+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
g = [0] * n
for s, t in enumerate(a):
    g[s] = t

d = [-1] * n
d[0] = 0
cur = 0
while True:
    if k == 0:
        print(cur + 1)
        exit()
    k -= 1
    if d[g[cur]] >= 0:
        cycle_size = d[cur] - d[g[cur]] + 1
        k %= cycle_size
        cur = g[cur]
        while k > 0:
            cur = g[cur]
            k -= 1
        print(cur + 1)
        exit()
    d[g[cur]] = d[cur] + 1
    cur = g[cur]

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

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

cnt = 0
NOW = 0
while True:
    NOW = A[NOW]
    cnt += 1
    if P[NOW] == -1:
        P[NOW] = cnt
        if cnt == K:
            print(NOW+1)
            exit()
    else:
        L = cnt - P[NOW]
        for i in range(P[NOW],P[NOW]+L):
            if K % L != i % L:
                continue
            for k,v in enumerate(P):
                if v == i:
                    print(k+1)
                    exit()

Submission status: Accepted

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

my_dict = dict()

ptr = 0
cnt = 0

while True:
    if ptr in my_dict:
        break
    else:
        my_dict[ptr] = cnt
        cnt += 1
        ptr = a_ls[ptr] - 1

loop = cnt - my_dict[ptr]

if k > 2 * 10 ** 5:
    k = k % loop + loop * (10 ** 6 // loop)

ptr = 0

for i in range(k):
    ptr = a_ls[ptr] - 1

print(ptr + 1)

Submission status: Accepted

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


already_city = [-1 for i in range(N)]
already_city[0] = 0
dep_city = 1

move_count  = 0
while move_count < K:
    move_count += 1
    dep_city = A[dep_city - 1]
    if already_city[dep_city - 1] == -1:
        already_city[dep_city - 1] = move_count
    else:
        loop_count = move_count - already_city[dep_city - 1]
        remain_ = K - move_count
        div_loop_count = remain_ % loop_count
        ans_list_num = div_loop_count + already_city[dep_city - 1]
        dep_city = already_city.index(ans_list_num) + 1
        break
        
        
print(dep_city)

Submission status: Accepted

Solution code:
#n=int(input())
n,k=map(int,input().split())
A = list(map(lambda x:int(x)-1,input().split()))
v = [-1 for _ in range(n)]
v[0] = 0
x = 0
i = 0
flag = False
while True:
    i+=1
    y = A[x]
    k-=1
    if k==0:
        break
    if not flag and v[y]>=0:
        flag = True
        t = i-v[y]
        k%=t
        x=y
        if k==0:
            print(y+1)
            exit(0)
    else:
        v[y]=i
        x=y
print(y+1)

Submission status: Accepted

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

cnt = defaultdict(lambda :0)
num = defaultdict(lambda :0)
cnt[1] = 1
num[1] = 1
trans = 1
for i in range(k):
    temp = a[trans - 1]
    #print(temp)
    if cnt[temp] != 0:
        roop = - cnt[temp] + cnt[trans] + 1
        omit = (k - cnt[temp] + 1) % roop

        ans = num[cnt[temp] + omit]
        print(ans)
        exit()
    cnt[temp] = cnt[trans] + 1
    num[cnt[temp]] = temp
    trans = temp

print(trans)