Submission #1018222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018222		jk410	Palindromes (APIO14_palindrome)	C++17	100 / 100	540 ms	63384 KiB

palindrome

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#define all(v) v.begin(),v.end()
#define compress(v) v.erase(unique(all(v)),v.end())
#define lbx(v,x) lower_bound(all(v),x)-v.begin()
#define ubx(v,x) upper_bound(all(v),x)-v.begin()
#define maxx(a,b) a=max(a,b)
#define minn(a,b) a=min(a,b)
#define for0(i,n) for (int i=0; i<n; i++)
#define for1(i,n) for (int i=1; i<=n; i++)
#define forr(i,l,r) for (int i=l; i<=r; i++)
#define sz(v) (int)v.size()
using namespace std;
typedef long long ll;
const ll B1=601;
const ll B2=997;
const ll P1=1104110479;
const ll P2=998244353;
const int MAX=300000;
ll PowB1[MAX+1],PowB2[MAX+1];
int N;
string S,A;
int P[MAX*2];
ll H1[MAX],H2[MAX];
map<pair<ll,ll>,int> Map;
int CntHash;
vector<int> Adj[MAX+1];
bool Visited[MAX+1];
int Cnt[MAX+1],L[MAX+1];
pair<ll,ll> getHash(int l,int r){
    ll h1=(H1[r]-(l?H1[l-1]:0)*PowB1[r-l+1]%P1+P1)%P1;
    ll h2=(H2[r]-(l?H2[l-1]:0)*PowB2[r-l+1]%P2+P2)%P2;
    return {h1,h2};
}
int getIdx(pair<ll,ll> h,int l,int r){
    if (Map.find(h)!=Map.end())
        return Map[h];
    Map[h]=++CntHash;
    L[CntHash]=r-l+1;
    return CntHash;
}
void solve(int l,int r){
    pair<ll,ll> h=getHash(l,r);
    int hi=getIdx(h,l,r);
    if (Visited[hi]||l+1>r-1)
        return;
    Visited[hi]=true;
    pair<ll,ll> p=getHash(l+1,r-1);
    int pi=getIdx(p,l+1,r-1);
    Adj[pi].push_back(hi);
    solve(l+1,r-1);
}
int dfs(int v){
    if (Visited[v])
        return Cnt[v];
    Visited[v]=true;
    for (int i:Adj[v])
        Cnt[v]+=dfs(i);
    return Cnt[v];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    PowB1[0]=PowB2[0]=1;
    for1(i,MAX){
        PowB1[i]=PowB1[i-1]*B1%P1;
        PowB2[i]=PowB2[i-1]*B2%P2;
    }
    cin>>S;
    N=sz(S);
    for0(i,N){
        H1[i]=((i?H1[i-1]:0)*B1%P1+(S[i]-'a'+1))%P1;
        H2[i]=((i?H2[i-1]:0)*B2%P2+(S[i]-'a'+1))%P2;
    }
    A.push_back(S[0]);
    for1(i,N-1){
        A.push_back('.');
        A.push_back(S[i]);
    }
    for (int i=0,r=-1,k=-1; i<2*N-1; i++){
        if (i<=r)
            P[i]=min(P[2*k-i],r-i);
        while (i-P[i]-1>=0&&i+P[i]+1<2*N-1&&A[i-P[i]-1]==A[i+P[i]+1])
            P[i]++;
        if (r<i+P[i]){
            r=i+P[i];
            k=i;
        }
        int len,li,ri;
        if (i&1){
            len=(P[i]+1)/2;
            li=i/2-len+1;
            ri=i/2+len;
        }
        else{
            len=P[i]/2;
            li=i/2-len;
            ri=i/2+len;
        }
        if (li>ri)
            continue;
        pair<ll,ll> h=getHash(li,ri);
        Cnt[getIdx(h,li,ri)]++;
        solve(li,ri);
    }
    fill(Visited+1,Visited+CntHash+1,false);
    ll ans=0;
    for1(i,CntHash)
        maxx(ans,(ll)L[i]*dfs(i));
    cout<<ans;
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27