Submission #234849

#	Time	Username	Problem	Language	Result	Execution time	Memory
234849		jhnah917	Palindromes (APIO14_palindrome)	C++14	100 / 100	331 ms	68268 KiB

palindrome

#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 (stderr)

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 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27