Submission #493469

#	Time	Username	Problem	Language	Result	Execution time	Memory
493469		MasterTaster	Palindromes (APIO14_palindrome)	C++14	100 / 100	63 ms	63392 KiB

palindrome

#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 600010

using namespace std;

struct PalTree{

    struct Node{
        int len, cnt, to[26], dub, slink;
        Node() { len=0; cnt=0; dub=0; slink=0; for (int i=0; i<26; i++) to[i]=-1; }
        Node(int a, int b, int c, int d)
        {
            len=a; cnt=b; dub=c; slink=d;
            for (int i=0; i<26; i++) to[i]=-1;
        }
    };

    vector<Node> pt;
    int suff;
    int s[MAXN];
    int gde=0;

    void addLetter(int c)
    {
        //cout<<gde<<" "<<suff<<endl;
        s[gde]=c;
        while (gde-1-pt[suff].len < 0 || c!=s[gde-1-pt[suff].len])
            suff=pt[suff].slink;
        //cout<<suff<<endl;

        int slnd=pt[suff].to[c];
        if (slnd==-1)
        {
            slnd=pt.size();
            pt[suff].to[c]=slnd;
            pt.pb(Node(pt[suff].len+2, 0, 0, 0));
            if (suff==1)
                pt[slnd].slink=2;
            else
            {
                int pom=pt[suff].slink;
                while(c!=s[gde-1-pt[pom].len])
                    pom=pt[pom].slink;
                pt[slnd].slink=pt[pom].to[c];
                assert(pt[pom].to[c] != -1);
                //assert(pt[slnd].slink<pt.size());
            }
            pt[slnd].dub=pt[pt[slnd].slink].dub+1;
        }
        pt[slnd].cnt++;
        suff=slnd;
        gde++;
        //cout<<slnd<<" "<<pt[slnd].slink<<endl;
    }

    void calc()
    {
        for (int i=pt.size()-1; i>2; i--){  pt[pt[i].slink].cnt+=pt[i].cnt; }
    }
    void init()
    {
        pt.clear();
        pt.pb(Node(-1, -1, -1, -1));
        pt.pb(Node(-1, 0, 0, 1));
        pt.pb(Node(0, 0, 0, 1));
        suff=2;
    }

    Node &operator[](int idx) {
        return pt[idx];
    }
};
PalTree pt;
ll ress=-1;
string st;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>>st;

    pt.init();
    for (int i=0; i<st.size(); i++) pt.addLetter((int)(st[i]-'a'));
    pt.calc();

    for (int i=3; i<pt.pt.size(); i++)
    {
        ress=max(ress, ((ll)pt[i].cnt*pt[i].len));
    }

    cout<<ress;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i=0; i<st.size(); i++) pt.addLetter((int)(st[i]-'a'));
      |                   ~^~~~~~~~~~
palindrome.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PalTree::Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i=3; i<pt.pt.size(); i++)
      |                   ~^~~~~~~~~~~~~

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