QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#577554	#4224. 串	Starrykiller^#	0	0ms	0kb	C++23	1.7kb	2024-09-20 12:45:09	2024-09-20 12:45:09

Judging History

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

[2024-09-20 12:45:09]
评测

测评结果：0
用时：0ms
内存：0kb

查看

[2024-09-20 12:45:09]
提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long 
constexpr int p=998244353, B=131;

void solve() {
    string s; cin>>s; int n=size(s);
    if (n==1) {
        cout<<0<<'\n'; return;
    }
    vector<vector<int>> id(n,vector<int>(n)); 
    vector<vector<int>> h(n,vector<int>(n)); 
    int N=0;
    vector<set<int>> str(n+1); set<int> hsh;
    vector<int> pw(n+1);
    pw[0]=1;
    for (int i=1; i<=n; ++i) pw[i]=pw[i-1]*B%p;
    for (int i=0; i<n; ++i)
    for (int j=i; j<n; ++j) {
        id[i][j]=N++;
        if (j>i) h[i][j]=h[i][j-1]*B%p;
        (h[i][j]+=s[j]-'a')%=p; hsh.insert(h[i][j]);
    }
    vector<vector<int>> G(N); vector<int> deg(N);

    for (int len=1; len+len+1<=n; ++len) {
        for (int l=0; l+len-1<n; ++l) {
            int r=l=len-1, h1=h[l][r];
            for (int L=0; L+len-1<n; ++L) {
                int R=L+len-1, h2=h[L][R];
                int h=(h1*pw[len+1]%p+h2)%p;
                if (!hsh.count(h)) continue;
                int u=id[l][r], v=id[L][R];
                // cerr<<u<<"->"<<v<<'\n';
                // cerr<<len<<" "<<l<<' '<<r<<'\n';
                G[u].push_back(v); 
                deg[v]++;
            }
        }
    }
    queue<int> q; vector<int> f(N);
    for (int i=0; i<N; ++i) 
        if (!deg[i]) q.push(i);
    int ans=0;
    while (size(q)) {
        int u=q.front(); q.pop();
        f[u]++;
        ans=max(ans,f[u]);
        for (auto v: G[u]) {
            f[v]=max(f[v],f[u]);
            if (!--deg[v]) q.push(v);
        }
    }
    cout<<ans<<'\n';

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int T; cin>>T;
    while (T--) solve();
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Pretests

Final Tests

Test #1:

score: 0

Time Limit Exceeded

input:

5
wwgpdvdwwgpdvdwwgpdvdwwwvdwdww
imeoqomeomqomeommeoqomeomqomem
blmjcxblmjcxlmjlmjcxjcxblmjcxl
exzhdyzhddyzhdedyzhyzhddydyyzd
tsbosqtsbosqtsbossbosqtssqtsbb

output:

result:

Test #2:

score: 0

Time Limit Exceeded

input:

5
rmgmlkgmlkllklmlkgmgmlklklmlkm
fstnttfttfnttfttfttfttfttttftt
hxiykziykzixiykziyykzixiyiyyky
fbtnfwbtnffwbfbtnfwbtnffwwbtnw
yhdizazyhdidihdidihdizzazyyhdi

output:

result:

Test #3:

score: 0

Time Limit Exceeded

input:

4
skjnitkwybtcsfagbpslfxtijbwjqvskibxqwjmukwybtcsfagbbpslfxtijbwjqvskibxqwjmukwybtcsfagbpslfxtijbwjqvskibxqwjmukwybtcsfagbbpslfxtijbwjqvskibxqwjmukwybtcsfagbbpslukwybtcsfagbbpslfxtijbbbpslukwybtcsfaslfc
ssrpyzpwiydtayxmoddtqksdrhcavtsonldnmujuyzpwiydtayxmoddtqksdrhcavtsoniydtayxmoddtqksdrhwiydtayxmo...

output:

result:

Test #4:

score: 0

Time Limit Exceeded

input:

4
oupltnlcbcgntpnkbvktcbcpltnlcbcgpltnlcgpltngntpnlcbcgntpnkbvktcbcpltnlcbcgpltnlnlcbcgpltnlcgpltngntpnlcbcgntpnktngntpnlcbcgntpnkbvktcbcpltnlcbcgpltnlnlcbcgpltnlcgpltngntpnlcbcgntpnlcbcgntlcbcgntpnkbvn
nzmyzhhsoehahmorxpahsoehahmororxpahsoehahmhsoehahmmyzhhsoehahmhahsoehahmororxpahsoehahmhsoehahmmy...

output:

result:

Test #5:

score: 0

Time Limit Exceeded

input:

4
wwsqbwicfggaflmvdvegdkclrnybwwsqbwicfggafgdkclrnyaflmvdvegdkclrnybwwsqbwlrnybwwsqbwicfggafgdkclrnyaflmvdvegdkclrnybwwegdknybwwsqybwwsqbwlrnybwwsqbwicfggafgdkclrnyaflmvdvegdkclrnybqbwicfggafgdkclrnyafg
tgloxggsznuxqxggszxggszsznuxqxggszxggszggsznuxqxggsggsznuxqxggszxggszsznuxqxggszxggszggsznuxqxggs...

output:

result:

Test #6:

score: 0

Time Limit Exceeded

input:

3
ikcblmcsjillvojwymeimbaeipbhobwwnyaakcsvkghhusduehctjexrtaakewiruishkmewsleodhikrnfaternerxiqhamqutaiazbldrrmaddpidimwxsqwbgedswzowhovibaauncxsthwdvudokzpsfulbtbaapxlexrtaakewiruishkmewsleodhikrnfaternerxiqhamqutaiazbldrrmaddpidimwxsqwbgedswzowhovibaauncxsthwdvudokzpsfulbtbaapxlidimwxsqwbgedswzowh...

output:

result:

Test #7:

score: 0

Time Limit Exceeded

input:

3
gsxasrisfpretvfhxlwnysaarwkvizqrrntjecdltvqmsvvqgsdgkggdcszmtrfkfzwldzxnysgsxasrisfpretvfhxlwgsxasrisfpretvfhqrrntjecdltvqmsvvqgsdgkggdcszmtrfkfzwarwkvizqrrntjecdltvqmsvvqgsdgkggdcszmtrfkfzwldzxnysgsxasrisfpretvjecdltvqmsvvqgsdgkggdcszmtrfkfzwldzxnfkfzwldzxnysgsxasrisfpretvjecdltvqmsvvqgsdgkggdcsz...

output:

result:

Test #8:

score: 0

Time Limit Exceeded

input:

3
aekaabidsppfvwzguexdmycjcqqcxdmycjcqqycjcqexdmycjcqqcxdmycjcqqcxdmycjcqqycjcqevwzguexdmycjcqqcxdmyabidsppfvwzguexdmycjcqqcxdmycjcqqycjcqexdmycjcqqcxdmycjcqqcxdmycjcqqycjcqezguexdmycjcqqcxdmycjcqqycjcqexdmycjcqqcxdmycjcqqcxdmycjcqqycjcqevwzguexdmycjcqqcxdmyxdmycjcqqcxdmycjcqqycjcqexdmycjcqqcxdmycjc...

output:

result:

Test #9:

score: 0

Time Limit Exceeded

input:

4
fqbsybwtrauafctwxtzxmhmelxssvxxapauncqgvqcwxfptcktzyanenlxfguejjhdzjufgmicmptfrfasgcgkqrjxzfcipjoqukvawffkuaqniqgotoylhiignmrevhwrruupzzawbqljitxdhyooixxxlqejxaaouufwvfuzxhigbilkiazqzypkovtnwwbssiqookpnsxvvhhfpjghkezwuushsoilgtbwholuilqdszikiptsvuoqpgxhwisfbwbkkpesawxuvhgfycxuwoklwjvtrpaulbexqlrsh...

output:

result:

Test #10:

score: 0

Time Limit Exceeded

input:

105
iiqnrmmdztbfxwmieuflzvuqveboseucomrfagkbzohyktiqnnbpkyhgciuwoqacerjgxthwjqxtkfjzvnqfnxlpfhnvznxfeglecvcllzhxhszcfphsnvjuewqelnlswxwauylfaufhnejutsngnybuxtaiglaekyeexsmxmrezvpuohjxxjatgttrbetirsmvrehqtawuvlqmuzltllmtgfmjmgrdagytkijfkfagsqumsfidsuyyclhotbrvhrotbzzmgbuyromlvuqnrpntauhvxaqereyvfzjla...

output:

result:

Test #11:

score: 0

Time Limit Exceeded

input:

1000001
s
o
k
g
r
z
l
d
z
i
n
u
d
j
i
o
k
b
o
s
h
y
w
y
u
k
v
p
d
f
e
x
v
q
d
o
p
r
s
o
z
f
i
e
r
q
s
b
u
i
w
b
g
u
b
a
e
w
p
j
e
v
g
z
l
l
o
c
c
i
q
b
n
b
h
g
t
z
i
p
h
e
s
q
a
u
s
e
s
i
n
w
f
t
y
t
g
o
v
j
w
o
m
l
r
u
s
k
t
c
c
d
i
u
t
i
q
l
m
j
v
b
f
d
w
f
w
c
t
r
l
p
h
y
b
y
u
v
l
n
x
n
s
f
j
n
...

output:

result:

Test #12:

score: 0

Time Limit Exceeded

input:

110
rxxioshkbndigoxntdcejhvoskbndigoxntdcejgoxntdcejhvoskbndigoxbndigoxntdcejhvoskbndigoxntdccejhvoskbndigogoxntdcejgoxntdcejhvoskbndigoxbnejgoxntdcejhvoskbndigoxbndigoxntdcejhvoskbndigoxntdccejhvoskbndigogoxntdcejgoxntdcejhvosxntdcejhvoskbndigoxbndigoxntdcejhvoskbndigoxntdccejhvoskbndigogoxntdcejgo...

output:

result:

Test #13:

score: 0

Time Limit Exceeded

input:

105
jlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizovzbjlugzbdizo...

output:

result:

Test #14:

score: 0

Time Limit Exceeded

input:

5
xsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmnxsolriymnoxsmn...

output:

result:

Test #15:

score: 0

Time Limit Exceeded

input:

30
qqgcvqshumzfapruaztsztbkdhknlqmegsgekylgmkmobfjceeuezxqcebpqrduyxccjcpqqbefdlqfpubvvymxfnovetrestidxxvnbzsekilcemxbmjaryqofjfjdashxrclsefyqqjswxsykbydcrshczqgaknzermwvsvmkgegeygqahteynlandipovosnbqkvnwfudnabuqddlhbzsdowmfmjtgywwjtmhaikoimkapplzsmrxcpjhdvdjtbievwmxewlokxocobbgoueqkpypkdzgejmzfyxjx...

output:

result:

Test #16:

score: 0

Memory Limit Exceeded

input:

3
pounzdtkokaonqyllykjhhycqxdmmwndkjqlnlxbwzqlpqwcpjnysncilfxzdkenuwbjhakfacsptrukajksxnbksyjykplglopupccpgugzlcllmwgjjhtdhebttpcgfrcuvelczudmyrakngvypqdyufrpwtxbnaykelodhusglsqayoypebnzigqgcokrokbuvsadmsjzkbzkpzzucovnwltyzdrpnvmlnmqbezaqazcsybmcrhpnsjouofleczrplhqrgqhirjarmoudvjtqsjmjqzptzgimnbetrl...

output:

result:

Test #17:

score: 0

Memory Limit Exceeded

input:

36
bqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrgxpbqsaqunccgyiarpeaezrg...

output:

result:

Test #18:

score: 0

Time Limit Exceeded

input:

36
ueuhiuuxbkqmcjrkbkknbuogliigucooglvofroicgveqoqtacgcwukjfuszwgpermvydlhfreljsdcuhkwdfgpmbhlznaefmbfrmmzdsmpmqrhxcddjmsvpziookuvyvbpjpqnideuvvbuzhxktrhkspahzvczsdpcvfrdkvxfszauizebrmljdlsfixedavhxbyalvyrpztjhsqkleljsdcuhkwdfgpfreljsdcuhkwdfgpmbhlznaefmbfrmmzdsmpmqrhxcddjmsvpziookuvyvbpjpqnideuvvbu...

output:

result:

Test #19:

score: 0

Time Limit Exceeded

input:

400001
ggg
eee
hhh
ppp
eee
nnn
hhh
aaa
nnn
uuu
xxx
ddd
ttt
sss
jjj
fff
ccc
ddd
aaa
xxx
vvv
mmm
qqq
bbb
qqq
uuu
bbb
ggg
mmm
qqq
ccc
hhh
nnn
yyy
hhh
qqq
fff
www
xxx
uuu
iii
ggg
nnn
rrr
sss
aaa
eee
vvv
iii
eee
vvv
www
qqq
ddd
qqq
rrr
qqq
xxx
ppp
yyy
nnn
bbb
uuu
bbb
yyy
aaa
ttt
www
mmm
lll
qqq
ggg
zzz
b...

output:

result:

Test #20:

score: 0

Time Limit Exceeded

input:

27
xtahmwzugvrelqyihbryeggyvqgliwxirxrdvtxbopgahekrhbpnixmfpuryqqiipznksnljetllzvehwvugsimiffivvsfktvumihxmdixcdelbziiuquevzotugagzvcndjkposprxtczumhoddsacivyowgqridxtqmikdbiyfhtsqhxtczxkvxbtfrknwjiowszbthabqtticsbgratmzufenstlbbczubdpkdqcylkcdnjvnejoarsplnaoocqkftcpwstwgdyjqhgfnstnjncuafkrhadptfgra...