結果
問題 | No.2761 Substitute and Search |
ユーザー |
![]() |
提出日時 | 2024-05-17 22:24:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,117 bytes |
コンパイル時間 | 2,197 ms |
コンパイル使用メモリ | 212,404 KB |
最終ジャッジ日時 | 2025-02-21 15:01:43 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 MLE * 7 |
ソースコード
#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; }