제출 #752801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
752801		Username4132	회문 (APIO14_palindrome)	C++14	73 / 100	263 ms	131072 KiB

palindrome

#include<iostream>
#include<vector>
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)
#define PB push_back

struct trie{
    int cnt=0, total=0, pos;
    int up[20], nxt[28]={0};
    trie(int Pos) : pos(Pos) {}
};

const int MAXN=600015;
int n, l=1, r=1, len[MAXN];
ll ans;
trie *root, *pal[MAXN];
string str, aux;
vector<trie*> bol;

void dfs(trie* v, int d, bool yes){
    v->total=v->cnt;
    forn(i, 28) if(v->nxt[i]){
        dfs(bol[v->nxt[i]], d+1, yes^1);
        v->total+=bol[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(0);
    bol.PB(root);
    forn(i, 20) root->up[i]=0;
    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=bol[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]==0){
                cur->nxt[pos]=bol.size();
                bol.PB(new trie(bol.size()));
                int* ptr=bol[cur->nxt[pos]]->up;
                ptr[0]=cur->pos;
                forn(j, 19) ptr[j+1]=bol[ptr[j]]->up[j];
            }
            cur=bol[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(bol[root->nxt[i]], 1, true);
    if(root->nxt[26]) dfs(bol[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