Submission #47587

#	Time	Username	Problem	Language	Result	Execution time	Memory
47587		TAMREF	Palindromes (APIO14_palindrome)	C++11	23 / 100	1086 ms	15040 KiB

palindrome

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

typedef long long ll;

const char g = 'a' + 26;
const ll o = 28LL;
const ll h[2] = {1000000007LL, 1610612741LL};
const ll io[2] = {35714286LL, 1323003323LL};
const int mx = 6e5 + 5;



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

void init_hash(){
    for(int b = 0; b < 2; b++){
        ph[b][0] = 1;
        iph[b][0] = 1;
        for(int i = 1; i < mx; i++){
            ph[b][i] = ph[b][i-1] * o % h[b];
            if(i <= 2) iph[b][i] = iph[b][i-1] * io[b] % h[b];
        }
    }
}

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;
        }
    }
    #ifdef TAMREF
    puts(S);
    for(int i = 0; i < n; i++) printf("%d ",R[i]);
    puts("");
    #endif
}

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 = 0; i < n; i++) S[i] -= 'a'-1;

    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 hv[2] = {0,0}, tmp;
        int child_i = -1;
        int tmp_i;
        int flag_once = 1, keep_loop = 1;

        for(int b = 0; b < 2; b++){
            for(int j = s; j <= e; j++){
                hv[b] = (hv[b] * o + S[j]) % h[b];
            }
        }

        while(e >= s){
            tmp = (hv[0] << 32 | hv[1]);
            tmp_i = I[tmp];
            if(!tmp_i){ //insert new hash value
                #ifdef TAMREF
                printf("%d-th HASH : [%d, %d],\nhash string = ",cnt.size(),s,e);
                for(int j = s; j <= e; j++) printf("%c",S[j] + 'a' - 1);
                puts("");
                #endif // TAMREF
                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;
            for(int b = 0; b < 2; b++){
                hv[b] -= (S[e] + o * S[e-1] + ph[b][e-s] * S[s] + ph[b][e-s-1] * S[s+1]) % h[b];
                hv[b] = (hv[b] * iph[b][2] % h[b] + h[b]) % h[b];
            }
            e -= 2;
            s += 2;
        }
    }
}

int vis[mx];
ll ans = 1;

int dfs(int x){
    #ifdef TAMREF
    printf("dfs : %d\n",x);
    #endif // TAMREF
    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++){
        #ifdef TAMREF
        printf("%d - th node : cnt = %d, len = %d, isRoot = %d\n",i,cnt[i],len[i],isRoot[i]);
        #endif // TAMREF
        if(isRoot[i] && !vis[i]){
            #ifdef TAMREF
            printf("dfs start on %d\n",i);
            #endif // TAMREF
            dfs(i);
        }
    }
    printf("%lld\n",ans);
}

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

Compilation message (stderr)

palindrome.cpp: In function 'void input()':
palindrome.cpp:32: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: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27