oj.uz

Submission #234849

# Submission time Handle Problem Language Result Execution time Memory
234849 2020-05-26T01:10:39 Z jhnah917 Palindromes (APIO14_palindrome) C++14
100 / 100
 331 ms 68268 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#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;
 
struct pair_hash{
  template <typename T1, typename T2>
  size_t operator () (const pair<T1, T2> &t) const {
    return std::hash<T1>()(t.first) ^ std::hash<T2>()(t.second);
  }
};
 
int n;
char s[606060];
int dp[606060];
ll ha1[303030], pw1[303030];
ll ha2[303030], pw2[303030];
 
int pv = 0;
unordered_map<pair<ll, ll>, int, pair_hash> 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:56:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(lnk[v]) return; lnk[v] = 1;
     ^~
palindrome.cpp:56: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 7552 KB Output is correct
2 Correct 8 ms 7552 KB Output is correct
3 Correct 9 ms 7552 KB Output is correct
4 Correct 9 ms 7552 KB Output is correct
5 Correct 9 ms 7552 KB Output is correct
6 Correct 9 ms 7552 KB Output is correct
7 Correct 9 ms 7552 KB Output is correct
8 Correct 9 ms 7552 KB Output is correct
9 Correct 9 ms 7552 KB Output is correct
10 Correct 9 ms 7552 KB Output is correct
11 Correct 9 ms 7552 KB Output is correct
12 Correct 9 ms 7552 KB Output is correct
13 Correct 9 ms 7552 KB Output is correct
14 Correct 9 ms 7552 KB Output is correct
15 Correct 9 ms 7552 KB Output is correct
16 Correct 9 ms 7552 KB Output is correct
17 Correct 9 ms 7552 KB Output is correct
18 Correct 9 ms 7552 KB Output is correct
19 Correct 10 ms 7600 KB Output is correct
20 Correct 9 ms 7552 KB Output is correct
21 Correct 9 ms 7680 KB Output is correct
22 Correct 9 ms 7552 KB Output is correct
23 Correct 9 ms 7552 KB Output is correct
24 Correct 8 ms 7552 KB Output is correct
25 Correct 9 ms 7552 KB Output is correct
26 Correct 10 ms 7552 KB Output is correct
27 Correct 9 ms 7552 KB Output is correct
28 Correct 9 ms 7552 KB Output is correct
29 Correct 9 ms 7552 KB Output is correct
30 Correct 9 ms 7552 KB Output is correct
31 Correct 9 ms 7552 KB Output is correct
32 Correct 9 ms 7552 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9216 KB Output is correct
2 Correct 14 ms 9088 KB Output is correct
3 Correct 17 ms 9216 KB Output is correct
4 Correct 15 ms 9088 KB Output is correct
5 Correct 13 ms 9472 KB Output is correct
6 Correct 13 ms 9472 KB Output is correct
7 Correct 13 ms 9088 KB Output is correct
8 Correct 11 ms 7936 KB Output is correct
9 Correct 11 ms 7936 KB Output is correct
10 Correct 14 ms 8960 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 23816 KB Output is correct
2 Correct 72 ms 23180 KB Output is correct
3 Correct 90 ms 23812 KB Output is correct
4 Correct 84 ms 23304 KB Output is correct
5 Correct 69 ms 26252 KB Output is correct
6 Correct 52 ms 21128 KB Output is correct
7 Correct 64 ms 21640 KB Output is correct
8 Correct 32 ms 11648 KB Output is correct
9 Correct 39 ms 14456 KB Output is correct
10 Correct 53 ms 23564 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 57352 KB Output is correct
2 Correct 264 ms 54020 KB Output is correct
3 Correct 331 ms 57348 KB Output is correct
4 Correct 285 ms 54660 KB Output is correct
5 Correct 230 ms 68268 KB Output is correct
6 Correct 231 ms 51716 KB Output is correct
7 Correct 228 ms 51588 KB Output is correct
8 Correct 77 ms 20216 KB Output is correct
9 Correct 75 ms 20216 KB Output is correct
10 Correct 194 ms 59012 KB Output is correct
11 Correct 242 ms 57604 KB Output is correct
12 Correct 85 ms 23820 KB Output is correct