提出 d7b7cfd6-4e27-481e-acfe-6b01c9c47fa3

コード

import math
import bisect
import collections
import heapq
#import sys
#import decimal
#import random

def main():
    n,q = map(int,input().split())
    logk = 30
    # C++の解説のinputに相当する
    get = 0
    doubling = [[-1]*n for i in range(logk)]
    fill = [[]]*(logk * n)
    dist = [-1]*n
    ex = 1
    unknown = 0
    for _ in range(q):
        case, x, y = map(int,input().split())
        if case == 1:
            x -= 1
            y -= 1
            if (doubling[0][x] == y):
                continue
            get += 1
            doubling[0][x] = y
            que = collections.deque()
            que.append(logk * x)
            while que:
                a = que[0] % logk
                b = que[0] // logk
                que.pop()
                if a != 0:
                    doubling[a][b] = doubling[a-1][doubling[a-1][b]]
                if doubling[a][b] == -1:
                    fill[logk * doubling[a-1][b] + a - 1].append(logk * b + a)
                    continue
                elif a == logk - 1:
                    continue
                que.append(logk * b + a + 1)
                for i in fill[logk * b + a]:
                    que.append(i)
            if get == n - 1:
                rev = [[]]*n
                next = collections.deque()
                for i in range(n):
                    if doubling[0][i] == -1:
                        unknown = i
                    else:
                        rev[doubling[0][i]].append(i)
                next.append(unknown)
                dist[unknown] = 0
                while next:
                    # C++の解答のgoto文を再現するための真偽値
                    tf = False
                    for i in rev[next[0]]:
                        if dist[i] > -1:
                            dist[i] = -1
                            tf = True
                            break
                        dist[i] = dist[next[0]] + 1
                        next.append(i)
                    if tf:
                        break
                    next.pop()
                maxi = 0
                for i in dist:
                    if i < 0:
                        maxi = 200000
                    maxi = max(maxi,i)
                for i in range(maxi+1):
                    ex = math.lcm(ex, i + 1)
                    if ex > 1000000000:
                        break
        else:
            x -= 1
            if (get == n - 1) and (y > dist[x]) and ((y - dist[x]) % ex == 0):
                print(unknown + 1)
                continue
            now = x
            cnt = 0
            while y > 0:
                if y % 2 == 1:
                    now = doubling[cnt][now]
                if now == -1:
                    break
                cnt += 1
                y //= 2
            if now == -1:
                now -= 1
            print(now + 1)
    return

main()

結果

問題	点数	言語	結果	実行時間	メモリ
S. Association	0	Python3 (CPython)	TLE	6162 ms	10112 KiB

テストセット

テストセット	結果	実行時間	メモリ
testcase1	AC × 2 TLE × 18	6162 ms	10112 KiB
testcase2	AC × 1 TLE × 11	6162 ms	10112 KiB
testcase3	AC × 2 TLE × 33	6162 ms	10112 KiB

詳細結果

テストケース	結果	実行時間	メモリ
sub1sub2sub3_hand_01.txt	AC	33 ms	10112 KiB
sub1sub2sub3_hand_02.txt	TLE	6018 ms	8192 KiB
sub1sub2sub3_hand_03.txt	TLE	6049 ms	8448 KiB
sub1sub2sub3_random_01.txt	TLE	6162 ms	7808 KiB
sub1sub2sub3_random_02.txt	TLE	6081 ms	8192 KiB
sub1sub2sub3_random_03.txt	TLE	6154 ms	7680 KiB
sub1sub3_corner_01.txt	AC	30 ms	10112 KiB
sub1sub3_corner_02.txt	TLE	6018 ms	8192 KiB
sub1sub3_corner_03.txt	TLE	6049 ms	8320 KiB
sub1sub3_corner_04.txt	TLE	6017 ms	8192 KiB
sub1sub3_corner_05.txt	TLE	6136 ms	7808 KiB
sub1sub3_corner_06.txt	TLE	6123 ms	7808 KiB
sub1sub3_corner_07.txt	TLE	6083 ms	8064 KiB
sub1sub3_example_01.txt	TLE	6036 ms	8192 KiB
sub1sub3_example_02.txt	TLE	6019 ms	8192 KiB
sub1sub3_hand_04.txt	TLE	6077 ms	7936 KiB
sub1sub3_hand_05.txt	TLE	6072 ms	8192 KiB
sub1sub3_random_04.txt	TLE	6094 ms	7936 KiB
sub1sub3_random_05.txt	TLE	6088 ms	8448 KiB
sub1sub3_random_06.txt	TLE	6082 ms	7936 KiB
sub2sub3_max_01.txt	TLE	6055 ms	8192 KiB
sub2sub3_max_02.txt	TLE	6051 ms	8320 KiB
sub2sub3_max_03.txt	TLE	6055 ms	8064 KiB
sub2sub3_random_07.txt	TLE	6054 ms	8192 KiB
sub2sub3_random_08.txt	TLE	6055 ms	8192 KiB
sub2sub3_random_09.txt	TLE	6053 ms	8192 KiB
sub3_corner_08.txt	TLE	6052 ms	8192 KiB
sub3_corner_09.txt	TLE	6053 ms	8192 KiB
sub3_corner_10.txt	TLE	6058 ms	7936 KiB
sub3_max_04.txt	TLE	6057 ms	8448 KiB
sub3_max_05.txt	TLE	6055 ms	8448 KiB
sub3_max_06.txt	TLE	6060 ms	8064 KiB
sub3_random_10.txt	TLE	6057 ms	8064 KiB
sub3_random_11.txt	TLE	6056 ms	7936 KiB
sub3_random_12.txt	TLE	6057 ms	8064 KiB