QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#125882#801. 回文自动机NOI_AK_ME#0 6ms17228kbC++231.6kb2023-07-17 20:48:212023-07-17 20:48:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-17 20:48:23]
  • 评测
  • 测评结果:0
  • 用时:6ms
  • 内存:17228kb
  • [2023-07-17 20:48:21]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long
#define dub long double
const int MAXN = 2e6+7;
const int inf = 1e9+7;
const dub eps = 1e-14;

using namespace std;

int tr[MAXN][30], len[MAXN], fail[MAXN];
int lst = 1, cnt = 1;
string s;
queue <int> q;
int in[MAXN], f[MAXN];

inline int read( )<%
    int x = 0 ; short w = 0 ; char ch = 0;
    while( !isdigit(ch) ) { w|=ch=='-';ch=getchar();}
    while( isdigit(ch) ) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return w ? -x : x;
%>

int get(char x){ return x - 'a'; }

void insert(int x){
    int p = lst, np = ++cnt, q, nq; lst = np;
    len[np] = len[p] + 1; f[np] = 1;
    for(; p and !tr[p][x]; p = fail[p]) tr[p][x] = np;
    if(!p) fail[np] = 1;
    else if(len[q = tr[p][x]] == len[p] + 1) fail[np] = q;
    else{
        nq = ++cnt;
        fail[nq] = fail[q];
        len[nq] = len[p] + 1;
        fail[q] = fail[np] = nq;
        memcpy(tr[nq], tr[q], sizeof(tr[q]));
        for(;p and tr[p][x] == q; p = fail[p]) tr[p][x] = nq;
    }
}

void tpsort( ){
    for(int i = 1; i <= cnt; i++)
        in[fail[i]]++;
    for(int i = 1; i <= cnt; i++)
        if(!in[i]) q.push(i);
    while(!q.empty()){
        int x = q.front( ); q.pop( );
        f[fail[x]] += f[x];
        in[fail[x]]--;
        if(!in[fail[x]]) q.push(fail[x]);
    }
}

int main( )<%

    cin >> s;

    for(int i = 0; i < (int)s.size( ); i++)
        insert(get(s[i]));

    tpsort();

    ll ans = 0; 
    for(int i = 2; i <= cnt; i++)
        if(f[i] > 1) ans = max(ans, (ll)f[i] * len[i]);

    cout << ans;

    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: 6ms
memory: 16712kb

input:

bdgedcfadbabbfgeacdgbggaefddebabbfgeacdgbefaecfddffeddacbabfcgecedacbffeddacbabfebadggfafabcdfdeaabdeecgbcecegcgecedacbfgdagbgagafdegecadfebcdbgfacdecdegecadfebbcdfdeaabdbfgcbccfcaebcecfdfccagdafaeaacbggaefddebcbecdafageeaabcbdafadcbecdbcgcbdgedcfadbcaefbdfcbgfcdeceddaaffgcedfcdcgdcgbfdddfdadgagbbef...

output:

5594

result:

ok answer is '5594'

Test #2:

score: 0
Accepted
time: 1ms
memory: 17228kb

input:

bdgfcbabegfbbbgecfbddbaceaefbebgeafdbbgaebebdabgebabacccebbaebeafbefaabdgfcbabegdbaceaefbegcaegagcdgcacccfbbfgffgcdgbccgecbdbcagbbcacccfbbfgeegfcaecbcebebdabgebbbebbgcfafbbbgbdbabgbabfgdfaggfbcbabeebbdaagacgbafecebfccdbgfacgcabefaaedadeacgdeegfcaecbcabacccebbacdbbdceeegcdbbdceeegbaccaecfbgbbebbgcfaf...

output:

7308

result:

ok answer is '7308'

Test #3:

score: 0
Accepted
time: 2ms
memory: 16564kb

input:

baeedcbgaeaabdcaeeagbeffgedegdfcggaeafeegccecbacaaaabdcaeeaggedcbbaebfbcbbbebeaeagedddgabgccdecfeegcababaddfcabcbbbebeaegabeddeedaaabebgcafgeefgeabcaafgcbcfaafgadddgdbccbcddfacfcgdeefgeabcaagbgbgdbefdcefcacafcagcfadegebcababaddfcaffbfgdfecefgafcfgddbagfgceabefcaaebagddabcbbbebeaedaddaacgfcabeffgfgeg...

output:

6011

result:

ok answer is '6011'

Test #4:

score: 0
Accepted
time: 5ms
memory: 14840kb

input:

fadabcedabffccgceafdfgebfgebdfffccgceafdfbabeebbccbcebdaabagbdcabbebbgbbdddddcfdfefcfgcaedcdfbfcgagggeacabgddfdggddgcgagfefgeafdaefefgeafdaefbabeebbccabccadccgcbbdddddcfdfadabcedabgbdegbcgdecfcefaedcffadabcedabadgbbacdfbfecccfacaaggggffddffffbcgacfgbcbeadagbfffefcfgcaedgeacabgddfgbcccdcgegbdcabbebbg...

output:

5874

result:

ok answer is '5874'

Test #5:

score: 0
Accepted
time: 3ms
memory: 15328kb

input:

efggbbfcabcdfbceagadfagaeegbegcbfbcfcgfbgdfffcdeagfcggffcacbbadedceffedbgafcbegdggabccbcecfcbfegdcbecdedfdeebebecffcaafgffabgbgedfcdabgbeffaagbffcdccaddcadgbbcadedgcfbgbdefggbbfcabddccdefedagebfbbfadfagagedffaagabcgbcffaggfebdbefdcfecegaeggggdacedbgfcdedfdeebececbfefeegdebddaeafbffabgbgedfcfcdgcaacc...

output:

5751

result:

ok answer is '5751'

Test #6:

score: -35
Wrong Answer
time: 1ms
memory: 17208kb

input:

eafdccagcbcaeebabcggdgdfcdfgeacbgcdfbgcabdegdbbaabgecbaaagffecffedeffcedcdgcecbgfedbdgabfdcbefcecdfdfaegccbfeefdccgfbfebecffedeffcbdegdbbaabeafcbegcbagecbaaagffefcdafgageffefbcceecdffabcbbdbefcdafgageedcdgcecbgcaeebabcggfbeegdaccfdffabcbbdbcbefcecdfdcdccfcbadcecffedeffcdcgaagfaegddecgffafcdgdfcdfgea...

output:

5755

result:

wrong answer expected '6156', found '5755'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%