oj.uz

Submission #209821

# Submission time Handle Problem Language Result Execution time Memory
209821 2020-03-15T15:47:05 Z jhnah917 Palindromes (APIO14_palindrome) C++14
73 / 100
 1000 ms 60960 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll p1 = 179, mod1 = 1e9-63;
const ll p2 = 917, mod2 = 1e9+7;

int n;
char s[606060];
int dp[606060];
ll ha1[303030], pw1[303030];
ll ha2[303030], pw2[303030];

int pv = 0;
map<pair<ll, ll>, int> mp;
int cnt[303030];
int len[303030];
int lnk[303030];
vector<int> g[303030];

void manacher(){
    for(int i=n-1; i>=0; i--){
        s[i << 1 | 1] = s[i];
        s[i << 1] = '#';
    }
    n <<= 1; s[n++] = '#';
    int r = -1, p = -1;
    for(int i=0; i<n; i++){
        dp[i] = (i <= r ? min(dp[p*2-i], r-i) : 0);
        while(i-dp[i]-1 >= 0 && i+dp[i]+1 < n && s[i-dp[i]-1] == s[i+dp[i]+1]) dp[i]++;
        if(i+dp[i] > r) r = i+dp[i], p = i;
    }
}
pair<ll, ll> substr(int l, int r){
    ll r1 = ha1[l] - ha1[r+1] * pw1[r-l+1]; r1 %= mod1; if(r1 < 0) r1 += mod1;
    ll r2 = ha2[l] - ha2[r+1] * pw2[r-l+1]; r2 %= mod2; if(r2 < 0) r2 += mod2;
    return {r1, r2};
}

void go(int s, int e, pair<ll, ll> now){
    if(e-s+1 <= 2) return;
    auto par = substr(s+1, e-1);
    int v = mp[now], u;
    if(!mp.count(par)){
        u = mp[par] = ++pv; len[u] = e-s-1;
    }else u = mp[par];
    if(lnk[v]) return; lnk[v] = 1;
    g[u].push_back(v);
    go(s+1, e-1, par);
}

int sz[303030];
int chk[303030];
void dfs(int v){
    sz[v] = cnt[v];
    chk[v] = 1;
    for(auto i : g[v]){
        if(chk[i]) continue;
        dfs(i); sz[v] += sz[i];
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> s; n = strlen(s);
    pw1[0] = 1, pw1[1] = p1;
    pw2[0] = 1, pw2[1] = p2;
    for(int i=n-1; i>=0; i--) ha1[i] = (ha1[i+1] * p1 + s[i]) % mod1;
    for(int i=2; i<=n; i++) pw1[i] = pw1[i-1] * p1 % mod1;
    for(int i=n-1; i>=0; i--) ha2[i] = (ha2[i+1] * p2 + s[i]) % mod2;
    for(int i=2; i<=n; i++) pw2[i] = pw2[i-1] * p2 % mod2;
    manacher();

    //for(int i=0; i<n; i++) cout << s[i] << " "; cout << "\n";
    //for(int i=0; i<n; i++) cout << dp[i] << " "; cout << "\n";

    for(int i=0; i<n; i++){
        if(!dp[i]) continue;
        int s, e;
        if(i & 1) s = i/2-dp[i]/2, e = i/2+dp[i]/2;
        else{
            s = i-1, e = i+1; s /= 2, e /= 2;
            s -= dp[i]/2-1;
            e += dp[i]/2-1;
        }
        auto now = substr(s, e);
        if(!mp.count(now)){
            mp[now] = ++pv; len[mp[now]] = e-s+1;
        }
        cnt[mp[now]]++;
        go(s, e, now);
    }

    ll ans = 0;
    for(int i=1; i<=pv; i++) if(!sz[i]) dfs(i);
    for(int i=1; i<=pv; i++){
        ans = max(ans, (ll)len[i] * sz[i]);
    }
    cout << ans;
};

// banana

Compilation message

palindrome.cpp: In function 'void go(int, int, std::pair<long long int, long long int>)':
palindrome.cpp:47:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(lnk[v]) return; lnk[v] = 1;
     ^~
palindrome.cpp:47:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     if(lnk[v]) return; lnk[v] = 1;
                        ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 9 ms 7548 KB Output is correct
4 Correct 9 ms 7548 KB Output is correct
5 Correct 9 ms 7544 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Correct 9 ms 7544 KB Output is correct
8 Correct 9 ms 7544 KB Output is correct
9 Correct 9 ms 7544 KB Output is correct
10 Correct 9 ms 7544 KB Output is correct
11 Correct 9 ms 7544 KB Output is correct
12 Correct 9 ms 7544 KB Output is correct
13 Correct 9 ms 7544 KB Output is correct
14 Correct 9 ms 7548 KB Output is correct
15 Correct 9 ms 7544 KB Output is correct
16 Correct 9 ms 7544 KB Output is correct
17 Correct 9 ms 7544 KB Output is correct
18 Correct 9 ms 7544 KB Output is correct
19 Correct 9 ms 7544 KB Output is correct
20 Correct 9 ms 7544 KB Output is correct
21 Correct 10 ms 7544 KB Output is correct
22 Correct 9 ms 7544 KB Output is correct
23 Correct 10 ms 7544 KB Output is correct
24 Correct 9 ms 7544 KB Output is correct
25 Correct 9 ms 7544 KB Output is correct
26 Correct 9 ms 7544 KB Output is correct
27 Correct 9 ms 7544 KB Output is correct
28 Correct 9 ms 7544 KB Output is correct
29 Correct 9 ms 7544 KB Output is correct
30 Correct 9 ms 7544 KB Output is correct
31 Correct 9 ms 7544 KB Output is correct
32 Correct 9 ms 7544 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7672 KB Output is correct
2 Correct 10 ms 7672 KB Output is correct
3 Correct 10 ms 7672 KB Output is correct
4 Correct 10 ms 7672 KB Output is correct
5 Correct 11 ms 7676 KB Output is correct
6 Correct 10 ms 7672 KB Output is correct
7 Correct 9 ms 7672 KB Output is correct
8 Correct 10 ms 7672 KB Output is correct
9 Correct 10 ms 7672 KB Output is correct
10 Correct 9 ms 7544 KB Output is correct
11 Correct 9 ms 7544 KB Output is correct
12 Correct 10 ms 7672 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 9340 KB Output is correct
2 Correct 22 ms 9208 KB Output is correct
3 Correct 28 ms 9336 KB Output is correct
4 Correct 28 ms 9208 KB Output is correct
5 Correct 16 ms 9464 KB Output is correct
6 Correct 19 ms 9336 KB Output is correct
7 Correct 22 ms 9080 KB Output is correct
8 Correct 11 ms 7928 KB Output is correct
9 Correct 11 ms 7928 KB Output is correct
10 Correct 15 ms 8828 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 25336 KB Output is correct
2 Correct 222 ms 24312 KB Output is correct
3 Correct 310 ms 25336 KB Output is correct
4 Correct 298 ms 24444 KB Output is correct
5 Correct 123 ms 25852 KB Output is correct
6 Correct 111 ms 20988 KB Output is correct
7 Correct 187 ms 21880 KB Output is correct
8 Correct 24 ms 11768 KB Output is correct
9 Correct 69 ms 14712 KB Output is correct
10 Correct 111 ms 23288 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 60960 KB Output is correct
2 Correct 806 ms 55800 KB Output is correct
3 Execution timed out 1098 ms 60876 KB Time limit exceeded
4 Halted 0 ms 0 KB -