oj.uz

답안 #47582

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
47582 2018-05-05T06:29:48 Z TAMREF 회문 (APIO14_palindrome) C++11
0 / 100
 1000 ms 131072 KB 
#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];
            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);

inline ll enc(ll *h){
    return h[0] << 32 | h[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;

        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 = enc(hv);
            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;
            }

            flag_once = 0;

            if(child_i != -1){
                gph[tmp_i].push_back(child_i);
                isRoot[child_i] = 0;
            }
            if(e - 2 < s + 2) break;
            child_i = tmp_i;
            for(int b = 0; b < 2; b++){
                hv[b] -= S[e] + o * S[e-1];
                hv[b] -= (ph[b][e-s] * S[s] + ph[b][e-s-1] * S[s+1]) % h[b];
                hv[b] = (hv[b] % 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]){
        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

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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 19192 KB Output is correct
2 Correct 21 ms 19300 KB Output is correct
3 Correct 20 ms 19300 KB Output is correct
4 Correct 20 ms 19300 KB Output is correct
5 Correct 20 ms 19300 KB Output is correct
6 Correct 21 ms 19300 KB Output is correct
7 Correct 22 ms 19316 KB Output is correct
8 Correct 20 ms 19316 KB Output is correct
9 Incorrect 20 ms 19316 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 214 ms 48192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1100 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1035 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1020 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -