Submission #47589

#	Time	Username	Problem	Language	Result	Execution time	Memory
47589		TAMREF	Palindromes (APIO14_palindrome)	C++11	100 / 100	404 ms	64588 KiB

palindrome

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

typedef long long ll;

const char g = 'a' + 26;
const ll o[2] = {613LL, 409LL};
const ll h = 1e9 + 613;
const int mx = 6e5 + 5;

char S[mx], P[mx];
int n, m;

void input(){
    scanf("%s",P); m = strlen(P);
    for(int i = 0; i < m; i++){
        S[2*i] = g;
        S[2*i+1] = P[i];
    }
    S[2*m] = g;
    n = 2 * m + 1;
}

int R[mx];

void Manacher(){
    int r = 0, j = 0;
    for(int i = 1; i < n; i++){
        int &h = R[i];
        if(i <= r) h = min(r - i, R[2*j - i]);
        while(i-h-1 >= 0 && i+h+1 < n && S[i-h-1] == S[i+h+1]) ++h;
        if(i + h > r){
            j = i;
            r = i + h;
        }
    }
}

ll ph[2][mx], hs[2][mx];

void init_hash(){
    for(int i = 0; i < n; i++) S[i] -= 'a'-1;

    for(int b = 0; b < 2; b++){
        ph[b][0] = 1;
        hs[b][0] = S[0];
        for(int i = 1; i < n; i++){
            ph[b][i] = ph[b][i-1] * o[b] % h;
            hs[b][i] = (hs[b][i-1] * o[b] + S[i]) % h;
        }
    }
}

inline ll enc(int s, int e){
    ll H[2];
    for(int b = 0; b < 2; b++){
        H[b] = ((hs[b][e] - hs[b][s-1] * ph[b][e-s+1]) % h + h) % h;
    }
    return H[0] * h + H[1];
}

unordered_map<ll,int> I;
vector<int> cnt(1);
vector<int> len(1);
vector<vector<int>> gph(1);
vector<int> isRoot(1);

void Shrink(){
    for(int i = 1, s, e; i < n-1; i++){
        if(!R[i]) continue;
        s = i - R[i] + 1, e = i + R[i] - 1;

        ll tmp;
        int child_i = -1;
        int tmp_i;
        int flag_once = 1, keep_loop = 1;

        while(e >= s){
            tmp = enc(s,e);
            tmp_i = I[tmp];
            if(!tmp_i){
                tmp_i = I[tmp] = cnt.size();
                cnt.push_back(flag_once);
                len.push_back((e-s)/2 + 1);
                gph.push_back(vector<int>());
                isRoot.push_back(1);
            }else{
                cnt[tmp_i] += flag_once;
                keep_loop = 0;
            }

            flag_once = 0;

            if(child_i != -1){
                gph[tmp_i].push_back(child_i);
                isRoot[child_i] = 0;
            }

            if(!keep_loop || e - 2 < s + 2) break;

            child_i = tmp_i;

            e -= 2;
            s += 2;
        }
    }
}

int vis[mx];
ll ans = 1;

int dfs(int x){
    ll c = cnt[x];
    vis[x] = 1;
    for(int &u : gph[x]){
        if(!vis[u]) c += dfs(u);
    }
    ans = max(ans, c * len[x]);
    return c;
}

void pro(){
    int N = cnt.size();
    for(int i = 1; i < N; i++){
        if(isRoot[i] && !vis[i]){
            dfs(i);
        }
    }
    printf("%lld\n",ans);
}

int main(){
    input();
    Manacher();
    init_hash();
    Shrink();
    pro();
}

Compilation message (stderr)

palindrome.cpp: In function 'void input()':
palindrome.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",P); m = strlen(P);
     ~~~~~^~~~~~~~

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