为什么会MLE

P8306 【模板】字典树

Little_Cabbage @ 2024-05-01 19:29:34

#include <bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define ldb long double
#define db double
#define endl '\n'
#define il inline
using namespace std;
int n, q;
class Trie {
    public:
        int cnt = 1;
        struct node {
            int num[123];
            int flag;
            void init() {
                flag = 0;
                memset(num, 0, sizeof num);
            }
        } tree[2000005];
        il void Init() {
            for (int i = 1; i <= cnt; i++) {
                tree[i].init();
            }
            cnt = 1;
        }
        il void Insert(string s) {
            int root = 1;
            for (int i = 0; i < s.size(); i++) {
                if (tree[root].num[s[i]] == 0) {
                    cnt++;
//                  tree[cnt].init();
                    tree[cnt].flag = 1;
                    tree[root].num[s[i]] = cnt;
                    root = cnt;
                } else {
                    tree[tree[root].num[s[i]]].flag++;
                    root = tree[root].num[s[i]];
                }
            }
//          tree[root].flag++;
        }
        il int Ask(string s) {
            int root = 1;
            for (int i = 0; i < s.size(); i++) {
                if (tree[root].num[s[i]] == 0) {
                    return 0;
                }
                root = tree[root].num[s[i]];
            }
            return tree[root].flag;
        }
};
Trie hhh;
void Solve() {
    cin >> n >> q;
    while (n--) {
        string s;
        cin >> s;
        hhh.Insert(s);
    }
    while (q--) {
//      cout << "Yes";
        string s;
        cin >> s;
        cout << hhh.Ask(s) << endl;
    }
    hhh.Init();
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//  freopen("P8306_1.in", "r", stdin);
//  freopen("ans.ans", "w", stdout);
    int t = 1;
    cin >> t;
//  t = read();
    while (t--) Solve();
    return 0;
}

by nxd_oxm @ 2024-05-01 21:54:50

很明显你又开了longlong又开 2 \times 10^6 \times 123 的数组不MLE才怪呢。你可以全部减去 0,那num数组就是大概80。再去掉longlong。


|