oj.uz

Submission #17973

# Submission time Handle Problem Language Result Execution time Memory
17973 2016-01-16T03:06:47 Z yswon Palindromes (APIO14_palindrome) C++14
100 / 100
 327 ms 50628 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int,int> pi;
#define MAXN 300005
char str[2*MAXN];
int n;
int dp[2*MAXN];

void manacher(){
    int max_val = 0, pos = 0;
    for (int i=1; i<=n; i++) {
        //ret은 현재 커버 범위
        int ret = i;
        //max_val은 이전 팰린드롬의 최대 커버 범위
        if(max_val >= i){
            ret = min(max_val,i + dp[2 * pos - i]);
        }
        while (ret+1<=n && 2*i-ret-1> 0 && str[ret+1] == str[2*i-ret-1]){
            ret++;
        }
        dp[i] = ret - i;
        if(ret > max_val){
            pos = i, max_val = ret;
        }
    }
    //짝수 길이의 팰린드롬에서도 적용할 수 있도록 문자 사이에 공백을 추가 했기 때문에 다시 변환 해줌
    //나누기 2를 해서 2n, 2n+1은 n으로 변환한다.
    for (int i=1; i<=n; i++) {
        if(i%2 == 0) dp[i]++;
        dp[i] /= 2;
    }
}

const int prime = 613;
const int prime2 = 409;
const int mod = 1e9 + 613;

int hs[MAXN], pw[MAXN];
int hs2[MAXN], pw2[MAXN];

long long get_hash(int s, int e){
    if(s > e) return 0;
    int hash1 = ((hs[e] - 1ll * hs[s-1] * pw[e - s + 1]) % mod + mod) % mod;
    int hash2 = ((hs2[e] - 1ll * hs2[s-1] * pw2[e - s + 1]) % mod + mod) % mod;
    return 1ll * hash1 * mod + hash2;
}

unordered_map<long long,int> num;
int piv;

int tcnt[MAXN], tlen[MAXN];
vector<int> graph[MAXN];
long long ret;

void shrink(int s, int e, long long pa){
    if(s > e) return;
    long long par = 0;
    num[0] = 0;
    int st = 1;
    while (s <= e) {
        long long hsh = get_hash(s,e);
        int npar = num[par], nhsh = 0;
        if(num.find(hsh) != num.end()){
            nhsh = num[hsh];
            if(par){
                graph[npar].push_back(nhsh);
                graph[nhsh].push_back(npar);
            }
            if(st){
                tcnt[nhsh]++;
            }
            break;
        }
        nhsh = num[hsh] = ++piv;
        if(par){
            graph[npar].push_back(nhsh);
            graph[nhsh].push_back(npar);
        }
        if(st){
            tcnt[nhsh]++;
            st = 0;
        }
        tlen[nhsh] = e - s + 1;
        par = hsh;
        s++;
        e--;
    }
    if(s > e){
        graph[0].push_back(num[par]);
        graph[num[par]].push_back(0);
    }
}

int dfs(int x, int pa){
    int r = tcnt[x];
    for (int i=0; i<graph[x].size(); i++) {
        if(graph[x][i] == pa) continue;
        r += dfs(graph[x][i],x);
    }
    ret = max(ret,1ll * r * tlen[x]);
    return r;
}

int main(){
    num[0] = 0;
    scanf("%s",str);
    n = (int)strlen(str);
    for (int i=n-1; i>=0; i--) {
        str[2*i+1] = str[i];
        str[2*i] = ' ';
    }
    n = 2 * n - 1;
    str[0] = 0;
    manacher();
    pw[0] = pw2[0] = 1;
    for (int i=1; i<=(n+1)/2; i++) {
        hs[i] = (1ll * hs[i-1] * prime + str[2*i-1]) % mod;
        hs2[i] = (1ll * hs2[i-1] * prime2 + str[2*i-1]) % mod;
        pw[i] = 1ll * pw[i-1] * prime % mod;
        pw2[i] = 1ll * pw2[i-1] * prime2 % mod;
    }
    for (int i=1; i<=n; i++) {
        if(i % 2 == 1){
            shrink((i+1)/2 - dp[i],(i+1)/2 + dp[i],0);
        }
        else{
            shrink(i/2 + 1 - dp[i], i/2 + dp[i],0);
        }
    }
    dfs(0,-1);
    printf("%lld",ret);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18576 KB Output is correct - answer is '7'
2 Correct 3 ms 18576 KB Output is correct - answer is '4'
3 Correct 0 ms 18576 KB Output is correct - answer is '9'
4 Correct 3 ms 18576 KB Output is correct - answer is '1'
5 Correct 0 ms 18576 KB Output is correct - answer is '1'
6 Correct 1 ms 18576 KB Output is correct - answer is '2'
7 Correct 0 ms 18576 KB Output is correct - answer is '3'
8 Correct 3 ms 18576 KB Output is correct - answer is '3'
9 Correct 4 ms 18576 KB Output is correct - answer is '15'
10 Correct 3 ms 18576 KB Output is correct - answer is '24'
11 Correct 0 ms 18576 KB Output is correct - answer is '10'
12 Correct 0 ms 18576 KB Output is correct - answer is '24'
13 Correct 0 ms 18576 KB Output is correct - answer is '25'
14 Correct 4 ms 18576 KB Output is correct - answer is '28'
15 Correct 0 ms 18576 KB Output is correct - answer is '2'
16 Correct 3 ms 18576 KB Output is correct - answer is '1'
17 Correct 0 ms 18576 KB Output is correct - answer is '15'
18 Correct 0 ms 18576 KB Output is correct - answer is '18'
19 Correct 0 ms 18576 KB Output is correct - answer is '1176'
20 Correct 0 ms 18576 KB Output is correct - answer is '1225'
21 Correct 0 ms 18576 KB Output is correct - answer is '136'
22 Correct 0 ms 18576 KB Output is correct - answer is '45'
23 Correct 4 ms 18576 KB Output is correct - answer is '2500'
24 Correct 0 ms 18576 KB Output is correct - answer is '380'
25 Correct 0 ms 18576 KB Output is correct - answer is '2304'
26 Correct 4 ms 18576 KB Output is correct - answer is '110'
27 Correct 0 ms 18576 KB Output is correct - answer is '93'
28 Correct 0 ms 18576 KB Output is correct - answer is '729'
29 Correct 0 ms 18576 KB Output is correct - answer is '132'
30 Correct 0 ms 18576 KB Output is correct - answer is '7'
31 Correct 4 ms 18576 KB Output is correct - answer is '8'
32 Correct 4 ms 18576 KB Output is correct - answer is '64'

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18576 KB Output is correct - answer is '124251'
2 Correct 4 ms 18576 KB Output is correct - answer is '38226'
3 Correct 4 ms 18576 KB Output is correct - answer is '249500'
4 Correct 0 ms 18576 KB Output is correct - answer is '5778'
5 Correct 0 ms 18576 KB Output is correct - answer is '247506'
6 Correct 2 ms 18576 KB Output is correct - answer is '248004'
7 Correct 0 ms 18576 KB Output is correct - answer is '973'
8 Correct 0 ms 18576 KB Output is correct - answer is '123753'
9 Correct 4 ms 18576 KB Output is correct - answer is '2346'
10 Correct 0 ms 18576 KB Output is correct - answer is '53'
11 Correct 0 ms 18576 KB Output is correct - answer is '52'
12 Correct 4 ms 18576 KB Output is correct - answer is '976'

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19412 KB Output is correct - answer is '12497500'
2 Correct 10 ms 19324 KB Output is correct - answer is '6481800'
3 Correct 5 ms 19412 KB Output is correct - answer is '25000000'
4 Correct 0 ms 19364 KB Output is correct - answer is '17816841'
5 Correct 8 ms 19360 KB Output is correct - answer is '9945'
6 Correct 6 ms 19304 KB Output is correct - answer is '504100'
7 Correct 8 ms 19224 KB Output is correct - answer is '1512930'
8 Correct 5 ms 18576 KB Output is correct - answer is '413'
9 Correct 3 ms 18576 KB Output is correct - answer is '428'
10 Correct 9 ms 19036 KB Output is correct - answer is '7232'

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 28752 KB Output is correct - answer is '1249925001'
2 Correct 69 ms 27392 KB Output is correct - answer is '396337935'
3 Correct 76 ms 28752 KB Output is correct - answer is '2500050000'
4 Correct 83 ms 27628 KB Output is correct - answer is '1016525689'
5 Correct 50 ms 27788 KB Output is correct - answer is '99645'
6 Correct 57 ms 24936 KB Output is correct - answer is '78569380'
7 Correct 62 ms 25276 KB Output is correct - answer is '82810000'
8 Correct 16 ms 18576 KB Output is correct - answer is '3989'
9 Correct 24 ms 20840 KB Output is correct - answer is '125529616'
10 Correct 52 ms 26760 KB Output is correct - answer is '66664'

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 50624 KB Output is correct - answer is '11250075000'
2 Correct 265 ms 43892 KB Output is correct - answer is '894243195'
3 Correct 327 ms 50624 KB Output is correct - answer is '22499400004'
4 Correct 303 ms 44652 KB Output is correct - answer is '2958163321'
5 Correct 219 ms 49444 KB Output is correct - answer is '298935'
6 Correct 248 ms 41316 KB Output is correct - answer is '1210831209'
7 Correct 201 ms 37900 KB Output is correct - answer is '303195156'
8 Correct 49 ms 18576 KB Output is correct - answer is '11804'
9 Correct 52 ms 18576 KB Output is correct - answer is '11813'
10 Correct 211 ms 43948 KB Output is correct - answer is '262144'
11 Correct 277 ms 50628 KB Output is correct - answer is '3750025000'
12 Correct 68 ms 21256 KB Output is correct - answer is '184796836'