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

flag=0
def woap(current_city,li,K):
    global flag
    next_city=li[current_city]-1
    if trace[next_city]!=-1 and trace[next_city]!=K:
        flag=1
        return current_city
    else:
        trace[next_city]=K
        return next_city

def woap2(current_city,li):
    next_city=li[current_city]-1
    return next_city

trace=[-1]*N
trace[0]=0
rest=K
current_city=0
for i in range(1,K+1):
    current_city=woap(current_city,A,i)
    if flag==1:
        break
    else:
        rest-=1


loop_length=K-rest-trace[A[current_city]-1]+1
amari=rest%loop_length
for i in range(amari):
    current_city=woap2(current_city,A)

print(current_city+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
r = [None] * N
i = 0
cur = 0
m = None
while True:
    if m is None and r[cur] is not None:
        m = i - r[cur]
        K = i + (K-i)%m
    else:
        r[cur] = i
    if i == K:
        print(cur+1)
        exit()
    i += 1
    cur = A[cur] - 1

Submission status: Accepted

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

root = [1]
pastTown = {1:0}
t = 0
nextTown = 1

while 1:
  t += 1
  nextTown = int(A[nextTown - 1])
  if nextTown in pastTown.keys():
    break
  else:
    root.append(nextTown)
    pastTown[nextTown] = t

if nextTown == root[0]:
  town = root[K % len(root)]
else:
  if K <= pastTown[nextTown]:
    town = root[K]
  else:
    tmp = (K - pastTown[nextTown]) % (len(root) - pastTown[nextTown])
    town = root[pastTown[nextTown] + tmp]

print(town)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
s = set()
s.add(1)
pas1 = [1]
pas2 = []
now = 1
count = 0
if k == 1:
    print(l[0])
    exit()
for i in range(2*n):
    a = l[now-1]
    if a in s:
        index = pas1.index(a)
        k -= index
        le = len(pas1)-index
        print(pas1[k%le+index])
        
        exit()
    else:
        now = a
        s.add(a)
        count += 1
        pas1.append(a)
        
        if count == k:
            print(a)
            exit()

Submission status: Accepted

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

visited = [-1 for i in range(n)]
visited_history = []
machi = 0
before = -1
loop = -1
flag = False
for idx in range(k):
    machi = a[machi] - 1
    if visited[machi] == -1:
        visited[machi] = idx
        visited_history.append(machi)
    else:
        before = visited[machi]
        loop = idx - before
        flag = True
        break

if flag:
    k -= before
    idx = k % loop - 1
    if idx == -1:
        idx = loop - 1
    machi = visited_history[idx + before]

ans = machi + 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

N = None
K = None
A = None

def check(start):
    global N,K,A
    slow = A[start]
    fast = A[A[start]]
    while slow != fast:
        slow = A[slow]
        fast = A[A[fast]]

    slow = start
    while slow != fast:
        slow = A[slow]
        fast = A[fast]

    cycle_start = slow

    cycle_length = 1
    slow = A[slow]
    fast = A[A[fast]]
    while slow != fast:
        slow = A[slow]
        fast = A[A[fast]]
        cycle_length += 1

    return cycle_start, cycle_length

def main():
    global N,K,A
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    A = [""] + A
    start,length = check(1)
    current = 1
    count = 0
    for _ in range(K):
        if current == start:
            break
        current = A[current]
        count += 1
    if current != start:
        return current
    K = (K-count)%length
    for _ in range(K):
        current = A[current] 
    return current

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A = list(map(int, input().split()))

# ループ解析
step_on = [-1] * N
current = 1
min_mv_count = 0
i = 0
for i in range(N + 1):
    #print(current)
    if i == K:
        print(current)
        exit()
    if step_on[current - 1] == -1:
        step_on[current - 1] = i
        current = A[current - 1]
        i += 1
    else:
        #print("else")
        period = i - step_on[current - 1]
        pre_mv = i - period
        min_mv_count = pre_mv + ((K - pre_mv) % period)
        #print("period {} pre_mv {}".format(period, pre_mv))
        #print("min_mv_count {}".format(min_mv_count))
        break

current = 1
#for i in range(K + 1): # 正攻法
for i in range(min_mv_count):
    current = A[current - 1]
print(current)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
keiro = [1]
keiro_set = {1}
flag = True
now = 1
start = 0
loopN = 0
loop_list = []
not_loop = False
for i in range(N):
    now = A[now - 1]
    if now in keiro_set:
        start = keiro.index(now)
        loop_list = keiro[start:]
        loopN = len(loop_list)
        break
    else:
        keiro.append(now)
        keiro_set.add(now)
    if i + 2 > K:
        not_loop = True
        break
if not_loop:
    print(keiro[K])
elif K - start >= 0:
    print(loop_list[(K - start) % loopN])
else:
    print(keiro[K])

Submission status: Accepted

Solution code:
# D
# Teleporter

import numpy as np

def next_town(_list,idx):
    return _list[idx]

n, k = map(int, input().split())
a_list = np.array([int(x) for x in input().split()])

t_list = np.zeros(n, dtype=int)

i = 1
count = 0
flag = True
while count < k:
    i = next_town(a_list,i-1)
    count += 1
    if t_list[i-1] == 0:
        t_list[i-1] = count
    elif flag:
        _roop = count - t_list[i-1]
        _tmp = k - count
        count = k - _tmp % _roop
        flag = False

print(i)

Submission status: Accepted

Solution code:
def main():
  n,k=map(int,input().split())
  a=list(map(int,input().split()))
  b=1
  seen=[-1]*n
  c=0
  while seen[b-1]==-1:
    seen[b-1]=c
    b=a[b-1]
    c+=1
  start=seen[b-1]
  end=c
  k=min(k,start+(k-start)%(end-start))
  b=1
  for _ in range(k):
    b=a[b-1]
  print(b)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:

n,m=list(map(int,input().split(" ")))
 
arr=list(map(int,input().split(" ")))

def bfs(start,n,visited,m):
	
	moves=[]
	moves.append(start)
	visited[start]=1
	br=-1
	# fl=0
	while(True):

		j=arr[start]-1
		
		if(visited[j]==0):
			moves.append(j)
			visited[j]=1
		
		else:
			br=j
			# fl=1
			break
		start=j


	# print(moves,left)
		# q.popleft()
	# print(left,moves)
	if(br!=-1):
		pre=[]
		post=[]
		for i in range(len(moves)):
			if(moves[i]==br):
				pre=moves[:i]
				post=moves[i:]
				break
		if(m<=len(pre)-1):
			print(pre[m]+1)
		else:
			m-=len(pre)
			# print

			print(post[m%len(post)]+1)


	else:
		# curr=0
		# print("hdks")
		print(moves[m%len(moves)]+1)
visited=[0]*n
bfs(0,n,visited,m)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A_s = list(map(int, input().split()))
# それぞれの街に訪れた時のカウント
cache = [0]*N
# cacheの逆引き辞書
MAP = {}
# 町カーソル
i=0
# テレポーターのカウント
cnt=1
# 閉路のサイズ
rplng = 0
nolp = False
while(True):
    if(cache[i]!=0):
        rplng = cnt - cache[i]
        break
    if(cnt > K):
        nolp = True
        break
    MAP[cnt] = i+1
    cache[i] = cnt
    i = A_s[i]-1
    cnt+=1
if(nolp):
    print(i+1)
else:
    ans = MAP[(K-cnt+1)%rplng+cache[i]]
    print(ans)

Submission status: Accepted

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

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

res = [0]
tmp = 0

tf = [-1 for i in range(n)]
tf[0] = 0

for i in range(n):
    tmp = a[tmp] - 1
    if tf[tmp] != -1:
        start = tmp
        break
    else:
        res.append(tmp)
        tf[tmp] = i+1

lenret = i+1
stridx = tf[start]

cycle = lenret - stridx

if stridx >= k:
    print(res[k]+1)
    exit()
else:
    k = k - stridx

    tmp = k % cycle

    print(res[stridx+tmp]+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A_list = list(map(int, input().split()))

ans_list = [1]
history_list = [0 for _ in range(N)]
before_town = 1
loop_start_town = 10 ** 10
for i in range(N):
    now_town = A_list[before_town - 1]
    if history_list[now_town - 1] == 1:
        break
    ans_list.append(now_town)
    before_town = now_town

if len(ans_list) > K:
    print(ans_list[K])
else:
    loop_start_idx = ans_list.index(A_list[ans_list[-1] - 1])
    loop_len = len(ans_list)
    ans_list = ans_list[loop_start_idx:]
    mod_num = (K - loop_len) % (loop_len - loop_start_idx)
    print(ans_list[mod_num])

Submission status: Accepted

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

otozureta = set([1])
otozureta_list = [1]

import sys
sys.setrecursionlimit(1000000)

def search(list, next):
    if not otozureta.isdisjoint(set([next])):
        return next
    else:
        otozureta.add(next)
        otozureta_list.append(next)
        return search(list, routes[next - 1])


target = search(routes, routes[0])
target_index = otozureta_list.index(target)

otozureta_list_len = len(otozureta_list)
loop_length = otozureta_list_len - target_index
loop_made_length = target_index
#print(otozureta)

if K < otozureta_list_len:
    print(otozureta_list[K])
else:

    print(otozureta_list[loop_made_length + ((K - loop_made_length) % loop_length)])

Submission status: Accepted

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

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

city = 1
route = []
cnt = [0] * n
cnt[0] += 1
route.append(1)


while True:
    city = roads[city-1] 
    cnt[city-1] += 1
    if cnt[city-1] == 2:
        st = route.index(city)
        length = len(route) - st
        break
    route.append(city)


if k < len(route):
    print(route[k])

else:
    amari = (k+1-st) % length
    if amari  == 0:
        print(route[-1])
    else:
        print(route[amari+st-1])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A_list = [-1] + list(map(int, input().split()))
out_loop = [1]
flag = [0, 1] + [0]* (N - 1)
a = A_list[1]
while flag[a] == 0:
    out_loop.append(a)
    flag[a] = 1
    a = A_list[a]
    

        
if K <= (len(out_loop) - 1):
    print(out_loop[K])
else:
    loop = out_loop[out_loop.index(a):]
    k = K - (len(out_loop) - 1)
    k %= len(loop)
    print(loop[k - 1])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a_l = list(map(int, input().split()))
a_m = dict()
tmp = list()  # startまでの距離を計測用

f = 1

while True:
    if f in a_m:
        # すでにfrom-toが登録済みであればループのstartを登録終了
        start = f
        pre = tmp.index(f)
        break
    tmp.append(f)
    t = a_l[f-1]  # to
    a_m[f] = t  # from-toを登録
    f = t

if k > pre:
    cycle_len = len(a_m) - pre
    k_mod = (k - pre) % cycle_len

    result = start

else:
    result = 1
    k_mod = k

for _ in range(k_mod):
    result = a_m[result]

print(result)

Submission status: Accepted

Solution code:
def main():
  n,k,*a = map(int,open(0).read().split())
  c = [0]
  visit = [False]*n
  visit[0] = True
  for i in range(n):
    nt = a[c[-1]]-1
    if visit[nt]:
      ws = c.index(nt)
      wst = c[:ws]
      wrt = c[ws:]
      wr = len(wrt)
      break
    else:
      c.append(nt)
      visit[nt] = True
  if ws > k:
    ans = wst[k]
  else:
    ans = wrt[(k-ws)%wr]
  print(ans+1)
main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [val - 1 for val in A]
# print(A)
route = [0]
seen = set()
here = 0
for _ in range(N + 100):
    here = A[here]
    route.append(here)

if len(route) >= K:
    print(route[K] + 1)
else:
    for i in range(len(route)):
        if route[i] in seen:
            start = route.index(route[i])
            period = i - start
            # print(period)
            r = (K - start + 1) % period
            if r == 0:
                idx = period + start - 1
            else:
                idx = r + start - 1
            print(route[idx] + 1)
            break
        seen.add(route[i])

Submission status: Accepted

Solution code:
n,k = list(map(int,input().split()));
a = list(map(int,input().split()));
i = 0;
start = 0;
count = 0;
finished = [0]*n;
while count < n+2 :
    #print(i,count)
    finished[i] = 1;
    i = a[i]-1;
    count += 1;
    if finished[i] :
        start = i;
        break;
    #print(i,count,1) 

amari = 0;
if count > n :
    ans = i+1;
else :
    if start == 0 :
        tostart = 0;
    else :
        i=0;
        count = 0;
        while count < n+1 :
            i = a[i]-1;
            count += 1;
            if i == start :
                break;
        tostart = count;
    i=start;
    count = 0;
    while count < n+1 :
        i = a[i]-1;
        count += 1;
        if i == start :
            break;
    if k < count+tostart :
        i = 0;
        for j in range(k) :
            i = a[i]-1;
        ans = i+1;
    else :
        #print(tostart,count);
        amari = (k-tostart)%count;
        i = start;
        for j in range(amari) :
            i = a[i]-1;
        ans = i+1;

print(ans);

Submission status: Accepted

Solution code:
from sys import stdin

def main():

    input = stdin.readline

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

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

    itta_set = set()
    itta_list = []
    idou_num = 0

    pos = 0

    for i in range(K):
        # itta_list記憶
        if pos not in itta_set:
            itta_set.add(pos)
            itta_list.append(pos)
        else:
            idou_num = i
            break

        # 次の街へ
        pos = A[pos] - 1
    else:
        ans_num = pos + 1
        print(ans_num)
        return

    roop_list = itta_list[itta_list.index(pos):]

    amari = (K - idou_num) % len(roop_list)

    ans_pos = roop_list[amari] + 1

    print(ans_pos)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N ,K  =  [int(i) for i in input().split()]
    As =   [int(i) for i in input().split()]

    rireki = []
    loop = ""

    ind = 1
    flags = [0 for _ in range(N)]
    while(1):
        if flags[ind-1] == 1:
            loop = ind
            break
        else:
            rireki.append(ind)
            flags[ind-1] = 1
            ind = As[ind-1]

        #print(flags)
    #print(rireki,loop)
    loop_c = len(rireki) - rireki.index(loop)
    if K <= len(rireki)-1:
        print(rireki[K])
    else:
        nokori = K-len(rireki)+1
        ans = nokori % loop_c
        if ans == 0:
            print(rireki[-1])
        else:
            print(rireki[rireki.index(loop)+ans-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

index = 0
keiro = []
s_keiro = set()
loop_f = False

for i in range(k):
  index = al[index] - 1
  if index in s_keiro:
    start = keiro.index(index)
    mod = i - start
    loop_f = True
    break
  s_keiro.add(index)
  keiro.append(index)

if loop_f:
  pos = (k-start-1) % mod
  if mod == 1:
    print(keiro[start]+1)
  else:
    print(keiro[start + pos]+1)
else:
  print(keiro[-1] + 1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
M = list(map(lambda x: int(x)-1, input().split()))
s = 0
order = [s]
sets = set(order)
while True:
  if M[s] in sets:
    #print(order, M[s])
    if len(order) > K:
      print(order[K]+1)
    else:
      K -= order.index(M[s])
      order = order[order.index(M[s]):]
      print(order[(K+1)%len(order)-1]+1)
    break
  order.append(M[s])
  sets.add(M[s])
  s = M[s]

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + a
c = [1]
x = True
y = [1, 1] + [0]*(n-1)

while x:
    c.append(a[c[-1]])
    y[c[-1]] += 1
    if y[c[-1]] == 2:
        x = False

t = c.index(c[-1])
if k <= t:
    ans = c[k]
else:
    ans = c[t + ((k-t) % (len(c)-1-t))]

print(ans)

Submission status: Accepted

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

loopcount=0
tmpPoint=1
vis={1:0}
for i in range(N):
    Next=A[tmpPoint-1]
    if Next in vis:
        startat=i
        #print(startat)
        #print(tmpPoint)
        #print(vis)
        #print(Next)
        #print(vis[Next]+1)
        loopcount=i - vis[Next]+1
        break
    vis[Next]=i+1
    tmpPoint=Next

if loopcount==0:
    print(tmpPoint)
    exit()
if startat+loopcount < K:
    nokori=(K-startat) % loopcount
    K=startat+nokori

tmpPoint=1
for i in range(K):
    Next=A[tmpPoint-1]
    tmpPoint=Next
print(tmpPoint)

Submission status: Accepted

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

now = 1
visited = [-1]*N
visited[0] = 0
for i in range(N+1):
    new = A[now-1]
    if visited[new-1] == -1:
        visited[new-1] = i+1
        now = new
    else:
        f = visited[new-1]
        b = i+1
        break
        
if K <= N:
    now = 1
    for i in range(K):
        new = A[now-1]
        now = new
    print(now)
else:
    k = f + ((K-f)%(b-f))
    now = 1
    for i in range(k):
        new = A[now-1]
        now = new
    print(now)

Submission status: Accepted

Solution code:
def m():
    n, k = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    visited = [[] for _ in range(n + 1)]
    visited[1].append(0)
    cur = 1
    i = 1
    while True:
        cur = a[cur]
        visited[cur].append(i)
        i += 1
        if len(visited[cur]) >= 2:
            break

    if k <= visited[cur][0]:
        now = 1
        for p in range(1, k+1):
            now = a[now]
        return now
    else:
        tmp = k - visited[cur][0]
        MOD = visited[cur][1] - visited[cur][0]
        count = tmp % MOD
        now = 1
        for p in range(1, count+1+visited[cur][0]):
            now = a[now]
        return now


print(m())

Submission status: Accepted

Solution code:
N, K = list(map(int,input().split()))
move_list = list(map(int,input().split()))
 
  
test = 1
find_f = {}
for i in range(N):
  find_f[i+1]=[]
 
find_f[1].append(0)
for i in range(K):
  test = move_list[test-1]
  find_f[test].append(i+1)
  if len(find_f[test]) == 2 and find_f[test][1]-find_f[test][0]<=1000000:
    state ,f = test, find_f[test]
    break
try:
  K = K-f[0]
  f = f[1]-f[0]
  remain = K%f
  for i in range(remain):
    state = move_list[state-1]
 
  print(state)
except:
  print(test)
#state = 1

Submission status: Accepted

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

visited = [0] * (n + 1)
now = 1
check = 2 * n
loop_start = 1
while check > 0:
    if visited[now - 1] == 1:
        loop_start = now
        break
    else:
        visited[now - 1] += 1
        now = a[now - 1]
        check -= 1

visited = [0] * (n + 1)
now = loop_start
check = n
loop = 0
while check > 0:
    if visited[now - 1] == 1:
        break
    else:
        visited[now - 1] += 1
        now = a[now - 1]
        check -= 1
        loop += 1

now = 1
while k > 0:
    if now == loop_start:
        k %= loop
        if k == 0:
            break
    now = a[now - 1]
    k -= 1

print(now)

Submission status: Accepted

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

l = [1]
s = {1}

while True:
    next = list_A[l[-1] - 1]

    if not next in s:
        l.append(next)
        s.add(next)

    else:
        start = l.index(next)
        roop = len(l) - start
        break

if len(l) == 1:
    print(1)
    exit()

elif len(l) > K:
    print(l[K])
    exit()

else:
    roop_remainder = (K + 1 - start) % roop
    if roop_remainder == 0:
        print(l[-1])
    else:
        print(l[start + roop_remainder -1])

Submission status: Accepted

Solution code:
nk = input().split()
n , k = int(nk[0]), int(nk[1])
a = [int(i) for i in 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)]
         
# print(tl)
# print(tl2)

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
def L_search(A,key):
    for i in range(len(A)):
        if A[i] == key:
            return i

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

    Loop_set,Loop_list = set([1]),[1]
    pt = 1 #最初の町
    while True:
        pt = A[pt-1]
        if pt not in Loop_set:
            Loop_set.add(pt)
            Loop_list.append(pt)
        else:
            break

    gosa = L_search(Loop_list,pt)
    shuki = len(Loop_list) - gosa
    if K < gosa:
        print(Loop_list[K])
    else:
        K -= gosa
        K %= shuki
        K += gosa
        print(Loop_list[K])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def q4():
    N, K = [int(i) for i in input().split(" ")]
    A = [-1] + [int(i) for i in input().split(" ")]

    arrived = []
    arrived_set = set()
    current = 1
    loop_start_station = -1
    while True:
        arrived.append(current)
        arrived_set.add(current)
        current = A[current]
        if current in arrived_set:
            loop_start_station = arrived.index(current)
            break

    if K <= loop_start_station:
        print(arrived[K])
        return
    K = K - loop_start_station
    arrived = arrived[loop_start_station:]
    K = K % len(arrived)
    print(arrived[K])
        

q4()

Submission status: Accepted

Solution code:
# D

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

def compute(city, K):
    for i in range(K):
        # print('\t', city)
        city = As[city-1]
    print(city)

cities_visited = [False] * N
i = 0
city = 1
city_visited_time = {}

while not cities_visited[city - 1]:
    # print(city)
    cities_visited[city - 1] = True
    city_visited_time[city-1] = i
    city = As[city-1]
    i += 1

loop_start = city_visited_time[city-1]
loop_end = i


div = (K - loop_start) // (loop_end - loop_start)
if K - loop_start < 0 or div == 0:
    compute(1, K)
else:
    compute(city, K - loop_start - div * (loop_end - loop_start))

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
visit=[False for i in range(n)]
visit[0]=True
looplist=[False for i in range(n)]
mark=-1
i=0
num=0
loop=0
count=0
while True:
  num+=1
  i=a[i]
  if mark<0 and visit[i]:
    mark=a[i]
  else:
    visit[i]=True
  if mark>-1 and looplist[i]:
    count=num-loop*2
    break
  elif mark>-1:
    loop+=1
    looplist[i]=True
if k < count:
  pass
else:
  k-=count
  k%=loop
  k+=count
ans=0
for i in range(k):
  ans=a[ans]
print(ans+1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import sys
sys.setrecursionlimit(4100000)

n,m= map(int,readline().split())
a = list(map(int,readline().split()))

if a[0] == 1:
  print(1)
  exit()
  
d = set([0])
def dfs(now,cc,d):
    if cc == m:
      return now
    else:
      next = a[now]
      next -= 1
      if not next in d:
        d.add(next)
        return dfs(next,cc+1,d)
      else:
        d = list(d)
        for i,di in enumerate(d[::-1]):
          if di == next:
            return (i+1,cc,now)

def f(now,cc):
    global mar
    if cc == mar:
      return now
    else:
      next = a[now]
      next -= 1
      return f(next,cc+1)
    
res = dfs(0,0,d)
if type(res) == int:
  print(res+1)
else:
  m -= res[1]
  mar = m % res[0]
  print(f(res[2],0)+1)

Submission status: Accepted

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

T = {0: 0}

for i in range(N):
    T.update({i + 1: A[i]})

i = 1

MOD_ = 0

VISIT = [0] * (N+1)

for j in range(K):
    i = T[i]

    if VISIT[i] != 0:
        K0 = VISIT[i] 
        MOD_ = j+1 - VISIT[i] 
        break

    VISIT[i] = j+1


if MOD_ !=0:
    i = T[i]
    if ((K - K0 - 1) % MOD_ ) != 0:
        for j in range((K-K0-1) % MOD_ ):
            i = T[i]


print (i)

Submission status: Accepted

Solution code:
l = [int(x) for x in input().split()]
n = l[0]
k = l[1]
pos = 1

go = [int(x) for x in input().split()]
ref = {}

#[first find, second find]

i = 0

while i < k:
    pos = go[pos-1]
    i = i+1

    if pos in ref:
        if ref[pos][1] == -1:
            ref[pos][1] = i
        else:
            temp = ref[pos][1] - ref[pos][0]
            tempy = ((k-i)//temp)*temp
            i = i + tempy

    else:
        ref[pos] = [i, -1]

print(pos)

Submission status: Accepted

Solution code:
N,K=list(map(int,input().split()))
s=[0]*N
src=list(map(int,input().split()))
x=0
y=0
z=-1
ind=1
for i in range(K):
  q=src[ind-1]
  s[ind-1]+=1
  if s[ind-1]==1:
    x+=1
    ind=q
  elif s[ind-1]==2:
    y+=1
    ind=q
  elif s[ind-1]==3:
    z+=1
    break
if z==-1 and y==0:
  print(ind)
  exit()
elif z==-1 and y!=0:
  print(ind)
  exit()
else:
  p=x-y
  K-=p
  K%=y
  if K==0:
    print(ind)
    exit()
  for k in range(K):
    q=src[ind-1]
    ind=q
  print(q)

Submission status: Accepted

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

d = {}
s_list = []
count = 0
idx = 1
while count < N:
    idx = a[idx-1]
    if idx in d.keys():
        break
    else:
        d[idx] = count
    s_list.append(idx)
    count += 1
loop_idx = len(s_list) - d[idx]

if d[idx] > K:
    print(s_list[K-1])
elif loop_idx != 0:
    t_idx = (K - d[idx])% loop_idx
    print(s_list[d[idx]:][t_idx-1])
else:
    t_idx = K % N
    print(s_list[t_idx-1])

Submission status: Accepted

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

    visited_town = []
    current_town = 0
    loop_flg     = False
    visited_town.append(current_town)
    set_visted_town = set(visited_town)
    for i in range(K):
        current_town = A[current_town]
        if current_town in set_visted_town:
            visited_town.append(current_town)
            loop_flg = True
            break
        visited_town.append(current_town)
        set_visted_town.add(current_town)


    if loop_flg:
        loop_start = visited_town.index(current_town)
        loop_end   = len(visited_town) - 1
        loop_length = loop_end - loop_start
        last_index = (K-loop_start)%loop_length
        current_town = visited_town[loop_start+last_index]

    print(current_town+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n = 0
loc = 1
flag_visit = [-1]*N
flag_when = [-1]*N
flag_visit[0] *= -1
flag_when[0] = 0
move_hist = [1, ]
while 1:
    loc = A[loc-1]
    move_hist.append(loc)
    n += 1
    if flag_visit[loc-1] == -1:
        flag_visit[loc-1] *= -1
        flag_when[loc-1] = n
    else:
        m = flag_when[loc-1]
        break
if K > m:
    print(move_hist[m+(K-m) % (n-m)])
else:
    print(move_hist[K])

Submission status: Accepted

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

result = 1
L = 2
current = A[0]
visited = [0] * N
visited_loop_cnt = 1
flag = True

while L < K:
    if visited[current - 1] == 3:
        J = K - L
        J %= visited_loop_cnt
        K = L + J
    elif visited[current - 1] == 2 and flag:
        visited[current - 1] += 1
        visited_loop_cnt = 1
        flag = False
    else:
        visited[current - 1] += 1
        visited_loop_cnt += 1
    current = A[current - 1]
    L += 1

print(A[current - 1])


# 同じところに来た場合、そのループ分だけ減らす必要がある。
# 1 6 2 5 3 2 5 3 2 5

Submission status: Accepted

Solution code:
def main():
    n, k = [int(x) for x in input().split()]
    teleporter = [int(x) - 1 for x in input().split()]
    route = []
    route_append = route.append
    seen = [False] * n
    traveled, now_i = 0, 0

    while True:
        if seen[now_i]:
            # テレポートがループしたら，ルート調査は終了する。
            break
        route_append(now_i)
        seen[now_i] = True
        now_i = teleporter[now_i]
        traveled += 1

    # 調査終了後，now_1 はループ部分の頭。ループ前にイントロがある。
    # ループ頭は何番目に尋ねるか？
    intro_length = route.index(now_i)
    loop_length = len(route) - intro_length
    if k >= intro_length:
        arriving_i = intro_length + (k - intro_length) % loop_length
    else:
        # k が イントロ内に収まる場合。ここを見落としてWA連発！
        arriving_i = k
    return route[arriving_i] + 1


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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(100000000)

stp = -1 
def main():
    n, k = map(int, readline().split())
    a = [int(i)-1 for i in readline().split()]

    order = []
    ex = set()
    def dfs(node):
        global stp
        order.append(node)
        ex.add(node)
        nx = a[node]
        if nx in ex:
            stp = nx
            return
        dfs(nx)
    dfs(0)

    cnt = order.index(stp)
    if k < cnt:
        print(order[k]+1)
    else:    
        m = len(order[cnt:])
        idx = (k-cnt)%m
        print(order[cnt:][idx]+1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
adj_list=[0]*N
for i in range(N):
    adj_list[i]=(A[i])
k=0
node = 1
c=[0]*N
count=1
flag=0
ROOP=[]
roopstart=0
while k<K:
    k+=1
    c[node-1]+=1
    node = adj_list[node-1]
    if c[node-1] ==1:
        if flag ==0:
            roopstart = k
            flag=1
        ROOP.append(node)
    if c[node-1] ==2:
        break
l = len(ROOP)
if l != 0:
    num = (K-l-roopstart) % (l)
    print(ROOP[num])
else:
    print(node)