結果

問題 No.515 典型LCP
ユーザー gew1fw
提出日時 2025-06-12 12:54:52
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,226 bytes
コンパイル時間 376 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 521,984 KB
最終ジャッジ日時 2025-06-12 12:59:34
合計ジャッジ時間 4,946 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other MLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    n = int(sys.stdin.readline())
    strings = [sys.stdin.readline().strip() for _ in range(n)]
    m, x, d = map(int, sys.stdin.readline().split())

    # Build the trie
    nodes = []
    root = {'children': {}, 'parent': -1, 'depth': 0, 'up': []}
    nodes.append(root)
    end_nodes = []

    for s in strings:
        current = 0  # root is index 0
        for c in s:
            if c not in nodes[current]['children']:
                new_node = {
                    'children': {},
                    'parent': current,
                    'depth': nodes[current]['depth'] + 1,
                    'up': []
                }
                nodes.append(new_node)
                nodes[current]['children'][c] = len(nodes) - 1
            current = nodes[current]['children'][c]
        end_nodes.append(current)

    max_level = 20  # Sufficient for up to 2^20 which is over 1e6
    # Precompute binary lifting tables
    for node in range(len(nodes)):
        if nodes[node]['parent'] == -1:
            # root node
            nodes[node]['up'] = [node] * max_level
        else:
            # up[0] is parent
            nodes[node]['up'] = [nodes[node]['parent']]
            for k in range(1, max_level):
                ancestor = nodes[node]['up'][k-1]
                if ancestor == -1:
                    # This should not happen as parent is root
                    nodes[node]['up'].append(-1)
                else:
                    nodes[node]['up'].append(nodes[ancestor]['up'][k-1 if k-1 < len(nodes[ancestor]['up']) else 0])
            # Ensure up has max_level elements, fill if necessary
            while len(nodes[node]['up']) < max_level:
                nodes[node]['up'].append(nodes[node]['up'][-1])

    # LCA function
    def lca(u, v):
        if u == v:
            return u
        # Bring u and v to the same depth
        depth_u = nodes[u]['depth']
        depth_v = nodes[v]['depth']
        if depth_u > depth_v:
            u, v = v, u
            depth_u, depth_v = depth_v, depth_u

        # Bring v up to depth_u
        for k in reversed(range(max_level)):
            if depth_v - (1 << k) >= depth_u:
                v = nodes[v]['up'][k] if k < len(nodes[v]['up']) else v
                depth_v -= (1 << k)

        if u == v:
            return u

        for k in reversed(range(max_level)):
            if nodes[u]['up'][k] != nodes[v]['up'][k]:
                u = nodes[u]['up'][k]
                v = nodes[v]['up'][k]

        return nodes[u]['up'][0]

    total = 0
    current_x = x
    mod_val = n * (n - 1)
    for _ in range(m):
        # Generate i and j
        i_val = (current_x // (n-1)) + 1
        j_val = (current_x % (n-1)) + 1

        if i_val > j_val:
            i_val, j_val = j_val, i_val
        else:
            j_val += 1

        # Now, i_val and j_val are 1-based and i_val < j_val
        i = i_val - 1  # convert to 0-based
        j = j_val - 1

        u = end_nodes[i]
        v = end_nodes[j]
        lca_node = lca(u, v)
        total += nodes[lca_node]['depth']

        current_x = (current_x + d) % mod_val

    print(total)

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