QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#655240#5311. Master of BothWA_automaton#TL 120ms48408kbC++202.0kb2024-10-19 01:52:452024-10-19 01:52:46

Judging History

你现在查看的是最新测评结果

  • [2024-10-19 01:52:46]
  • 评测
  • 测评结果:TL
  • 用时:120ms
  • 内存:48408kb
  • [2024-10-19 01:52:45]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back
void debug() {std::cerr << "\n";}
template<class T, class... OtherArgs>
void debug(T &&var, OtherArgs &&... args) {
    std::cerr << std::forward<T>(var) << " ";
    debug(std::forward<OtherArgs>(args)...);
}
#define SZ(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using i64 = long long;
using u64 = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
constexpr int N = 1000010;
constexpr int P = 998244353;

int son[N][26], cnt[N], idx, ans[N];
vector<int> cmp[26][26];
int extra;

void insert(string &s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int u = s[i] - 'a';
        for (int v = 0; v < 26; v++) {
            if (!son[p][v]) {
                continue;
            }
            for (int id : cmp[u][v]) {
                ans[id] += cnt[son[p][v]];
            }
        }
        if (!son[p][u]) {
            son[p][u] = ++idx;
        }
        p = son[p][u];
        cnt[p]++;
    }
    for (int v = 0; v < 26; v++) {
        if (!son[p][v]) {
            continue;
        }
        extra += cnt[son[p][v]];
    }
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<string> str(n);
    for (int i = 0; i < n; i++) {
        cin >> str[i];
    }

    for (int i = 0; i < q; i++) {
        string s;
        cin >> s;
        for (int x = 0; x < 26; x++) {
            for (int y = x + 1; y < 26; y++) {
                cmp[s[x] - 'a'][s[y] - 'a'].pb(i);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        insert(str[i]);
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] + extra << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
}   

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

input:

5 3
aac
oiputata
aaa
suikabudada
aba
abcdefghijklmnopqrstuvwxyz
qwertyuiopasdfghjklzxcvbnm
aquickbrownfxjmpsvethlzydg

output:

4
3
4

result:

ok 3 number(s): "4 3 4"

Test #2:

score: 0
Accepted
time: 4ms
memory: 48408kb

input:

100 100
spkfvrbkfsspmnlgrdojwdqutknvzejorqxsmfgbfrhpxkrrtravhmxenjrzypkxounrbantpkaezlcnudjmwxpgqakfoxcmdjcygujdtpluovbisxmklkzzuuyziapzyrszcggjkzrwmtyolnbobubbezdwmumyzyhaogiiolictzjpxbyaamecytpnyzxlumxjkzyfavxlzdwtgrxtqcnddzfocznitlaxlpcceuelqlbmyzetlpaivxnuvuctsbjbaulmbmkangqahpdojqimvmcugjeczkgx...

output:

2368
2693
2179
2466
2435
2370
2604
2468
2335
2268
2686
2781
2538
2208
2386
2539
2728
2383
2248
2372
2446
2266
2290
2688
2602
2515
2634
2558
2598
2632
2763
2255
2557
2579
2367
2516
2676
2273
2429
2556
2576
2635
2422
2829
2362
2552
2377
2261
2603
2516
2298
2282
2520
2333
2505
2287
2261
2476
2791
2328
...

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 120ms
memory: 48264kb

input:

500000 5
ru
x
tb
s
e
w
e
m
l
b
g
zr
jp
h
js
xk
fjwtk
wtkem
o
ev
a
a
x
sy
dh
y
kkdcxfr
hgq
j
k
xr
s
cvwbrlk
u
u
x
wtvgef
dzxsk
qv
gxl
g
m
rpl
ldp
q
lc
dk
g
k
im
o
yhn
z
a
knc
tyv
mz
ak
qdhq
c
niw
o
j
heu
w
g
e
kt
n
inqt
i
al
q
ebphky
sv
m
mry
oj
cl
j
r
sf
vpd
u
rio
sfkg
m
el
s
zs
g
o
e
njp
r
xczcm
gh...

output:

61908555824
61940608380
61883035862
61951203480
61924597894

result:

ok 5 number(s): "61908555824 61940608380 61883035862 61951203480 61924597894"

Test #4:

score: -100
Time Limit Exceeded

input:

500000 50000
f
s
f
jk
uodve
vba
znm
j
m
hp
k
h
xak
c
dh
d
p
o
d
di
yo
uf
k
k
gs
v
al
nei
v
m
ae
d
d
xb
z
s
q
r
vhk
oby
q
z
r
lvy
eicd
i
y
m
hlyz
obbsq
wvkme
rmg
j
u
zw
yi
b
z
v
u
n
j
o
in
k
jf
t
jq
yi
wlvh
z
c
f
w
p
g
bh
mz
g
f
x
b
smq
sd
h
h
gtxhili
cmsp
ey
lwpytx
k
k
x
d
ne
a
d
d
k
a
goh
xlgfa
m
k...

output:


result: