結果

問題 No.2761 Substitute and Search
ユーザー ttkkggwwttkkggww
提出日時 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 -
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0