oj.uz

Submission #13163

# Submission time Handle Problem Language Result Execution time Memory
13163 2015-02-01T10:51:42 Z gs14004 Palindromes (APIO14_palindrome) C++14
47 / 100
 1000 ms 23344 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int,int> pi;

char str[600005];
int n;
int dp[600005];

void manacher(){
    int max_val = 0, pos = 0;
    for (int i=1; i<=n; i++) {
        int ret = i;
        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, ret = max_val;
        }
    }
    for (int i=1; i<=n; i++) {
        if(i%2 == 0) dp[i]++;
        dp[i] /= 2;
    }
}

const int prime = 811;
const long long mod = 1e15 + 811;
long long hs[300005], pw[300005];

unordered_map<long long,int> len, cnt, num;
unordered_map<long long,long long> nxt;
vector<long long> hash_candidate;

int piv;

long long gob(long long b1, long long b2){
    long long r = 0;
    while (b1) {
        r += b2 * (b1 & 255);
        b2 <<= 8;
        b1 >>= 8;
        b2 %= mod;
        r %= mod;
    }
    return r;
}

long long get_hash(int s, int e){
    return ((hs[e] - gob(hs[s-1],pw[e - s + 1])) % mod + mod) % mod;
}

void shrink(int s, int e, long long pa){
    if(s > e) return;
    long long par = 0;
    num[0] = 0;
    cnt[get_hash(s,e)]++;
    while (s <= e) {
        long long hsh = get_hash(s,e);
        hash_candidate.push_back(hsh);
        if(par) nxt[par] = hsh;
        if(len.find(hsh) == len.end()){
            len[hsh] = e - s + 1;
            num[hsh] = ++piv;
        }
        else break;
        par = hsh;
        s++;
        e--;
    }
}

int tpar[300005], tcnt[300005], tlen[300005];
vector<int> graph[300005];
int subsize[300005];
long long ret;

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);
    }
    subsize[x] = r;
    // printf("%d %d\n",subsize[x],tlen[x]);
    ret = max(ret,1ll * subsize[x] * tlen[x]);
    return r;
}

void make_tree(){
    for (long long i : hash_candidate){
        tpar[num[i]] = num[nxt[i]];
        tcnt[num[i]] = cnt[i];
        tlen[num[i]] = len[i];
    }
    for (int i=0; i<=piv; i++) {
        if (i == tpar[i]) continue;
        graph[i].push_back(tpar[i]);
        graph[tpar[i]].push_back(i);
    }
    dfs(0,-1);
}

int main(){
    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] = 1;
    for (int i=1; i<=(n+1)/2; i++) {
        hs[i] = (hs[i-1] * prime + str[2*i-1]) % mod;
        pw[i] = pw[i-1] * prime % 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);
        }
    }
    make_tree();
    printf("%lld",ret);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 23344 KB Output is correct - answer is '12497500'
2 Correct 59 ms 23260 KB Output is correct - answer is '6481800'
3 Correct 157 ms 23304 KB Output is correct - answer is '25000000'
4 Correct 126 ms 23252 KB Output is correct - answer is '17816841'
5 Correct 18 ms 23288 KB Output is correct - answer is '9945'
6 Correct 17 ms 23240 KB Output is correct - answer is '504100'
7 Correct 33 ms 23208 KB Output is correct - answer is '1512930'
8 Correct 9 ms 21060 KB Output is correct - answer is '413'
9 Correct 5 ms 21056 KB Output is correct - answer is '428'
10 Correct 15 ms 22476 KB Output is correct - answer is '7232'

Subtask #4
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 20920 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -