結果
問題 | No.2761 Substitute and Search |
ユーザー |
|
提出日時 | 2024-05-05 16:42:24 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,783 bytes |
コンパイル時間 | 340 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 817,792 KB |
最終ジャッジ日時 | 2024-05-07 04:53:41 |
合計ジャッジ時間 | 14,968 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 32 ms
10,752 KB |
testcase_01 | AC | 32 ms
10,752 KB |
testcase_02 | AC | 32 ms
10,880 KB |
testcase_03 | AC | 33 ms
11,008 KB |
testcase_04 | AC | 5,642 ms
19,328 KB |
testcase_05 | AC | 838 ms
19,456 KB |
testcase_06 | MLE | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
ソースコード
class TrieNode: __slots__ = ("sum", "children") def __init__(self): self.sum = 0 self.children = [None] * 26 def merge(self, other): self.sum += other.sum for c in range(26): rhs = other.children[c] if rhs: lhs = self.children[c] if lhs: lhs.merge(rhs) else: self.children[c] = rhs class Trie: __slots__ = ("root", "subst") def __init__(self, l): self.root = TrieNode() self.subst = [[[c] for c in range(26)] for _ in range(l)] def add(self, s): cur = self.root cur.sum += 1 for k in range(len(s)): c = s[k] if not cur.children[c]: node = TrieNode() cur.children[c] = node cur = cur.children[c] cur.sum += 1 def substitute(self, k, c, d): x, y = self.subst[k][d], self.subst[k][c] if len(x) < len(y): x, y = y, x for v in y: x.append(v) self.subst[k][d] = x self.subst[k][c] = [] def search(self, s): cur = self.root for k in range(len(s)): d = s[k] last = None for c in self.subst[k][d]: node = cur.children[c] if node: if last: last.merge(node) cur.children[c] = None else: last = node if not last: return 0 cur = last return cur.sum def convert(str): return [ord(str[i]) - 0x61 for i in range(len(str))] N, L, Q = map(int, input().split()) trie = Trie(L) for _ in range(N): trie.add(convert(input().strip())) for _ in range(Q): query = input().strip().split() if query[0] == "1": k = int(query[1]) - 1 c = ord(query[2]) - 0x61 d = ord(query[3]) - 0x61 trie.substitute(k, c, d) else: t = convert(query[1]) print(trie.search(t))