結果

問題 No.2172 SEARCH in the Text Editor
ユーザー 👑 NachiaNachia
提出日時 2022-12-24 02:02:07
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,342 bytes
コンパイル時間 1,996 ms
コンパイル使用メモリ 108,124 KB
実行使用メモリ 12,416 KB
最終ジャッジ日時 2024-04-29 06:08:27
合計ジャッジ時間 7,894 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 78 ms
5,632 KB
testcase_04 AC 164 ms
12,416 KB
testcase_05 AC 149 ms
11,008 KB
testcase_06 AC 30 ms
5,376 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 104 ms
9,472 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 28 ms
5,376 KB
testcase_16 AC 35 ms
5,376 KB
testcase_17 WA -
testcase_18 AC 48 ms
5,376 KB
testcase_19 AC 47 ms
5,376 KB
testcase_20 AC 27 ms
5,376 KB
testcase_21 AC 136 ms
11,008 KB
testcase_22 AC 73 ms
5,376 KB
testcase_23 AC 73 ms
5,376 KB
testcase_24 AC 74 ms
5,376 KB
testcase_25 AC 73 ms
5,376 KB
testcase_26 AC 157 ms
10,496 KB
testcase_27 AC 153 ms
10,240 KB
testcase_28 AC 55 ms
5,376 KB
testcase_29 AC 53 ms
5,376 KB
testcase_30 AC 51 ms
5,376 KB
testcase_31 WA -
testcase_32 AC 134 ms
10,368 KB
testcase_33 AC 137 ms
10,112 KB
testcase_34 AC 73 ms
5,376 KB
testcase_35 AC 75 ms
5,376 KB
testcase_36 AC 73 ms
5,376 KB
testcase_37 AC 73 ms
5,376 KB
testcase_38 AC 163 ms
11,776 KB
testcase_39 AC 162 ms
11,520 KB
testcase_40 AC 56 ms
5,376 KB
testcase_41 AC 55 ms
5,376 KB
testcase_42 AC 54 ms
5,376 KB
testcase_43 AC 54 ms
5,376 KB
testcase_44 AC 145 ms
11,264 KB
testcase_45 AC 145 ms
11,264 KB
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <atcoder/string>
#include <atcoder/modint>
using namespace std;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
using Modint = atcoder::static_modint<998244353>;

const int SZ = 50;
const int SZZ = SZ * (SZ+1) / 2;

int Z(const string& preof, const string& sufof){
    int x = min(preof.size(), sufof.size());
    auto z = atcoder::z_algorithm(preof.substr(0, x) + sufof.substr(sufof.size() - x));
    for(int i=x; i>=1; i--) if(z[z.size()-i] >= i) return i;
    return 0;
}

string T;
int t;
int T6L[SZ+1]={}, T6R[SZ+1]={};
int T5[SZ+1][SZ+1]={};
string TPRE[SZ+1];
string TSUF[SZ+1];
vector<string> substrs;
int T4[SZZ][SZZ]={};
int T3L[SZZ]={}, T3R[SZZ]={};
int T2L[SZZ][SZ]={}, T2R[SZZ][SZ]={};
int T1[SZ][SZ]={};
void precalc(){
    t = T.size();
    rep(i,t+1) TPRE[i] = T.substr(0, i);
    rep(i,t+1) TSUF[i] = T.substr(t-i);
    rep(i,t+1) T6L[i] = i ? Z(TSUF[i].substr(0,i-1), T) : 0;
    rep(i,t+1) T6R[i] = i ? Z(T, TPRE[i].substr(1)) : 0;
    auto sa = atcoder::suffix_array(T);
    auto lcp = atcoder::lcp_array(T, sa);
    rep(i,t+1) rep(j,t+1) T5[i][j] = -1;
    rep(i,t){
        int k = i ? lcp[i-1] : 0;
        for(int j=1; j<=t-sa[i] && j<t; j++){
            if(j <= k){ T5[sa[i]][j] = T5[sa[i-1]][j]; continue; }
            T5[sa[i]][j] = substrs.size();
            substrs.push_back(T.substr(sa[i],j));
        }
    }
    int nn = substrs.size();
    rep(i,nn) rep(j,nn) T4[i][j] = -1;
    rep(k,t+1) rep(j,k) rep(i,j) T4[T5[i][j-i]][T5[j][k-j]] = T5[i][k-i];
    rep(j,nn) T3L[j] = Z(substrs[j], T);
    rep(j,nn) T3R[j] = Z(T, substrs[j]);
    rep(j,nn) rep(x,t) T2L[j][x] = Z(substrs[j] + TSUF[x], TSUF[t-1]);
    rep(j,nn) rep(x,t) T2R[j][x] = Z(TPRE[t-1], TPRE[x] + substrs[j]);
    for(int i=1; i<t; i++) T1[i][t-i] = 1;
    for(int d=t+1; d<2*t; d++) for(int i=d-t+1; i<t; i++) T1[i][d-i] = T1[T6R[i]][d-i] + T1[i][T6L[d-i]] - T1[T6R[i]][T6L[d-i]];
}

struct Node{ int l; int r; Modint c; };
Node createNode(const string& s){
    if(s.size() < T.size()){
        auto x = lower_bound(substrs.begin(), substrs.end(), s);
        if(x != substrs.end() && *x == s) return Node{ (int)(x-substrs.begin()), -1, Modint() };
        return Node{ Z(s,TSUF[t-1]), Z(TPRE[t-1],s), Modint() };
    }
    int cnt = 0;
    auto z = atcoder::z_algorithm(T + s);
    rep(i,s.size()) if(z[t+i]>=t) cnt++;
    return Node{ Z(s,TSUF[t-1]), Z(TPRE[t-1],s), Modint::raw(cnt) };
}
Node mergeNode(Node l, Node r){
    if(l.r >= 0){
        if(r.r >= 0) return { l.l, r.r, l.c + r.c + Modint::raw(T1[l.r][r.l]) };
        return { l.l, T2R[r.l][l.r], l.c + Modint::raw(T1[l.r][T3L[r.l]]) };
    }
    if(r.r < 0){
        int nx = T4[l.l][r.l];
        if(nx >= 0) return { nx, -1, Modint() };
        int lr = T3R[l.r], rl = T3L[r.l];
        return { T2L[l.l][rl], T2R[r.l][lr], Modint::raw(T1[lr][rl]) };
    }
    return { T2L[l.l][r.l], r.r, r.c + Modint::raw(T1[T3R[l.l]][r.l]) };
}

int main() {
    int N; cin >> N;
    cin >> T;
    precalc();
    vector<Node> X(N);
    rep(i,N){
        string s; cin >> s;
        if(s == "~"){
            int j,k; cin >> j >> k;
            X[i] = mergeNode(X[j-1], X[k-1]);
        }
        else{
            X[i] = createNode(s);
        }
    }
    cout << X[N-1].c.val() << '\n';
    return 0;
}
0