結果

問題 No.263 Common Palindromes Extra
ユーザー uwiuwi
提出日時 2015-03-31 04:44:23
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,167 ms / 2,000 ms
コード長 3,496 bytes
コンパイル時間 1,052 ms
コンパイル使用メモリ 70,328 KB
実行使用メモリ 136,124 KB
最終ジャッジ日時 2024-05-07 07:56:49
合計ジャッジ時間 6,698 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
72,104 KB
testcase_01 AC 31 ms
68,036 KB
testcase_02 AC 33 ms
68,164 KB
testcase_03 AC 90 ms
78,536 KB
testcase_04 AC 472 ms
118,584 KB
testcase_05 AC 422 ms
121,528 KB
testcase_06 AC 56 ms
72,620 KB
testcase_07 AC 1,160 ms
132,540 KB
testcase_08 AC 1,167 ms
134,504 KB
testcase_09 AC 437 ms
136,124 KB
testcase_10 AC 420 ms
134,268 KB
testcase_11 AC 382 ms
130,688 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef long long ll;
const int Maxl=1000005;
int fa[Maxl],ran2[Maxl],a[Maxl],b[Maxl];
int sa[Maxl],lcp[Maxl],ran[Maxl],rad[Maxl<<1],tmp[Maxl];
int n,k;
string S="",s1,s2;
ll res,cur;
 
void init(){for(int i=0;i<Maxl;++i)ran2[i]=a[i]=b[i]=0,fa[i]=i;}
int Find(const int &x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
void unite(int x,int y){
    x=Find(x);y=Find(y);if(x==y)return;
    if(ran2[x]<ran2[y])swap(x,y);fa[y]=x;
    cur+=1LL*a[x]*b[y]+1LL*a[y]*b[x];
    a[x]+=a[y];b[x]+=b[y];
    if(ran2[x]==ran2[y])ran2[x]++;
}
bool same(const int &x,const int &y){return Find(x)==Find(y);}
void add_a(int x){cur+=b[x=Find(x)];a[x]++;}
void add_b(int x){cur+=a[x=Find(x)];b[x]++;}
void manacher(){
    string s(n<<1|1,'#');
    for(int i=0;i<n;++i)s[i<<1|1]=S[i];
    for(int i=0,j=0,k=1;i<(n<<1|1);k=1){
        while(i>=j&&i+j<(n<<1|1)&&s[i-j]==s[i+j])++j;
        rad[i]=j;
        while(i>=k&&rad[i-k]<rad[i]-k)rad[i+k]=rad[i-k],++k;
        i+=k;j=max(j-k,0);
    }
}
int num[Maxl],wa[Maxl],wb[Maxl],wv[Maxl],wd[Maxl];
bool cmp(int *r,const int &a,const int &b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(string r,const int &n,int m){
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i<m;i++)wd[i]=0;
    for(i=0;i<n;i++)wd[x[i]=r[i]] ++;
    for(i=1;i<m;i++)wd[i]+= wd[i-1];
    for(i=n-1;i>=0;i--)sa[-- wd[x[i]]]=i;
    for(j=1,p=1;p<n;j*=2,m=p){
        for(p=0,i=n-j;i<n;i++)y[p ++]=i;
        for(i=0;i<n;i++)if(sa[i]>=j)y[p ++] = sa[i] - j;
        for(i=0;i<n;i++)wv[i]=x[y[i]];
        for(i=0;i<m;i++)wd[i]=0;
        for(i=0;i<n;i++)wd[wv[i]]++;
        for(i=1;i<m;i++)wd[i]+=wd[i-1];
        for(i=n-1;i>=0;i--)sa[--wd[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    for(int i=0;i<n;++i)ran[sa[i]]=i;
}
 
void Init_LCP(){
    lcp[sa[0]]=0;
    for(int i=0,h=0,j;i<n;++i){
        j=sa[ran[i]-1];if(h)h--;
        while(i+h<n&&j+h<n&&S[i+h]==S[j+h])++h;
        lcp[ran[i]-1]=h;
    }
}
vector<int>query[Maxl];
vector<int>in[Maxl];
 
void Init(){
    cin>>s1>>s2;
    S=s1+"$"+s2;
    n=S.size();
    da(S,n,128);Init_LCP();
    manacher();
}
 
void Work(){
    Init();
    //odd
    cur=0;init();
    for(int i=0;i<n;i++)query[lcp[i]].push_back(i);
    for(int i=0;i<n;i++){int f=rad[i<<1|1]-1;in[f].push_back(i);}
    int m=n;if(!(m&1))m--;
    for(int i=n;i>(m+1)/2;--i)
        for(int j=0;j<query[i].size();++j)
            unite(sa[query[i][j]],sa[query[i][j]+1]);
    for(int i=m;i>=1;i-=2){
        for(int j=0;j<in[i].size();++j)
            if(in[i][j]<s1.size())add_a(in[i][j]);
            else if(in[i][j]>s1.size())add_b(in[i][j]);
        for(int j=0;j<query[(i+1)/2].size();++j)
            unite(sa[query[(i+1)/2][j]],sa[query[(i+1)/2][j]+1]);
        res+=cur;
    }
 
    //even
    cur=0;init();
    for(int i=0;i<Maxl;i++)in[i].clear();
    for(int i=0;i<=2*n;i+=2){int f=rad[i]-1;in[f].push_back(i/2);}
    m=n;if(m&1)m--;
    for(int i=n;i>m/2;i--)
        for(int j=0;j<query[i].size();j++)
            unite(sa[query[i][j]],sa[query[i][j]+1]);
    for(int i=m;i>=2;i-=2){
        for(int j=0;j<in[i].size();j++)
            if(in[i][j]<s1.size())add_a(in[i][j]);
            else if(in[i][j]>s1.size())add_b(in[i][j]);
        for(int j=0;j<query[i/2].size();j++)
            unite(sa[query[i/2][j]],sa[query[i/2][j]+1]);
        res+=cur;
    }
    cout<<res<<endl;
}
int main(){Work();return 0;}
0