結果

問題 No.515 典型LCP
ユーザー lumc_lumc_
提出日時 2018-08-30 00:06:52
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 5,496 bytes
コンパイル時間 1,878 ms
コンパイル使用メモリ 178,136 KB
実行使用メモリ 85,912 KB
最終ジャッジ日時 2024-09-13 19:43:13
合計ジャッジ時間 21,676 ms
ジャッジサーバーID
（参考情報） 		judge5 / 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 AC 939 ms
85,232 KB
testcase_15 TLE -
testcase_16 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// #undef DEBUG
// #define DEBUG
/// {{{ DEBUG --- ///
#ifdef DEBUG
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << "{"; for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? ", " : ""); o << "}"; return o; }
#ifdef USE_COUT
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);cout<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}()
#else
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}()
#endif
template<class T> inline void dump2D(T &d, size_t sizey, size_t sizex) { ostream&o=
#ifdef USE_COUT
  cout;
#else
  cerr;
#endif
  for(size_t i = 0; i < sizey; i++) { for(size_t j = 0; j < sizex; j++) o << d[i][j] << " "; o << endl; }
}
#else
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? " " : ""); return o; }
#define dump(...) (42)
#define dump2D(...) (42)
#endif
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
template<class T, class U> ostream & operator<<(ostream &o, pair<T, U> const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; }
/// }}}--- ///


// Mamber & Mayers
// SA
// *1 : if you want original comparison rule, change here
struct SA {
  const int n;
  const string &s;
  vector< int > rnk;
  vector< int > sa;
  int operator[](int i) const { return sa[i]; }
  SA(const string &s) : n(s.size()), s(s), rnk(n), sa(n) {
    iota(begin(sa), end(sa), 0);
    sort(begin(sa), end(sa), [&](int a, int b) { return s[a] < s[b]; }); // *1
    for(int i = 0; i < n; i++) rnk[i] = s[i];                        // *1
    for(int i = 1; i < n; i <<= 1) {
      auto comp = [&](int a, int b) {
        if(rnk[a] != rnk[b]) return rnk[a] < rnk[b];
        a = a + i < n ? rnk[a + i] : -1;
        b = b + i < n ? rnk[b + i] : -1;
        return a < b;
      };
      sort(begin(sa), end(sa), comp);
      auto tmp = rnk;
      tmp[sa[0]] = 0;
      for(int j = 1; j < n; j++) tmp[sa[j]] = tmp[sa[j - 1]] + comp(sa[j - 1], sa[j]); ///
      rnk = tmp;
    }
  }
};

struct LCP {
  const int n;
  const string &s;
  vector< int > lcp;
  int operator[](int i) const { return lcp[i]; }
  LCP(const SA& sa) : n(sa.n), s(sa.s), lcp(n - 1) {
    int h = 0;
    for(int i = 0; i < n; i++) {
      if(h) h--;
      if(sa.rnk[i] == 0) continue;
      int j = sa[sa.rnk[i] - 1];
      while(i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
      lcp[sa.rnk[i] - 1] = h;
    }
  }
};

// NOTE : query in range!
/// --- Sparse Table Library {{{ ///

// struct SemiLattice {
//   using T = _underlying_set_;
//   static T op(T const &a, T const &b) { return _a_op_b_; }
// };

template<class SemiLattice>
struct SparseTable {
  using T = typename SemiLattice::T;
  std::size_t n;
  std::vector<std::size_t> log2;
  std::vector< std::vector<T> > t;
  T identity;
  SparseTable():n(0) {}
  SparseTable(std::size_t n, T identity = T()): n(n), log2(n + 1), identity(identity) {
    for(std::size_t i = 2; i <= n; i++) log2[i] = log2[i >> 1] + 1;
    t.resize(log2[n] + 1, std::vector<T>(n, identity));
  }
  template<class InputIter, class = typename std::iterator_traits<InputIter>::value_type>
    SparseTable(InputIter first, InputIter last, T identity = T())
    : SparseTable(std::distance(first, last), identity) {
      std::copy(first, last, std::begin(t[0]));
      build();
    }
  void set(size_t i, T val) { t[0][i] = val; }
  T get(size_t i) { return t[0][i]; }
  void build() {
    for(std::size_t j = 0; j < log2[n]; j++) {
      std::size_t w = 1 << j;
      for(std::size_t i = 0; i + (w << 1) <= n; i++) {
        t[j + 1][i] = SemiLattice::op(t[j][i], t[j][i + w]);
      }
    }
  }
  T query(std::size_t l, std::size_t r) {
    if(r - l < 1) return identity;
    std::size_t j = log2[r - l];
    return SemiLattice::op(t[j][l], t[j][r - (1 << j)]);
  }
};

/// }}}--- ///

// sparse table expample {{{

struct RMQSL {
  using T = int;
  static T op(T const &a, T const &b) { return a < b ? a : b; }
};

// }}}

ll n;
ll x, d;
pair< int, int > nx() {
  int i = (x / (n - 1)), j = (x % (n - 1));
  if(i > j) swap(i, j);
  else j++;
  x = (x + d) % (n * (n - 1));
  return make_pair(i, j);
}

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n;
  string s;
  vector<int> idx(n);
  vector<int> len(n);
  for(int i = 0; i < n; i++) {
    string t;
    cin >> t;
    idx[i] = s.size();
    len[i] = t.size();
    s += t;
  }
  // s += "-"; // sentinel
  SA sa(s);
  LCP lcp(sa);
  // dump(s);
  // dump(sa.rnk);
  // dump(lcp.lcp);
  SparseTable<RMQSL> ecas(begin(lcp.lcp), end(lcp.lcp), 1e9);

  int m;
  cin >> m >> x >> d;
  ll ans = 0;
  while(m--) {
    int i, j;
    tie(i, j) = nx();
    int a = min(len[i], len[j]);
    // dump(i, j, n);
    i = idx[i];
    j = idx[j];
    i = sa.rnk[i];
    j = sa.rnk[j];
    // dump(i, j, s.size());
    a = min(a, (int) ecas.query(min(i,j), max(i,j)));
    // dump(a);
    ans += a;
  }
  cout << ans << endl;
  return 0;
}
0