Submission #1102774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102774		vjudge1	Palindromes (APIO14_palindrome)	C++17	100 / 100	32 ms	40528 KiB

palindrome

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Mod 51123987

const int MAXN = 300000 , MAXK = 26;
char str[ MAXN + 5 ];
struct Palindromes_Automaton {
    int Size , Last , Root0 , Root1 , Trans[ MAXN + 5 ][ MAXK + 5 ] , Link[ MAXN + 5 ];
    int Len[ MAXN + 5 ] , Cnt[ MAXN + 5 ];

    Palindromes_Automaton( ) {
        Root0 = Size ++ , Root1 = Size ++; Last = Root1;
        Len[ Root0 ] = 0  , Link[ Root0 ] = Root1;
        Len[ Root1 ] = -1 , Link[ Root1 ] = Root1; 
    }

    void Extend( int ch , int dex ) {
        int u = Last;
        for( ; str[ dex ] != str[ dex - Len[ u ] - 1 ] ; u = Link[ u ] );
        if( !Trans[ u ][ ch ] ) {
            int Newnode = ++ Size , v = Link[ u ];
            Len[ Newnode ] = Len[ u ] + 2;
            for( ; str[ dex ] != str[ dex - Len[ v ] - 1 ] ; v = Link[ v ] );
            Link[ Newnode ] = Trans[ v ][ ch ]; Trans[ u ][ ch ] = Newnode;
        }
        Last = Trans[ u ][ ch ];
        Cnt[ Last ] ++;
    }
    void Build( char *str ) {
        int len = strlen( str );
        for( int i = 0 ; i < len ; i ++ )
            Extend( str[ i ] - 'a' + 1 , i );
    }
    long long Calc( ) {
        long long Ans = 0;
        for( int i = Size ; i >= 0 ; i -- )
            Cnt[ Link[ i ] ] += Cnt[ i ] , Ans = max( Ans , 1ll * Cnt[ i ] * Len[ i ] );
        return Ans;
    }
}PAM;

int main() {
    scanf("%s", str );
    PAM.Build( str );
    printf("%lld", PAM.Calc( ) );
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%s", str );
      |     ~~~~~^~~~~~~~~~~~
palindrome.cpp: In constructor 'Palindromes_Automaton::Palindromes_Automaton()':
palindrome.cpp:14:17: warning: '*<unknown>.Palindromes_Automaton::Size' is used uninitialized in this function [-Wuninitialized]
   14 |         Root0 = Size ++ , Root1 = Size ++; Last = Root1;
      |                 ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27