結果

問題 No.2761 Substitute and Search
ユーザー t98slidert98slider
提出日時 2024-05-17 22:01:46
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,274 bytes
コンパイル時間 1,963 ms
コンパイル使用メモリ 206,996 KB
実行使用メモリ 21,136 KB
最終ジャッジ日時 2024-05-17 22:01:56
合計ジャッジ時間 9,423 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1,197 ms
21,136 KB
testcase_05 TLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Trie{
    struct Node {
        std::array<int,26> child;
        int sz;
        Node(void) :sz(0) { child.fill(-1); }
        const int& operator[](int k) const { return child[k]; }
        int& operator[](int k) { return child[k]; }
    };
    int num;
    vector<Node> tree;
    Trie() : num(0) {
        tree.push_back(Node());
    }
    void insert(const string &s){
        int cur = 0;
        for(auto c : s){
            if(tree[cur][c - 'a'] == -1){
                tree[cur][c - 'a'] = ++num;
                tree.push_back(Node());
            }
            cur = tree[cur][c - 'a'];
            tree[cur].sz++;
        }
    }
    void erase(const string &s){
        int cur = 0;
        for(auto c : s){
            cur = tree[cur][c - 'a'];
            tree[cur].sz--;
        }
    }
    int size(const string &s){
        int cur = 0;
        for(auto c:s){
            if(tree[cur][c - 'a'] == -1) return 0;
            cur = tree[cur][c - 'a'];
        }
        return tree[cur].sz;
    }
    int size(int node_num){
        return (node_num==-1?0:tree[node_num].sz);
    }
    int search(string &s){
        int cur=0,ans=0;
        array<int,26> t;
        t.fill(0);
        for(auto c:s)t[c-'a']++;
        for(auto c:s){
            for(int j=0;j<26;j++){
                if(t[j])ans+=size(tree[cur][j]);
            }
            if(tree[cur][c-'a']==-1)return ans;
            cur=tree[cur][c-'a'];
            t[c-'a']--;
        }
        return ans;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, l, q;
    cin >> n >> l >> q;
    vector<string> s(n);
    Trie trie;
    for(auto &&ss : s){
        cin >> ss;
        trie.insert(ss);
    }
    while(q--){
        int cmd;
        cin >> cmd;
        if(cmd == 1){
            int k;
            char c1, c2;
            cin >> k >> c1 >> c2;
            k--;
            for(auto &&ss : s){
                if(ss[k] == c1){
                    trie.erase(ss);
                    ss[k] = c2;
                    trie.insert(ss);
                }
            }
        }else{
            string s;
            cin >> s;
            cout << trie.size(s) << '\n';
        }
    }
}
0