結果

問題 No.263 Common Palindromes Extra
ユーザー RubikunRubikun
提出日時 2022-11-25 00:40:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,960 bytes
コンパイル時間 3,178 ms
コンパイル使用メモリ 222,776 KB
実行使用メモリ 174,956 KB
最終ジャッジ日時 2024-10-01 12:41:38
合計ジャッジ時間 9,908 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
42,160 KB
testcase_01 AC 30 ms
33,280 KB
testcase_02 AC 32 ms
33,280 KB
testcase_03 AC 67 ms
41,548 KB
testcase_04 AC 220 ms
74,788 KB
testcase_05 AC 204 ms
74,328 KB
testcase_06 AC 49 ms
39,300 KB
testcase_07 AC 1,351 ms
153,012 KB
testcase_08 AC 1,477 ms
152,560 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod1=998244353,mod2=1000000007,MAX=500005,INF=1<<30;

// Manacher https://snuke.hatenablog.com/entry/2014/12/02/235837

vector<int> Manacher(string S){
    vector<int> R(si(S));
    int i = 0, j = 0;
    while (i < S.size()) {
        while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j;
        R[i] = j;
        int k = 1;
        while (i-k >= 0 && k+R[i-k] < j) R[i+k] = R[i-k], ++k;
        i += k; j -= k;
    }
    return R;
}
// 偶数長のも求めるために$を入れる必要がある

//ロリハ

struct Rollinghash{
    string S;
    int n;
    int base1;
    int base2;
    vector<ll> h1,h2,ru1,ru2;
    
    void make(string &T,int ba1,int ba2){
        S=T;
        n=S.size();
        h1.assign(n+1,0);
        h2.assign(n+1,0);
        ru1.assign(n+1,0);
        ru2.assign(n+1,0);
        base1=ba1;
        base2=ba2;
        
        ru1[0]=1;
        ru2[0]=1;
        
        for(int i=1;i<=n;i++){
            h1[i]=h1[i-1]*base1+ll(S[i-1]-'$'+1);
            h1[i]%=mod1;
            
            h2[i]=h2[i-1]*base2+ll(S[i-1]-'$'+1);
            h2[i]%=mod2;
            
            ru1[i]=ru1[i-1]*base1%mod1;
            ru2[i]=ru2[i-1]*base2%mod2;
        }
    }
    
    pair<ll,ll> ha(int l,int r){
        pair<ll,ll> res;
        res.fi=(h1[r]-h1[l]*ru1[r-l]%mod1+mod1)%mod1;
        res.se=(h2[r]-h2[l]*ru2[r-l]%mod2+mod2)%mod2;
        
        return res;
    }//開区間
};

//強連結成分分解

int V,cmp[MAX];
vector<int> G[MAX],rG[MAX],vs;//vsがトポソの逆順になってる
bool used[MAX];

int get_id(int i,bool f){
    return 2*i+f;
}

void add_edge(int from,int to){
    G[from].push_back(to);
    rG[to].push_back(from);
}

void either(int i,bool f,int j,bool g){
    add_edge(get_id(i,!f),get_id(j,g));
    add_edge(get_id(j,!g),get_id(i,f));
    //add_edge(2*i+(!f),2*j+g);
    //add_edge(2*j+(!g),2*i+f);
}

void imply(int i,bool f,int j,bool g){
    either(i,!f,j,g);
}
//iがfならばjがg

void must(int i,bool f){
    either(i,f,i,f);
}

void DFS(int v){
    used[v]=1;
    for(int i=0;i<G[v].size();i++){
        if(used[G[v][i]]==0) DFS(G[v][i]);
    }
    vs.push_back(v);
}

void rDFS(int v,int k){
    used[v]=1;
    cmp[v]=k;
    for(int i=0;i<rG[v].size();i++){
        if(used[rG[v][i]]==0) rDFS(rG[v][i],k);
    }
}

int scc(){
    memset(used,0,sizeof(used));
    vs.clear();
    for(int v=0;v<V;v++){
        if(used[v]==0) DFS(v);
    }
    
    memset(used,0,sizeof(used));
    int k=0;
    for(int i=vs.size()-1;i>=0;i--){
        if(used[vs[i]]==0) rDFS(vs[i],k++);
    }
    return k;
}

ll dp[MAX];

void init(int sz){
    V=sz;
    for(int i=0;i<V;i++){
        dp[i]=0;
        cmp[i]=0;
        G[i].clear();
        rG[i].clear();
        used[i]=false;
    }
    vs.clear();
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string S,T;cin>>S>>T;
    string SS,TT;
    SS+='$';TT+='$';
    for(char c:S){
        SS+=c;
        SS+='$';
    }
    for(char c:T){
        TT+=c;
        TT+='$';
    }
    S=SS;
    T=TT;
    
    ll ha1=103,ha2=109;
    
    map<pair<ll,ll>,ll> MA1,MA2;
    
    for(int q=0;q<2;q++){
        map<pair<ll,ll>,ll> dic;
        Rollinghash ro;
        ro.make(S,ha1,ha2);
        init(MAX);
        
        auto mana=Manacher(S);
        
        for(int i=0;i<si(S);i++){
            int s=(i-mana[i]+1);
            if(s%2==0) s++;
            pair<ll,ll> la=mp(-1,-1);
            for(int l=s;l<=i;l+=2){
                int r=i+(i-l)+1;
                auto re=ro.ha(l,r);
                if(dic.count(re)){
                    if(l==s) dp[dic[re]]++;
                    else{
                        add_edge(dic[la],dic[re]);
                    }
                    break;
                }else{
                    int sz=si(dic);
                    dic[re]=sz;
                    if(l==s) dp[sz]++;
                    else{
                        add_edge(dic[la],dic[re]);
                    }
                    la=re;
                }
            }
        }
        
        V=si(dic);
        
        scc();
        
        reverse(all(vs));
        
        for(int a:vs){
            for(int to:G[a]){
                dp[to]+=dp[a];
            }
        }
        
        for(auto a:dic){
            MA1[a.fi]+=dp[a.se];
        }
        
        swap(S,T);
        swap(MA1,MA2);
    }
    
    ll ans=0;
    
    for(auto a:MA1){
        if(MA2.count(a.fi)) ans+=a.se*MA2[a.fi];
    }
    
    cout<<ans<<endl;
}
0