結果

問題 No.515 典型LCP
ユーザー SPARKLE_mathSPARKLE_math
提出日時 2022-05-03 14:22:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,583 bytes
コンパイル時間 1,047 ms
コンパイル使用メモリ 91,128 KB
実行使用メモリ 100,220 KB
最終ジャッジ日時 2023-09-15 09:40:26
合計ジャッジ時間 6,404 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 AC 739 ms
100,220 KB
testcase_02 AC 527 ms
99,700 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 AC 506 ms
99,496 KB
testcase_10 AC 515 ms
99,476 KB
testcase_11 AC 502 ms
99,704 KB
testcase_12 AC 499 ms
99,608 KB
testcase_13 AC 502 ms
99,692 KB
testcase_14 AC 402 ms
99,468 KB
testcase_15 TLE -
testcase_16 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "main.cpp"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#line 4 "/home/kokoro601/compro_library/String/SuffixArray.hpp"
#include <numeric>
#line 6 "/home/kokoro601/compro_library/String/SuffixArray.hpp"
#include <assert.h>
#line 3 "/home/kokoro601/compro_library/DataStructure/SparseTable.hpp"

template <class T> class SparseTable {
public:
    std::vector<std::vector<T> > tab;
    std::vector<int> lookup;


    void build(const std::vector<T> &v) {
        int b = 0;
        int n = v.size();
        while (1 << b <= n) b++;
        tab.assign(b, std::vector<T>(1 << b));

        for (int i = 0; i < n; i++) tab[0][i] = v[i];
        
        for (int i = 1; i < b; i++) {
            int pre_len = 1 << (i - 1);
            int ub = n - (1 << i);
            for (int j = 0; j <= ub; j++) {
                tab[i][j] = std::min(tab[i - 1][j], tab[i - 1][j + pre_len]);
            }
        }

        lookup.resize(v.size() + 1);
        for (int i = 2; i < lookup.size(); i++)
            lookup[i] = lookup[i >> 1] + 1;
    }

    // [l, r)
    inline T rmq(int l, int r) {
        // assert(l < r);
        int b = lookup[r - l];
        return std::min(tab[b][l], tab[b][r - (1 << b)]);
    }
};
#line 8 "/home/kokoro601/compro_library/String/SuffixArray.hpp"

// this implemantation is based on
// https://megalodon.jp/2022-0430-1612-24/https://wk1080id.hatenablog.com:443/entry/2018/12/25/005926
// the construction of suffix array is O(nlogn), where n is the length of the string

class SuffixArray
{

    std::vector<int> sort_cyclic_shifts(const std::string &s)
    {
        int n = s.size();

        std::vector<int> cn(n), pn(n), p(n), c(n), cnt(n);
        std::iota(p.begin(), p.end(), 0);
        std::sort(p.begin(), p.end(), [&](int a, int b)
                  { return s[a] == s[b] ? a < b : s[a] < s[b]; });
        c[p[0]] = 0;
        for (int i = 1; i < n; i++) c[p[i]] = (s[p[i]] == s[p[i - 1]]) ? c[p[i - 1]] : i;

        for (int len = 1; len < n; len <<= 1)
        {
            for (int i = 0; i < n; i++) {
                pn[i] = p[i] - len;
                if (pn[i] < 0) pn[i] += n;
            }

            std::iota(cnt.begin(), cnt.end(), 0);
            for (int i = 0; i < n; i++) p[cnt[c[pn[i]]]++] = pn[i];

            if (2 * len >= n) break;

            c[p[0]] = 0;
            for (int i = 1; i < n; i++)
            {
                if (c[p[i]] == c[p[i - 1]] && c[(p[i] + len) % n] == c[(p[i - 1] + len) % n])
                    cn[p[i]] = cn[p[i - 1]];
                else
                    cn[p[i]] = i;
            }
            std::swap(c, cn);
        }
        return p;
    }

    void calc_lcp(std::string &s) {
        int n = sa.size();
        int slen = n - 1;

        rank.resize(n);
        lcp.resize(n);
        for (int i = 0; i < n; i++) rank[sa[i]] = i; 

        int h = 0;
        lcp[0] = 0;
        for (int i = 0; i < slen; 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.build(lcp);
    }
    

public:
    std::vector<int> sa, lcp, rank;
    SparseTable<int> st;
    bool need_lcp;

    SuffixArray(std::string &s, bool need_lcp = true): 
        need_lcp(need_lcp)
    {
        s.push_back('$');
        sa = sort_cyclic_shifts(s);
        s.pop_back();

        if (need_lcp) calc_lcp(s);
    }

    int get_lcp(int i, int j) {
        assert(need_lcp && i != j);
        int rank_i = rank[i];
        int rank_j = rank[j];
        if (rank_i > rank_j) std::swap(rank_i, rank_j);
        return st.rmq(rank_i, rank_j);
    } 
    
};
#line 7 "main.cpp"

using namespace std;
using ll = long long;
using Graph = vector<vector<int> >;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n; cin >> n;
    vector<int> l(n), offset(n + 1);
    string s = "";

    for (int i = 0; i < n; i++) {
        string si; cin >> si;
        l[i] = si.size();
        offset[i + 1] = offset[i] + l[i];
        s += si;
    }

    SuffixArray sa(s);

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

        ans += min(min(l[i - 1], l[j - 1]), sa.get_lcp(offset[i - 1], offset[j - 1]));

        x = (x + d) % (n * (n - 1));
    }
    cout << ans << endl;

    return 0;
}
0