結果
問題 | No.2761 Substitute and Search |
ユーザー | ttkkggww |
提出日時 | 2024-05-31 12:54:30 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 3,507 bytes |
コンパイル時間 | 5,866 ms |
コンパイル使用メモリ | 296,464 KB |
実行使用メモリ | 590,284 KB |
最終ジャッジ日時 | 2024-12-20 21:54:10 |
合計ジャッジ時間 | 24,882 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,820 KB |
testcase_04 | AC | 151 ms
20,224 KB |
testcase_05 | AC | 36 ms
7,680 KB |
testcase_06 | MLE | - |
testcase_07 | MLE | - |
testcase_08 | AC | 79 ms
25,656 KB |
testcase_09 | AC | 135 ms
30,264 KB |
testcase_10 | MLE | - |
testcase_11 | MLE | - |
testcase_12 | MLE | - |
testcase_13 | MLE | - |
testcase_14 | AC | 86 ms
28,312 KB |
testcase_15 | MLE | - |
ソースコード
#include<bits/stdc++.h>using namespace std;#include<atcoder/all>using namespace atcoder;using ll = long long;struct Trie{vector<map<int,int>> node;vector<int> cnt;vector<set<int>> depth;Trie(){node.push_back(map<int,int>());cnt.push_back(0);depth.push_back(set<int>());depth[0].insert(0);}void add(string s){int now = 0;for(int i = 0;i<s.size();i++){if(node[now].count(s[i]-'a') == 0){node.push_back(map<int,int>());cnt.push_back(0);depth.push_back(set<int>());node[now][s[i]-'a'] = node.size()-1;depth[i+1].insert(node.size()-1);}now = node[now][s[i]-'a'];cnt[now]++;}}int get_cnt(string s){int now = 0;for(int i = 0;i<s.size();i++){if(node[now].count(s[i]-'a') == 0){return 0;}now = node[now][s[i]-'a'];}return cnt[now];}void swap(int k, char c, char d){for(auto root :depth[k]){if(node[root].count(c-'a')==0)continue;if(node[root].count(d-'a') == 0){depth[k+1].erase(node[root][d-'a']);node[root][d-'a'] = node[root][c-'a'];node[root].erase(c-'a');}else{queue<tuple<int,int,int>> Q;Q.push({node[root][c-'a'], node[root][d-'a'],k+1});depth[k+1].erase(node[root][c-'a']);cnt[node[root][d-'a']] += cnt[node[root][c-'a']];cnt[node[root][c-'a']] = 0;node[root].erase(c-'a');while(Q.size()){auto [a, b,k] = Q.front();Q.pop();for(int j = 0;j<26;j++){if(node[a].count(j)==0){continue;}if(node[b].count(j) == 0){depth[k+1].erase(node[b][j]);node[b][j] = node[a][j];node[a].erase(j);}else{Q.push({node[a][j], node[b][j],k+1});depth[k+1].erase(node[a][j]);cnt[node[b][j]] += cnt[node[a][j]];cnt[node[a][j]] = 0;node[a].erase(j);}}}}}}void print(){for(int i = 0;i<node.size();i++){cout<<i<<": ";for(int j = 0;j<26;j++){if(node[i][j] != -1){cout<<char(j+'a')<<node[i][j]<<' ';}}cout<<endl;}/*cout<<"depth: "<<endl;for(int i = 0;i<depth.size();i++){cout<<i<<": ";for(auto x:depth[i]){cout<<x<<' ';}cout<<endl;}*/cout<<"cnt:"<<endl;for(int i = 0;i<cnt.size();i++){cout<<i<<": "<<cnt[i]<<endl;}}};int N,L,Q;vector<string> S;vector<int> OP;vector<string> T;vector<int> K;vector<char> C,D;void solve(){Trie trie;for(int i = 0;i<N;i++){trie.add(S[i]);}cerr<<trie.node.size()<<endl;//trie.print();for(int i = 0;i<Q;i++){if(OP[i] == 1){trie.swap(K[i]-1, C[i], D[i]);//trie.print();}else{cout << trie.get_cnt(T[i]) << endl;}}}signed main(){cin.tie(nullptr);ios::sync_with_stdio(false);cin >> N >> L >> Q;S.resize(N);OP.resize(Q);T.resize(Q);K.resize(Q);C.resize(Q);D.resize(Q);for(int i = 0;i<N;i++){cin >> S[i];}for(int i = 0;i<Q;i++){cin >> OP[i];if(OP[i] == 2){cin >> T[i];}else{cin >> K[i] >> C[i] >> D[i];}}solve();}