Submission #112437

#	Time	Username	Problem	Language	Result	Execution time	Memory
112437		Akashi	Palindromes (APIO14_palindrome)	C++14	100 / 100	111 ms	66732 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;


struct Node{
    vector <int> v;
    int son[26];
    int num, length, link;
};

Node PalTree[300005];
char s[300005];


void initialize_tree(){
    PalTree[1].length = -1; PalTree[1].link = 1;
    PalTree[2].length = 0; PalTree[2].link = 1;
}

int Last = 2, tree_size = 2;
void add_letter(int pos){
    char ch = s[pos] - 'a';

    while(true){
        if(pos - PalTree[Last].length - 1 >= 0 && s[pos] == s[pos - PalTree[Last].length - 1]) break ;
        Last = PalTree[Last].link;
    }

    if(PalTree[Last].son[ch]){
        PalTree[PalTree[Last].son[ch]].num++;
        Last = PalTree[Last].son[ch];
        return ;
    }

    int cur = ++tree_size;
    PalTree[Last].son[ch] = cur;
    PalTree[cur].length = PalTree[Last].length + 2;
    PalTree[cur].num = 1;

    if(Last == 1){
        PalTree[2].v.push_back(cur);
        PalTree[cur].link = 2;
        Last = cur;
        return ;
    }

    while(true){
        Last = PalTree[Last].link;
        if(pos - PalTree[Last].length - 1 >= 0 && s[pos] == s[pos - PalTree[Last].length - 1]){
            PalTree[cur].link = PalTree[Last].son[ch];
            PalTree[PalTree[cur].link].v.push_back(cur);
            break ;
        }
    }
    Last = cur;
}

long long Sol = 0;
void dfs(int nod = 2){
    for(auto it : PalTree[nod].v){
        dfs(it);
        PalTree[nod].num += PalTree[it].num;
    }
    Sol = max(Sol, 1LL * PalTree[nod].length * PalTree[nod].num);
}

int main()
{
//    freopen("palindrome.in", "r", stdin);
//    freopen("palindrome.out", "w", stdout);

    initialize_tree();

    scanf("%s", s);
    int L = strlen(s);
    for(int i = 0; i < L ; ++i) add_letter(i);

    dfs();

    printf("%lld", Sol);

    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'void add_letter(int)':
palindrome.cpp:29:28: warning: array subscript has type 'char' [-Wchar-subscripts]
     if(PalTree[Last].son[ch]){
                            ^
palindrome.cpp:30:37: warning: array subscript has type 'char' [-Wchar-subscripts]
         PalTree[PalTree[Last].son[ch]].num++;
                                     ^
palindrome.cpp:31:36: warning: array subscript has type 'char' [-Wchar-subscripts]
         Last = PalTree[Last].son[ch];
                                    ^
palindrome.cpp:36:25: warning: array subscript has type 'char' [-Wchar-subscripts]
     PalTree[Last].son[ch] = cur;
                         ^
palindrome.cpp:50:53: warning: array subscript has type 'char' [-Wchar-subscripts]
             PalTree[cur].link = PalTree[Last].son[ch];
                                                     ^
palindrome.cpp: In function 'int main()':
palindrome.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
     ~~~~~^~~~~~~~~

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