結果

問題 No.515 典型LCP
ユーザー finefine
提出日時 2019-10-30 02:33:53
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 5,150 bytes
コンパイル時間 2,507 ms
コンパイル使用メモリ 186,324 KB
実行使用メモリ 97,616 KB
最終ジャッジ日時 2024-09-14 21:42:05
合計ジャッジ時間 7,174 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 TLE -
testcase_02 TLE -
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct SuffixArray {
    string str;
    vector<int> sa;

    SuffixArray() {}
    SuffixArray(const string& s) : str(s) {
        constructSA();
    }

    // O(N (log N)^2)
    void constructSA() {
        if (str.empty()) return;

        int n = str.size();

        sa.resize(n + 1);
        vector<int> rank(n + 1);
        for (int i = 0; i <= n; i++) {
            sa[i] = i;
            rank[i] = (i < n ? str[i] : -1);
        }

        int len;
        auto compare_sa = [&](const int i, const int j) {
            if (rank[i] != rank[j]) return rank[i] < rank[j];
            else {
                int ri = (i + len <= n ? rank[i + len] : -1);
                int rj = (j + len <= n ? rank[j + len] : -1);
                return ri < rj;
            }
        };

        vector<int> tmp(n + 1);
        for (len = 1; len <= n; len <<= 1) {
            sort(sa.begin(), sa.end(), compare_sa);

            tmp[sa[0]] = 0;
            for (int i = 1; i <= n; i++) {
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
            }
            for (int i = 0; i <= n; i++) {
                rank[i] = tmp[i];
            }
        }
    }

    int operator[](int idx) const {
        return sa[idx];
    }

    // 文字列s以上となる最小の接尾辞について、SAのindexを返す（無いならsa.size()を返す）
    int lower_bound(const string& s) {
        int ng = -1, ok = sa.size();
        while (ok - ng > 1) {
            int mid = (ok + ng) >> 1;
            (str.compare(sa[mid], s.size(), s) < 0 ? ng : ok) = mid;
        }
        return ok;
    }

    // 文字列sが文字列strに含まれるならSAのindexを、無いなら-1を返す
    int find(const string& s) {
        int idx = lower_bound(s);
        return ((idx < sa.size() && str.compare(sa[idx], s.size(), s) == 0) ? idx : -1);
    }

    // 文字列sが文字列strに含まれるか？
    bool contain(const string& s) {
        return find(s) != -1;
    }
};

template <class SemiLattice>
struct SparseTable {
    using T = typename SemiLattice::T;

    int n;
    vector< vector<T> > table;
    vector<int> log_table;

    SparseTable() {}
    SparseTable(const vector<T>& v) {
        n = v.size();

        log_table.resize(n + 1, 0);
        for (int i = 2; i <= n; i++) {
            log_table[i] = log_table[i >> 1] + 1;
        }

        table.resize(log_table[n] + 1, vector<T>(n));
        for (int i = 0; i < n; i++) {
            table[0][i] = v[i];
        }

        size_t sz = table.size();
        for (int i = 1; i < sz; i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                table[i][j] = SemiLattice::merge(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    //区間[l, r)に対するクエリに答える
    T query(int l, int r) {
        assert(l < r);
        int k = log_table[r - l];
        return SemiLattice::merge(table[k][l], table[k][r - (1 << k)]);
    }
};

//以下、SemiLatticeの例
template <class U = ll>
struct RMQSL {
    using T = U;
    static T merge(T a, T b) { return min(a, b); }
};

struct LongestCommonPrefixArray {
    vector<int> lcp;
    const SuffixArray& sa;
    SparseTable< RMQSL<int> > st;

    LongestCommonPrefixArray() : sa(SuffixArray()) {}
    LongestCommonPrefixArray(const SuffixArray& sa) : sa(sa) {
        const string& s = sa.str;
        int n = s.size();

        vector<int> rank(n + 1);
        for (int i = 0; i <= n; i++) rank[sa[i]] = i;

        lcp.resize(n + 1);
        lcp[0] = 0;
        for (int i = 0, h = 0; i < n; i++) {
            int j = sa[rank[i] - 1];

            if (h > 0) h--;
            for (; j + h < n && i + h < n; h++) {
                if (s[j + h] != s[i + h]) break;
            }

            lcp[rank[i] - 1] = h;
        }

        st = SparseTable< RMQSL<int> >(lcp);
    }

    int operator[](int idx) const {
        return lcp[idx];
    }

    int getLCP(int i, int j) {
        //i = sa[i], j = sa[j];
        if (i > j) swap(i, j);
        return st.query(i, j);
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    string all_s = "";
    vector<int> ids(n), len(n);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        ids[i] = all_s.size();
        len[i] = s.size();
        all_s += s;
    }

    SuffixArray sa(all_s);
    LongestCommonPrefixArray lcp(sa);

    vector<int> rev_sa(all_s.size() + 1, -1);
    cerr << all_s << "\n";
    for (int i = 0; i <= all_s.size(); i++) {
        rev_sa[sa[i]] = i;
    }

    int m;
    ll x, d;
    cin >> m >> x >> d;
    ll ans = 0;
    for (int k = 1; k <= m; k++) {
        ll i = (x / (n - 1)) + 1;
        ll j = (x % (n - 1)) + 1;
        if (i > j) swap(i, j);
        else j++;

        int min_len = min(len[i - 1], len[j - 1]);
        i = rev_sa[ids[i - 1]];
        j = rev_sa[ids[j - 1]];

        ans += min(min_len, lcp.getLCP(i, j));

        x = (x + d) % ((ll)n * (n - 1));
    }
    cout << ans << "\n";
    return 0;
}
0