結果
問題 |
No.962 LCPs
|
ユーザー |
|
提出日時 | 2021-07-25 16:15:48 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 769 bytes |
コンパイル時間 | 150 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 76,740 KB |
最終ジャッジ日時 | 2024-07-21 00:29:35 |
合計ジャッジ時間 | 20,339 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 WA * 32 |
ソースコード
from dataclasses import dataclass, field N = int(input()) ans = 0 tri = lambda x: x * (x + 1) // 2 @dataclass class TrieNode: num: int last: int seq: int child: dict = field(default_factory=dict) G = [None] * (2 * 10 ** 5 + 1) G[0] = TrieNode(num=0, last=0, seq=0) nodenum = 1 for i in range(N): S = input() pointer = 0 for s in S: if s not in G[pointer].child: G[pointer].child[s] = nodenum G[nodenum] = TrieNode(num=nodenum, last=i - 1, seq=0) nodenum += 1 pointer = G[pointer].child[s] if G[pointer].last == i - 1: G[pointer].seq += 1 ans += tri(G[pointer].seq) else: G[pointer].seq = 1 G[pointer].last = i print(ans)