Submission #752788

#	Time	Username	Problem	Language	Result	Execution time	Memory
752788		Username4132	Palindromes (APIO14_palindrome)	C++14	73 / 100	147 ms	131072 KiB

palindrome

#include<iostream>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)

struct trie{
    int cnt=0, total=0;
    trie *up[20], *nxt[28]={0};
};

const int MAXN=1200015;
int n, l=1, r=1, len[MAXN];
ll ans;
trie *root, *pal[MAXN];
string str, aux;

void dfs(trie* v, int d, bool yes){
    v->total=v->cnt;
    forn(i, 28) if(v->nxt[i]){
        dfs(v->nxt[i], d+1, yes^1);
        v->total+=v->nxt[i]->total;
    }
    if(yes) ans=max(ans, ((ll)d)*v->total);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> aux;
    str.resize(2*aux.size() + 1);
    str[0]='$';
    forn(i, aux.size()) str[2*i+1]=aux[i];
    forn(i, aux.size()-1) str[2*i + 2]='z'+1;
    str.back()='^';
    n = str.size();
    root = new trie;
    forn(i, 20) root->up[i]=root;
    forsn(i, 1, n-1){
        trie* cur=NULL;
        if(i>=r) cur=root;
        else{
            len[i]=min(r-i, len[l+r-i]);
            cur=pal[l+r-i];
            int goUp=len[l+r-i]-len[i];
            dforn(j, 20) if(goUp>=(1<<j)) goUp-=(1<<j), cur=cur->up[j];
        }
        while(str[i+len[i]]==str[i-len[i]]){
            int pos=str[i+len[i]]-'a';
            ++len[i];
            if(cur->nxt[pos]==NULL){
                cur->nxt[pos]=new trie;
                trie** ptr=cur->nxt[pos]->up;
                ptr[0]=cur;
                forn(j, 19) ptr[j+1]=ptr[j]->up[j];
            }
            cur=cur->nxt[pos];
        }
        if(i+len[i]>r) r=i+len[i], l=i-len[i];
        pal[i]=cur;
        cur->cnt++;
    }
    forn(i, 26) if(root->nxt[i]) dfs(root->nxt[i], 1, true);
    if(root->nxt[26]) dfs(root->nxt[26], 1, false);
    cout << ans << '\n';
}

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