Submission #331149

#	Time	Username	Problem	Language	Result	Execution time	Memory
331149		couplefire	Palindromes (APIO14_palindrome)	C++17	100 / 100	59 ms	40552 KiB

palindrome

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

template<int SZ> struct PalTree{
    static const int sigma = 26;
    int s[SZ], len[SZ], link[SZ], to[SZ][sigma], oc[SZ];
    int n, last, sz;
    PalTree(){
        s[n++] = -1;
        link[0] = 1;
        len[1] = -1;
        sz = 2;
    }
    int getLink(int v){
        while(s[n-len[v]-2] != s[n-1]) v = link[v];
        return v;
    }
    void add(int c){
        s[n++] = c;
        last = getLink(last);
        if(!to[last][c]){
            len[sz] = len[last]+2;
            link[sz] = to[getLink(link[last])][c];
            to[last][c] = sz++;
        }
        last = to[last][c];
        oc[last]++;
    }
    void prop(){
        vector<pair<int, int>> v;
        for(int i = 2; i<sz; i++) v.push_back({len[i], i});
        sort(v.begin(), v.end()); reverse(v.begin(), v.end());
        for(auto a : v) oc[link[a.second]] += oc[a.second];
    }
};

PalTree<MAXN> tree;
string s;

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    for(int i = 0; i<s.length(); i++){
        tree.add(s[i]-'a');
    }
    tree.prop();
    long long ans = 0;
    for(int i = 2; i<tree.sz; i++){
        ans = max(ans, 1ll*tree.len[i]*tree.oc[i]);
    }
    cout << ans << endl;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0; i<s.length(); i++){
      |                    ~^~~~~~~~~~~
palindrome.cpp: In constructor 'PalTree<SZ>::PalTree() [with int SZ = 300005]':
palindrome.cpp:10:11: warning: '*<unknown>.PalTree<300005>::n' is used uninitialized in this function [-Wuninitialized]
   10 |         s[n++] = -1;
      |           ^

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