結果
問題 | No.2761 Substitute and Search |
ユーザー |
![]() |
提出日時 | 2024-05-17 22:24:22 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,117 bytes |
コンパイル時間 | 2,266 ms |
コンパイル使用メモリ | 221,804 KB |
実行使用メモリ | 663,680 KB |
最終ジャッジ日時 | 2024-05-17 22:24:43 |
合計ジャッジ時間 | 17,684 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 806 ms
8,448 KB |
testcase_05 | AC | 172 ms
8,448 KB |
testcase_06 | MLE | - |
testcase_07 | MLE | - |
testcase_08 | AC | 202 ms
24,960 KB |
testcase_09 | AC | 526 ms
24,960 KB |
testcase_10 | MLE | - |
testcase_11 | MLE | - |
testcase_12 | MLE | - |
testcase_13 | MLE | - |
testcase_14 | AC | 279 ms
24,960 KB |
testcase_15 | MLE | - |
ソースコード
#include <bits/stdc++.h> using namespace std; struct TrieNode { int count; unordered_map<char, TrieNode*> children; TrieNode() : count(0) {} }; void insert(TrieNode* root, const string& word) { TrieNode* current = root; for (char c : word) { if (current->children.find(c) == current->children.end()) { current->children[c] = new TrieNode(); } current->children[c]->count += 1; current = current->children[c]; } } int main() { int n, l, q; cin >> n >> l >> q; vector<string> s(n); for (int i = 0; i < n; ++i) { cin >> s[i]; } TrieNode* tree = new TrieNode(); for (const string& t : s) { insert(tree, t); } vector<vector<char>> char_cur(l, vector<char>(26)); for (int i = 0; i < l; ++i) { for (int j = 0; j < 26; ++j) { char_cur[i][j] = 'a' + j; } } for (int i = 0; i < q; ++i) { int com; cin >> com; if (com == 1) { int k; char c, d; cin >> k >> c >> d; --k; replace(char_cur[k].begin(), char_cur[k].end(), c, d); } else { string t; cin >> t; vector<TrieNode*> cur = {tree}; int ans = 0; for (int i = 0; i < t.size(); ++i) { vector<TrieNode*> cur_next; ans = 0; for (TrieNode* tr : cur) { for (auto& [key, value] : tr->children) { if (char_cur[i][key - 'a'] == t[i]) { cur_next.push_back(value); ans += value->count; } } } cur = cur_next; } cout << ans << endl; } } // Clean up dynamically allocated TrieNodes function<void(TrieNode*)> deleteTrie = [&](TrieNode* node) { for (auto& [key, child] : node->children) { deleteTrie(child); } delete node; }; deleteTrie(tree); return 0; }