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: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    N, K = [int(item) for item in input().split()]
    A_list = [int(item) for item in input().split()]
    order_dict = dict(zip(range(1,N+1),A_list))

    foot_print = []

    goto = 1
    for i in range(N):
        if goto in foot_print:
            break
        else:
            foot_print.append(goto)
            goto = order_dict[goto]

    if K > len(foot_print):
        foot_print2 = []
        for i in range(N):
            if goto in foot_print2:
                break
            else:
                foot_print2.append(goto)
                goto = order_dict[goto]



        temp_num = K -len(foot_print)
        temp_num = temp_num % len(foot_print2)
        for i in range(temp_num):
            goto = order_dict[goto]

    print(goto)
if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

ans = deque()
ans.appendleft(1)
count = 1
s = -1

while True:
    if a[count-1] in a[:count-1]:
        s = a[count-1]
        ans = a[:count-1]
        break
    else:
        count = a[count-1]

if s == -1:
    print(ans[k-1])
else:
    t = ans.index(s)
    if t >= k:
        print(ans[k-1])
    else:
        ans = ans[t-1:]
        print(ans[(k-t)%len(ans)])

Submission status: Wrong Answer

Solution code:
import sys
stdin=sys.stdin

ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))

N,K=nm()
A=nl()

city_l=[]
city_l.append(1)
city_c=[0]*(N+1)
city_c[1]+=1
n_city=A[0]
flag=True
r_start=-1
r_end=-1
while(flag):
    city_c[n_city]+=1
    city_l.append(n_city)
    if(city_c[n_city]>1):
        r_start=city_l.index(n_city)+1
        r_end=len(city_l)-1
        flag=False
    n_city=A[n_city-1]

if(K<r_end):
    print(A[city_l[K-1]])


else:
    K2=K-r_end
    K2=K2%(r_end-r_start+1)
    if(K2==0):
       print(A[city_l[r_end-1]-1])
    else:
       print(A[city_l[r_start+K2-2]-1])

Submission status: Wrong Answer

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


def readstr():
    return input().strip()


def readint():
    return int(input())


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


def readstrs():
    return input().split()


def main():
    N, K = readnums()
    A = list(readnums())
    '''
    setでinを回したい
    -> l = set()
    順序も保持したい
    dictで保持？
    {1: 0, 3: 1, 4: 2, 1: 3, ...}
    a in l = Trueのとき
    dict[a]
    '''
    l = {A[0]}
    dic = {A[0]: 0}
    a = A[0]
    for i in range(1, N):
        a = A[a - 1]
        if a in l:
            d = dic[a]
            loop = list(dic.keys())[d:]
            K -= d
            print(loop[K % len(loop) - 1])
            break
        else:
            l.add(a)
            dic[a] = i
    else:
        print(list(dic.keys())[-1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
a=input().split()
N=int(a[0])
K=int(a[1])
c=input().split()
list1=[]
for i in range(N) :
  list1.append([i+1,int(c[i])])

current_num_list=[1]
current_num=1
for item in list1:
  if item[0] == current_num:
    current_num_list.append(item[1])
    current_num = item[1]
    break

while(current_num not in current_num_list[:-1]):
  for item in list1 :
    if item[0]==current_num :
      current_num_list.append(item[1])

      current_num=item[1]
      break



c=len(current_num_list)
first_index=0
for i in range(c) :
  if current_num_list[i]==current_num :
    first_index=i
    break


index=(K+1-first_index)%(c-first_index)+first_index
print(current_num_list[index])

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    if a[0] == 1:
        print(1)
        exit()
    visit = [-1] * n
    start = 1
    tmpa = 0
    while visit[start - 1] != 1:
        visit[start - 1] = 1
        start = a[start - 1]
        tmpa += 1
    visit = [-1] * n
    #この時点ですでに周期点からのスタート
    T = 0
    while visit[start - 1] != 1:
        visit[start - 1] = 1
        start = a[start - 1]
        T += 1
    if (n) % T == 0:
        print(start)
        exit()
    else:
        for i in range((k - tmpa) % T):
            start = a[start - 1]
    print(start)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Wrong Answer

Solution code:

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

map = {}
for i in range(N):
    map[i+1] = A[i]

visited = {}
note = []
locate = 1
visited[1] = True
note.append(A[0])

i = 1
skippedFlg = False
while True:
    locate = map[locate]
    if locate in visited and not skippedFlg:
        # print("visitted!")
        diff = 0
        for j in range(len(note)-1,-1,-1):
            diff += 1
            if note[j] == locate:
                break

        i = i - diff + ( diff * (K // diff))
        skippedFlg = True
    else:
        visited[locate] = True
        note.append(locate)

    i += 1
    if i > K:
        break

print(locate)

Submission status: Wrong Answer

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

flag=[0]*n
place=[0]*n
p=0
for i in range(len(a_list)+1):
    if flag[p]>0:
        rep=i
        replis=place[flag[p]-1:i]
        st=p+1
        break
        
    else:
        place[i]=p+1
        flag[p]=i+1
        p=a_list[p]-1


if i<k:
    print(replis[(k-st-len(replis))%len(replis)])
else :
    print(place[k])

Submission status: Wrong Answer

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

s = 0
seen = [False for _ in range(n+1)]
d = [0]
cy = -1
for _ in range(n+1):
    seen[s] = True
    s = a[s]-1
    if seen[s]:
        cy = s
        break
    d.append(s)

if cy == -1:
    print(d[k-1])
    exit()

if cy == -1:
    print(d[k-1])
    exit()

noncyi = d.index(cy)
cyi = len(d) - noncyi
if k <= noncyi:
    print(d[k-1])
else:
    k -= noncyi
    print(d[noncyi + k%cyi]+1)

Submission status: Wrong Answer

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

ans = A[0]

d = {0:1, ans -1:1}
#移動する可能性がある街の個数uを出す
for i in range( 2 *N + 1):
  #print(ans)
  ans = A[ans - 1]
  if ans -1 not in d:
    d[ans -1] = 1
  else:
    d[ans - 1] += 1
  
#print("d", d, len(d))
u = len(d)

cnt_ = 0
#1回しかこない地点は何個
for i in d.values():
  if i == 1:
    cnt_ += 1

if cnt_ != 0:
  u = u - cnt_
  a = (K - cnt_) % u
  
  ans = A[0]
  for i in range(cnt_):
    ans = A[ans - 1]

else:
  a = K % u
  ans = A[0]
  
if a == 0:
  a = u

#print("a", a)

for i in range(a - 1):
  #print(i, ans)
  ans = A[ans - 1]
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
d = dict()
for i, a in enumerate(input().split()):
    d[i+1] = int(a)

a = []
j = 1
for k in range(K):
    j = d[j]
    if j in a:
        hh = a.index(j)
        aaa = (K - k) % (k - hh)
        print(a[hh + aaa - 1])
        exit()
    else:
        a.append(j)

Submission status: Wrong Answer

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


loop_find_list_ = []
loop_point = -1

dp = [0] * (2 * 10**5 + 1)
dp[1] = data[1 - 1] # 1番目埋め
loop_find_list_.append( dp[1] )

for k_ in range(2, k+1):
  dp[k_] = data[dp[k_ - 1] - 1]
  if dp[k_] in loop_find_list_:
    # print("検出したので終了します")
    loop_point = dp[k_]
    break
  else:
    loop_find_list_.append( dp[k_] )

if k <= len(loop_find_list_):
  print(loop_find_list_[k - 1])
else:
  idx = loop_find_list_.index(loop_point)
  len_ = len(loop_find_list_)
  loop_len_ = len_ - idx

  real_loop_list_ = loop_find_list_[idx:]
  k = k % loop_len_
  print(real_loop_list_[k])

Submission status: Wrong Answer

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 - div * (loop_end - loop_start) < 0 or div == 0:
    compute(1, K)
else:
    compute(city, K - loop_start - div * (loop_end - loop_start))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
town = {}
for i in range(n):
    town[i+1] = [a[i], 0, 0, i+1]
temp = town[1]
count = -1
while k != 0:
    count += 1
    if temp[1] == 1:
        loop_size = count-temp[2]
        mod = k % loop_size
        while mod != 0:
            temp = town[temp[0]]
        print(temp[3])
        break
    temp[1] = 1
    temp[2] = count
    if k == 0:
        print(temp[3])
        break
    k -= 1
    temp = town[temp[0]]

Submission status: Wrong Answer

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

#ループする場合
flag=[0]*N
patt=[]
aaaa=0
i=0
while True:
    patt.append(i)
    if flag[i]==1:
        #del patt[-1]
        break
    flag[i]=1
    i=A[i]-1


srt = patt.index(patt[-1])
#print('srt',srt)
end = len(patt)-2
ptrn = patt[srt:end+1]

if K<len(ptrn):
    print(patt[K-1]+1)
else:
    B = (K-srt) % len(ptrn)
    #print('B',B)

    print(ptrn[B]+1)
    #print('0000000')

    #print('ptrm',ptrn)
    #print(patt)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k = map(int,input().split())
line = list(map(int,input().split()))
d = deque()

d.append(line[0])
count = 1
for i in range(2*n):
  p=d.pop()
  d.append(line[p-1])
  count += 1
  if p-1 == 1:
    break
nk = k%count
for i in range(nk):
  p=d.pop()
  d.append(line[p-1])
print(d.pop())

Submission status: Wrong Answer

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

S = "1"
i = 1
while not Visited[i-1]:
    Visited[i-1] = True
    i = A[i-1]
    S += str(i)

# print (S)
pos = S.find(S[-1])
# print (pos)

# print (K % 1000000.0)
K -= float(pos)
S = S[pos:-1]
# print (S)
# print (K % 1000000.0)

ansp = int(K % float(len(S)))
# print ansp
print (S[ansp])

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
A = list(map(int, input().split()))
A.insert(0, 0)
root = [0 for i in range(N + 1)]
root[1] = 1
now = A[1]
roop = 0
getroop = 0
startroop = -1
mae_now = -1
for j in range(K):
    root[now] += 1
    if root[now] == 3:
        startroop = now
        break
    if root[now] == 2:
        roop += 1
    if root[now] == 1:
        getroop += 1
    mae_now = now
    now = A[now]
if startroop == -1:
    print(mae_now)
if startroop != -1:
    nokoriroop = (K+(getroop-roop)) % roop
    for i in range(nokoriroop):
        now = A[now]
    print(now)

Submission status: Wrong Answer

Solution code:
def get_town(towns, n):
  return towns[n-1]

def write_memo(memo, towns, n):
  tmp = get_town(towns, n)
  memo.append(tmp)

def read_memo(memo, towns, n):
  tmp = get_town(towns, n)
  if tmp in memo:
    idx = memo.index(tmp)
    return idx
  return -1

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

tmp_K = K

memo = []

place = 1
before_place = 1
score = 0
size = 0
pre_size = 0

while(True):
  tmp_K = tmp_K - 1
  score = score + 1
  if read_memo(memo, towns, place) >= 0:
    
    size = score - read_memo(memo, towns, place)
    #print('read:{}'.format(read_memo(memo, towns, place)))
    pri_size = len(memo) - size
    place = get_town(towns, place)
    #print('score: {}'.format(score))
    break

  else:
    write_memo(memo, towns, place)
    before_place = place
    place = get_town(towns, place)
  # print('next: {}'.format(place))

  if tmp_K <= 0:
    print(place)
    exit()
  

#print(memo)


tmp_K = K
tmp_K = K - pre_size
tmp_K = tmp_K % size

#print('pre: {}, size: {}, tmp_K: {}'.format(pre_size, size, tmp_K))

if tmp_K == 0:
  print(before_place)

else:

  while(True):
    tmp_K = tmp_K - 1
    place = get_town(towns, place)
    
    if tmp_K <= 0:
      print(place)
      exit()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A_list =  list(map(int, input().split()))
A_list
toutatul = [0]*N
next_jump = 0
before =-1
toutatul[0] =1
asibumi =False
asibumitown =0
roop_start = 0
roop_end =0
roop_count =0
for x in range(len(A_list)):
    A_list[x] = A_list[x]-1
for x in range(N):
    before = next_jump
    next_jump = A_list[next_jump]
    
    toutatul[next_jump] =1
    if next_jump == before:
        asibumi =True
        asibumitown = next_jump
        break
    if toutatul[next_jump] ==1:
        roop_start =next_jump
        roop_end =before
        roop_count =x+1
        break
next_jump = 0
before =0

if asibumi:
    if N<K:
        ans =asibumitown
    else :
        for x in range(K):
            before = next_jump
            next_jump = A_list[next_jump]

        ans = next_jump
else :
    if N<K:
        next_jump = roop_start
        roop_long = 0
        for x in range(roop_count):
            if next_jump ==roop_end:
                break
            next_jump = A_list[next_jump]
            roop_long +=1
        move = (K-roop_count)%roop_long+1
        next_jump = roop_start
        for x in range(move):
            before = next_jump
            next_jump = A_list[next_jump]
            
        ans = next_jump 
    else :
        for x in range(K):
            before = next_jump
            next_jump = A_list[next_jump]

        ans = next_jump
print(ans+1)

Submission status: Wrong Answer

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[-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: Wrong Answer

Solution code:
from sys import stdin
N,K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]

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

tmp = [0]*(N+1)
cnt = 1
zyunkai = 0
idou = A[0]
tmp[idou] = 1
A = [0] + A
ans = [0]*(N+1)
ans[1] = A[1]

cook = 0
for i in range(N):
   
    cnt += 1
    ans[cnt] = A[idou]
    idou = A[idou]
    if visited[idou]:
        zyunkai = cnt - tmp[idou]
        cook = tmp[idou]
        K -= tmp[idou]
        break
    tmp[idou] = cnt
    visited[idou] = True

ooo = (K-cook)%zyunkai
#print(zyunkai,cook)
ans = ans[ooo]
print(ans)

Submission status: Wrong Answer

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])
    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: Wrong Answer

Solution code:
n,k=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
x=set(range(1,n+1))
dic=dict.fromkeys(x,0)
for i in x:
    dic[i]=l[i-1]
l=[-1]*n
curr=1
x=0
while x<=k:
    if l[curr-1]==-1:
        l[curr-1]=x
        x+=1
        continue
    else:
        #if l[curr-1]==0:
        l[curr-1]=x
    x=k-((k-x)%l[curr-1])*l[curr-1]
    #print(x)
    curr=dic[curr]
    x+=1
print(dic[curr])

Submission status: Wrong Answer

Solution code:
def detectCycle(a):
    start, length = 0, 1
    p1, p2 = a[1], a[a[1]]
    while p1 != p2:
        p1, p2 = a[p1], a[a[p2]]
    
    p2 = 1
    while p1 != p2:
        p1, p2 = a[p1], a[p2]
        start += 1
    
    p2 = a[p1]
    while p1 != p2:
        p2 = a[p2]
        length += 1
    
    return start, length

n, k = (int(x) for x in input().split())
a = [-1] + [int(x) for x in input().split()]
start, length = detectCycle(a)

loc = 1
k -= start+1
for i in range(start+1):
    loc = a[loc]

k %= length
for i in range(k):
    loc = a[loc]
print(loc)

Submission status: Wrong Answer

Solution code:
import sys
stdin=sys.stdin

ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))

N,K=nm()
A=nl()

city_l=[]
city_l.append(1)
city_c=[0]*(N+1)
city_c[1]+=1
n_city=A[0]
flag=True
r_start=-1
r_end=-1
while(flag):
    city_c[n_city]+=1
    city_l.append(n_city)
    if(city_c[n_city]>1):
        r_start=city_l.index(n_city)+1
        r_end=len(city_l)-1
        flag=False
    n_city=A[n_city-1]

if(K<=r_end):
    print(A[city_l[K-1]])


else:
    K2=K-r_end
    K2=K2%(r_end-r_start+1)
    if(K2==0):
       print(A[city_l[r_end-1]-1])
    else:
       print(A[city_l[r_start+K2-2]-1])

Submission status: Wrong Answer

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

rec = [0] * (N + 1)
costs = [0] * (N + 1)

loc = 1
rec[loc] = 1

finished = True
for i in range(1, K+1):
    next_loc = A[loc-1]

    if rec[next_loc] == 1:
        finished = False
        break

    costs[next_loc] = i
    rec[next_loc] = 1
    loc = next_loc

if finished:
    print(i)
else:
    loop_index_cost = costs[next_loc]
    loop_cost = i - loop_index_cost

    final_loc = costs.index((K - loop_index_cost) % loop_cost + loop_index_cost)
    print(final_loc)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

route = [1]

end = False
i = 0

if a[0] == 1:
    ans = 1
else:
  while not end:
    if a[i] not in route:
      route.append(a[i])
      i = a[i] -1
      # route[1].append(1)
    else:
      position = route.index(a[i])
      # print(position)
      break
    if len(route) == n:
      overhead = 0
      end = True

  overhead = position
  cycle_length = len(route) - overhead

  # print(route)
  # print(overhead)
  # print(cycle_length)

  end_position = (k-overhead) % cycle_length
  # print(end_position)

  ans = route[overhead + end_position]

print(ans)

Submission status: Wrong Answer

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main(n, k, a):
    ck=[-1]*n
    tak=0
    c=0
    ck[0]=c
    for i in range(n):
        c+=1
        tak=a[tak]-1
        if ck[tak]!=-1:
            loop=c-ck[tak]
            lps=ck[tak]
            break
        ck[tak]=c
    print(ck, loop, lps)

    tak=0
    for i in range((k-lps)%(loop)+lps):
        tak=a[tak]-1

    print(tak+1)


if __name__ == '__main__':
    n,k=map(int, input().split())
    a=list(map(int, input().split()))
    main(n, k, a)

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, k = i_map()
    num_list = i_list()

    trans_list = [0] * n

    next_trans = num_list[0]

    for i in range(n):
        trans_list[i] = next_trans
        next_trans = num_list[next_trans-1]

    tras_index = k % (n-1)

    if tras_index == 0:
        tras_index = 1

    print(trans_list[n-tras_index-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

n,k = (int(i) for i in input().split())

a = [int(i)-1 for i in input().split()]

hantei = [True]*(n+1)
otozure = [None]*(n+1)
mokuteki = a[0]
moto = k
kazoe = 0
otozure[0] = 0
while k>0:
        
    if hantei[mokuteki] == False: #二週目突入
       # print("break\nmokuteki= {}\nk = {}".format(mokuteki,k))
        otozure[kazoe+1] = mokuteki
        saigo = otozure
        break

    else:
        hantei[mokuteki]= False
        otozure[kazoe+1] = mokuteki#今いるところを記憶
       # print(otozure[kazoe])
        mokuteki = a[mokuteki]#次に行くところ
        kazoe+=1
    k-=1
else:
    print(otozure[kazoe-2]+1)
    sys.exit()
i = 0
while True:
    if otozure[kazoe+1] == otozure[kazoe-i]:
        break
    i+=1


nokori = k%(i+1)
#print(nokori)
i=0
while otozure[i] != mokuteki:
    i+=1

if a[0]==0:
    print("1")
else:
    print(otozure[i-1+nokori]+1)

Submission status: Wrong Answer

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

a.append(1)
buf = [x for x in set(a) if a.count(x) > 1]
buf_cnt = {}
for i in buf:
    buf_cnt[str(i - 1)] = 0


cnt = 0
now = 1
transition = []

while True:
    if now in buf:
        buf_cnt[str(now - 1)] += 1
        if buf_cnt[str(now - 1)] == 2:
            transition.append(now)
            key = now
            break
    transition.append(now)
    now = a[now - 1]
    cnt += 1


p = [i for i, j in enumerate(transition) if j == key]

buf2 = k - p[0] 
amari = buf2 % (p[1] - p[0])
kasou = transition[p[0]: -1]
ans = kasou[amari]
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
 
A = [int(x) for x in input().split()]
 
here = 1
towns = [0 for i in range(n)]
cnt = 0
while(True):
  towns[cnt] = here
  next_town = A[here-1]
  here = next_town
  cnt += 1
  if here in towns:
    towns[cnt] = here
    cnt += 1
    break
  
start = towns.index(towns[-1])
    
if k <= start:
  print(towns[k])
else:
  idx = (k - start) % (cnt-1-start) + start
  print(towns[idx])

Submission status: Wrong Answer

Solution code:

N,K = map(int, input().split())
Line = [int(s) for s in input().split()]

X = [-1]*N

# print(X)
ikisaki = Line[0]
X[0] = 0

# print(ikisaki)

for i in range(N+1):
    if X[ikisaki-1] == -1:
        X[ikisaki-1] = i + 1
        ikisaki = Line[ikisaki-1]
    else:
        warukazu = i+1 - X[ikisaki-1]
        saisyo = X[ikisaki-1]
        break
    # print(X)
# print(saisyo)
# print(warukazu)
Z = K%warukazu
# print(Z)
if saisyo >= K:
    print(X.index(K)+1)
else:
    print(X.index(Z)+1)

Submission status: Wrong Answer

Solution code:

#import numpy as np
from functools import *
import sys
sys.setrecursionlimit(300000)
input = sys.stdin.readline




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




def search(x,step,vnode):
    global L,visited,K
    
    #print(visited,x)
    #print(step)
    visited[x]=step
    vnode.append(x)
    
                
    if L[x]==x:
        print(x)
        sys.exit(0)
        
    if visited[L[x]]>=0:
        C=step+1-visited[L[x]]
        k=(K%(2*C)-visited[L[x]])%C
        if k<0:
            k=(k+C)%C
            
        #print(vnode)
        #print(k,L[x],visited[L[x]])
        vnode.append(L[x])
        print(vnode[visited[L[x]]+k])
               
        #print(step,x,visited)
        sys.exit(0)
        return
    
    if step==K:
        print(step)
        #print(visited)
        sys.exit(0)            
    
    search(L[x],step+1,vnode)
    
    
    

N,K=acinput()
L=[0]
L.extend(acinput())

visited=[-1]*(N+1)
#visited[1]=1
search(1,0,[])

#4 500000000000000000000000001
#2 3 4 4

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
d = [0]*N
d[0] = a[0]
for i in range(1,N):
  d[i] = a[a[i-1]-1]

if 0 < K % N < N:
  ans = d[K % N] 
else:
  ans = d[N]

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().strip().split()))
B=1
list=[]
for i in range(K-1):
    B=A[(A[B-1])-1]
    if B in list:
        break
    else:
        list.append(B)
num=K%len(list)
if num-2<0:
    num+=len(list)
    
print(list[num-2])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[1]
t=0
for i in range(n):
    for j in range(len(b)):
        if b[j]==a[b[i]-1]:
            r=j
            t=1
            break
    if t==1:
        break
    b.append(a[b[i]-1])
b1=b[:r]
b2=b[r:]
print(b1)
print(b2)
print(r)
if k<=r:
    print(b1[k-1])
else:
    print(b2[((k-r+1)%len(b2)+len(b2))%len(b2)-1])

Submission status: Wrong Answer

Solution code:
import sys
n,k=map(int,input().split())
alist=list(map(int,input().split()))

vislist=[1]
visset={1}
loopflag=True
endflag=False
donek=0
ima=1

while loopflag:
    ima=alist[ima-1]
    if ima in visset:
        loopflag=False
        if ima == alist[ima-1]:
            endflag=True
        elif donek==k-1:
            endflag=True
    else:
        vislist.append(ima)
        visset.add(ima)

        donek+=1

        if donek == k:
            loopflag=False
            endflag=True

if endflag:
    print(ima)
    sys.exit()

loopstartindex=vislist.index(ima)
looplength=len(visset)-loopstartindex
print(vislist[loopstartindex+(k+1-loopstartindex)%looplength-1])

Submission status: Wrong Answer

Solution code:
DEBUG = False

import time

N, K = map(int, input().split())
A = [int(i)-1 for i in input().split()]

visited = [False] * N
next = A[0]
visited[0] = True
K -= 1
count = 1
while not visited[next]:
    if DEBUG:
        print("next: {}".format(next))
        print("visited: {}".format(visited))
        time.sleep(0.1)
    if K == 0:
        print(next+1)
        exit()
    visited[next] = True
    next = A[next]
    K -= 1
    count += 1

K -= 1
count += 1
now = next

K %= count

if DEBUG:
    print("now: {}, count: {}, K: {}".format(now, count, K))

while K > 0:
    if DEBUG:
        print("now: {}".format(now))
    now = A[now]
    K -= 1

print(A[now]+1)

Submission status: Wrong Answer

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


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

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

    step = 0
    current = 1

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

    #print(n1, n2)
    #print(n1-1, ((K-(n1-1))%n2))

    print(seq[n1-1+((K-(n1-1))%n2)])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

N, K = map(int, input().split())
dist = [[] for i in range(N)]
A = list(map(int, input().split()))
for i in range(N):
    dist[i].append(A[i] - 1)
dp = [[0, 0] for i in range(N)]

def dfs(pos, depth):
    # 初めての訪問なら
    if dp[pos][0] == 0:
        dp[pos][0] = depth
        for i in dist[pos]:
            dfs(i, depth + 1)
    elif dp[pos][1] == 0:
        dp[pos][1] = depth
        for i in dist[pos]:
            dfs(i, depth + 1)
dfs(0, 0)
for i in range(N):
    if dp[i][0] == K or dp[i][1] == K:
        print(i + 1)
        break
    else:
        split = dp[i][1] - dp[i][0]
        if split > 0:
            if (K - dp[i][0]) % split == 0:
                print(i + 1)
                break

Submission status: Wrong Answer

Solution code:
no_towns, no_moves = list(map(int, input().split()))

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


pos = moves[0]
chain_len = len(set(moves))-1
current_pos = moves[0]
if no_moves < chain_len:
    while no_moves > 0:
        current_pos = moves[current_pos-1]
        no_moves -= 1
    print(current_pos)
else:
    chain = [moves[min(moves)-1]]
    while len(chain) < chain_len+1:
        pos = moves[pos-1]
        chain.append(pos)
    chain = chain[1:]

    current_pos = moves[0]
    while current_pos != chain[0]:
        current_pos = moves[current_pos-1]
        no_moves -= 1

    extra_pos = no_moves % chain_len

    if extra_pos > 0:
        current_pos = chain.pop()
        for i in range(extra_pos):
            current_pos = moves[current_pos-1]

    print(current_pos)