結果

問題 No.2761 Substitute and Search
ユーザー ttkkggwwttkkggww
提出日時 2024-05-31 13:09:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 3,622 bytes
コンパイル時間 5,603 ms
コンパイル使用メモリ 297,188 KB
実行使用メモリ 586,772 KB
最終ジャッジ日時 2024-05-31 13:09:51
合計ジャッジ時間 22,953 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 145 ms
20,224 KB
testcase_05 AC 34 ms
7,680 KB
testcase_06 MLE -
testcase_07 MLE -
testcase_08 AC 67 ms
23,356 KB
testcase_09 AC 123 ms
30,316 KB
testcase_10 MLE -
testcase_11 MLE -
testcase_12 MLE -
testcase_13 MLE -
testcase_14 AC 74 ms
26,836 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<char,int>> node;
	vector<int> cnt;
	vector<set<int>> depth;
	Trie(){
        node.reserve(3000000);
        cnt.reserve(3000000);
        depth.reserve(3000000);
		node.push_back(map<char,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<char,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]);
	}
    S.clear();
    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();
}
0