QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#474487 | #801. 回文自动机 | wangzhifang# | 0 | 1ms | 6000kb | C++14 | 1.5kb | 2024-07-12 19:09:33 | 2024-07-12 19:09:34 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sqr(const ll&x){
return x*x;
}
void maxify(ll&x,const ll&y){
y>x&&(x=y);
}
const int max_n=1000000;
struct node{
int len,fail,cnt,sn[26];
};
char str[max_n+2];
struct pam_t{
node tr[max_n+1];
int now,nodcnt;
void clearsn(const int u){
memset(tr[u].sn,0,sizeof(tr[u].sn));
}
void init(){
nodcnt=1;
tr[0].len=-1,tr[0].fail=1;
clearsn(1);
tr[1].len=0,tr[1].fail=0;
clearsn(2);
now=1;
}
void append(const int i){
while(str[i-tr[now].len-1]!=str[i])
// fprintf(stderr,"*%d\n",now),
now=tr[now].fail;
// fprintf(stderr,"par %d\n",now);
if(!tr[now].sn[int(str[i])]){
const int v=++nodcnt;
tr[v].len=tr[now].len+2;
// fprintf(stderr,"%d\n",tr[v].len);
tr[v].cnt=0,clearsn(v);
int j=tr[now].fail;
for(; str[i-tr[j].len-1]!=str[i]; j=tr[j].fail);
// fprintf(stderr,"&& %d %d\n",j,int(str[i]));
tr[v].fail=tr[j].sn[int(str[i])];
tr[now].sn[int(str[i])]=v;
}
++tr[now=tr[now].sn[int(str[i])]].cnt;
// fprintf(stderr,"%d: %d %d\n",i,now,tr[now].fail);
}
void solve(){
ll ans=0;
for(int i=nodcnt; i>1; --i){
// fprintf(stderr,"%d: %d %d\n",i,tr[i].len,tr[i].cnt);
tr[tr[i].fail].cnt+=tr[i].cnt;
maxify(ans,sqr(tr[i].len)*tr[i].cnt);
}
printf("%lld\n",ans);
}
}pam;
int main(){
scanf("%s",str+1);
str[0]=26;
const int n=strlen(str+1);
pam.init();
for(int i=1; i<=n; ++i){
str[i]-='a';
pam.append(i);
}
pam.solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 35
Accepted
time: 1ms
memory: 6000kb
input:
bdgedcfadbabbfgeacdgbggaefddebabbfgeacdgbefaecfddffeddacbabfcgecedacbffeddacbabfebadggfafabcdfdeaabdeecgbcecegcgecedacbfgdagbgagafdegecadfebcdbgfacdecdegecadfebbcdfdeaabdbfgcbccfcaebcecfdfccagdafaeaacbggaefddebcbecdafageeaabcbdafadcbecdbcgcbdgedcfadbcaefbdfcbgfcdeceddaaffgcedfcdcgdcgbfdddfdadgagbbef...
output:
5594
result:
ok answer is '5594'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5812kb
input:
bdgfcbabegfbbbgecfbddbaceaefbebgeafdbbgaebebdabgebabacccebbaebeafbefaabdgfcbabegdbaceaefbegcaegagcdgcacccfbbfgffgcdgbccgecbdbcagbbcacccfbbfgeegfcaecbcebebdabgebbbebbgcfafbbbgbdbabgbabfgdfaggfbcbabeebbdaagacgbafecebfccdbgfacgcabefaaedadeacgdeegfcaecbcabacccebbacdbbdceeegcdbbdceeegbaccaecfbgbbebbgcfaf...
output:
7308
result:
ok answer is '7308'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
baeedcbgaeaabdcaeeagbeffgedegdfcggaeafeegccecbacaaaabdcaeeaggedcbbaebfbcbbbebeaeagedddgabgccdecfeegcababaddfcabcbbbebeaegabeddeedaaabebgcafgeefgeabcaafgcbcfaafgadddgdbccbcddfacfcgdeefgeabcaagbgbgdbefdcefcacafcagcfadegebcababaddfcaffbfgdfecefgafcfgddbagfgceabefcaaebagddabcbbbebeaedaddaacgfcabeffgfgeg...
output:
6011
result:
ok answer is '6011'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
fadabcedabffccgceafdfgebfgebdfffccgceafdfbabeebbccbcebdaabagbdcabbebbgbbdddddcfdfefcfgcaedcdfbfcgagggeacabgddfdggddgcgagfefgeafdaefefgeafdaefbabeebbccabccadccgcbbdddddcfdfadabcedabgbdegbcgdecfcefaedcffadabcedabadgbbacdfbfecccfacaaggggffddffffbcgacfgbcbeadagbfffefcfgcaedgeacabgddfgbcccdcgegbdcabbebbg...
output:
5874
result:
ok answer is '5874'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
efggbbfcabcdfbceagadfagaeegbegcbfbcfcgfbgdfffcdeagfcggffcacbbadedceffedbgafcbegdggabccbcecfcbfegdcbecdedfdeebebecffcaafgffabgbgedfcdabgbeffaagbffcdccaddcadgbbcadedgcfbgbdefggbbfcabddccdefedagebfbbfadfagagedffaagabcgbcffaggfebdbefdcfecegaeggggdacedbgfcdedfdeebececbfefeegdebddaeafbffabgbgedfcfcdgcaacc...
output:
5751
result:
ok answer is '5751'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
eafdccagcbcaeebabcggdgdfcdfgeacbgcdfbgcabdegdbbaabgecbaaagffecffedeffcedcdgcecbgfedbdgabfdcbefcecdfdfaegccbfeefdccgfbfebecffedeffcbdegdbbaabeafcbegcbagecbaaagffefcdafgageffefbcceecdffabcbbdbefcdafgageedcdgcecbgcaeebabcggfbeegdaccfdffabcbbdbcbefcecdfdcdccfcbadcecffedeffcdcgaagfaegddecgffafcdgdfcdfgea...
output:
6156
result:
ok answer is '6156'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5888kb
input:
aecedcggbddbeeadcfbcaebcdceeegbcbaegcecbfefbbgbcfgegbdaggeebdfebbaeddgffdgfedegbaecedcggbdbbddadfageebfadbbegbaaaffddbdacdgbgbdggfgebaaebcfceefgaedacdeeecaccecgdcbafafccffdaedbbegagecfcdbbacceafeaabbefccgbgceeabcbaegcecbdfgacggffbdcbafafccfbfccfbgggadddddacbfeeebgdaddagcdgbgbdggffdaedbbegabcbaegcecb...
output:
5662
result:
ok answer is '5662'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
aaffagaebeecbgagbccbafgceadgeebdgffeceacbgcbebggfdbgcbebggfdadgceeggefaaffagaebeegfafdeeecaaffagaebebgaabbebcaaaaceagaabcabddacfebbfbefagdbcdaggeggcfagdgfddegcabcddaefcdcaaaceagaabecbgagbccbaaffagaebegbagabfddcbdgffeceacccafcbcdcagcebbbgfggbfbefagdbcgddcdaadafgcebbbgfggccafcbcdcaafgceadgeebfbgbbddeb...
output:
6006
result:
ok answer is '6006'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5884kb
input:
bfbbfccggagbeddgdcbdfecaedcedefgfeaabdcaebabegdgdebbddaefebgcefgfcagdbgccacgdbcdadbeafcedeffbeccebabacedebabagadfgbdcaeaadbacgdfbgabgdbafeadgbfbecfccbfgeecabgfafacefbgbcebbddaefebgadbacgdfbgdagefcefgeddgagggedefgafgdbgacffbeccebabgbeebbdafegbeddgdcbdcefgfcagdbacafdggbacccebfdcddgadbeafcedecefgfcagdb...
output:
5966
result:
ok answer is '5966'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
gbegegfcdbbdagefbgadbfafadedacdbbffcbagfcgebcbbeabedbedegbdbebfcbcbffddeadadffffadccgfebbadbdcdfecbadbfbfeaefadfdgfeaebfcbgdbfbcfebdagefbgadedgaeecegbeaffcddaggcafcddaffccafcddaffcgfdegffaaeggadabffaddbaebcffcadbaebcffcabfafadedacdabgaccfdedbfbfeaefadeadadffffeaffeffaffdbbffcbagfcbbaebfbfgebfcbcbffd...
output:
5997
result:
ok answer is '5997'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
cihgfkaabfcjeehlggeihjadhfkjdfegfiibdidefcdehjgkkhjfldaeelddklklgjdkbeidjahlkjligjdhjffddfljlbejibdgllkddjcccddajbkfjkfkecegichgklaeccfcgjidfkgckhafjeabajihcchghkchjfjkkbeeajcghaillghbcidglkcldfkkkegjdgcjfecjbaekhcadlfefcgagjdgebkgafagdeijfkgcebkkefbblkdlajccehgiidfahkfblfjafgikaacjfddalheeelcjifafk...
output:
3028
result:
ok answer is '3028'
Test #12:
score: 0
Accepted
time: 0ms
memory: 4036kb
input:
xbqpbhaecvtkxghbvkmwarwpsrjwhgqnojrdskecifmlbcbctlolyjdswhhclojnnfcynqqfvcchkuehqxgbuaqsnwotkfskrnmkwoonkhcvwwmplrxlfjvaepipcegcekikifaxpqclhwmstfifhnawojfngbphtfftcewckdeseoxnfwdtymodyqlewkbcjwtyufrevupfapglxllumkvspbebirrytpcmodoncourbanwyylnwugxujjtdwgyjipayvmgucnqnrpwqplwpdsocasjykituacpagydmymp...
output:
1481
result:
ok answer is '1481'
Test #13:
score: 0
Accepted
time: 0ms
memory: 5944kb
input:
tobdfhlrhrypwivkkpiugptzudfkxlxkprusxvwlhwqinpfwdxelgpgrfkmkjfoovtwrinkdpehykvkksgswkikxbowttkqdpkvevjbrigecweqaehejnugxnukpqcueewuazbzfbijnvrqlimbipyeyxhszbdqeduibykofvyqbhgxecowsrrqzpboxzafxinkqtxgcavjiezzjoqweqtupcxgjtxgxxzanmwamwhpzyxqxgouhgnkvqglgunyqnawrwlqpxhtdscimoedcwpuwbqhiygbfoshwjkvquisd...
output:
1437
result:
ok answer is '1437'
Test #14:
score: 0
Accepted
time: 1ms
memory: 5868kb
input:
epkkjklkmnmgajmqaqfdepfdlhockegkcpekmdmfaphqmqpqopjhngpblcephamlqmekfnqjoknnkmbodonbfkmobeddbmplkallmeqipgdimpiqfeficqknaeapllechkpdamdpeoanqoghnlhfggaihfnppbmfdnjcokjfakladhdmdiejcecaheilbeoebgfgcfjlngiphlqeemgopopmonfcccpjhleijllfngdomcqhkfcidmkgqqgoqegikioaoodkokhaklaihlenckifchcjoibffdjqflgqfmdo...
output:
2190
result:
ok answer is '2190'
Test #15:
score: -35
Wrong Answer
time: 1ms
memory: 5920kb
input:
acbabbcbaacacabcbabcaaacaabcaaabccbabcbcaaaabbcabaaabbacbcaaabcccbaaccbbcabbaaababccbbacacbabaaacbacbcabcbbcbabccccccbbaacacbcacacabbbbbbcbcaaacbcbacccaabbbabbbcabccbabaabcbccbacccccbabbbbbbaaccaabbccccbabbcaccbaccaaababbcaaabcbaaacbbaccbbcbacbccacabbccacbbacbabbcabcbbaccaabbccbcbbcbccabcbccabbbabcb...
output:
12339
result:
wrong answer expected '15924', found '12339'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%