結果

問題 No.515 典型LCP
コンテスト
ユーザー しらっ亭
提出日時 2017-05-06 05:08:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,699 bytes
コンパイル時間 2,583 ms
コンパイル使用メモリ 194,676 KB
実行使用メモリ 566,980 KB
最終ジャッジ日時 2024-09-14 13:01:43
合計ジャッジ時間 11,659 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 TLE * 1 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define _p(...) (void)printf(__VA_ARGS__)
#define forr(x,arr) for(auto&& x:arr)
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define bit(n) (1LL<<(n))
#define sz(x) ((int)(x).size())
#define ten(n) ((int)1e##n)
#define fst first
#define snd second
using ll=long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pil=pair<int,ll>;using pli=pair<ll,int>;
using vs=vector<string>;using vvs=vector<vs>;using vvvs=vector<vvs>;
using vb=vector<bool>;using vvb=vector<vb>;using vvvb=vector<vvb>;
using vi=vector<int>;using vvi=vector<vi>;using vvvi=vector<vvi>;
using vl=vector<ll>;using vvl=vector<vl>;using vvvl=vector<vvl>;
using vd=vector<double>;using vvd=vector<vd>;using vvvd=vector<vvd>;
using vpii=vector<pii>;using vvpii=vector<vpii>;using vvvpii=vector<vvpii>;
template<class T> bool amax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool amin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
ll ri(){ll l;cin>>l;return l;} string rs(){string s;cin>>s;return s;}
template<class T>T read(){T t;cin>>t;return t;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<<'('<<p.fst<<", "<<p.snd<<')';}
ostream&operator<<(ostream&o,const vb&t){forr(e,t)o<<"#."[e];return o;}
template<class T>ostream&operator<<(ostream&o,const vector<T>&t){o<<"{";forr(e,t)o<<e<<",";o<<"}"<<endl;return o;}
#ifdef LOCAL
vs s_p_l_i_t(const string&s,char c){vs v;stringstream ss(s);string x;while(getline(ss,x,c))v.emplace_back(x);return move(v);}
void e_r_r(vs::iterator it){cerr<<endl;}
template<class T,class... Args>void e_r_r(vs::iterator it,T a,Args... args){cerr<<it->substr((*it)[0]==' ',it->length())<<" = "<<a<<", ";e_r_r(++it,args...);}
#define out(args...){vs a_r_g_s=s_p_l_i_t(#args,',');e_r_r(a_r_g_s.begin(),args);}
#else
#define out(args...)
#endif

struct Trie {
  const int EMPTY = -1;
  vector<vector<int>> trie;
  vector<vector<int>> E;

  Trie() {
    assign_new_state();
  }

  int add_word(const string& word) {
    int now = 0;
    for (char c : word) {
      c -= 'a';
      if (trie[now][c] == EMPTY) {
        trie[now][c] = trie.size();
        assign_new_state();
        E[now].emplace_back(trie[now][c]);
      }
      now = trie[now][c];
    }
    return now;
  }

  private:
  void assign_new_state() {
    trie.emplace_back(26, EMPTY);
    E.emplace_back();
  };
};

template <class T> struct SparseTable {
  vector<vector<T>> table;

  SparseTable() {}
  SparseTable(const vector<T> &A) {
    init(A);
  }

  void init(const vector<T> &A) {
    int n = (int) A.size();
    int height = 32 - __builtin_clz(n - 1);
    int width = 1 << height;
    table.resize(height, vector<T>(width));
    for (int i = 0; i < width; i++) table[0][i] = A[i];
    for (int i = 1; i < height; i++) for (int j = 0; j < width; j++) {
      const int b = ((j >> i) | 1) << i;
      table[i][j] = (j >> i) & 1 ? query(b, j) : query(j, b-1);
    }
  }

  // [l, r]
  T query(int l, int r) {
    if (l == r) return table[0][l];
    const int d = 31 - __builtin_clz(l ^ r);
    return min(table[d][l], table[d][r]);
  }
};

// complexity depends on RMQ
template <class RMQ> struct LCA {
  static const int inf = 1e9+7;
  size_t n;
  vector<int> D, P, L, R;
  vector<pair<int, int>> ET;
  vector<long long> WD;
  vector<vector<int>> W;
  bool weighted;
  RMQ rmq;

  LCA(const vector<vector<int>> &G) : n(G.size()), D(n), P(n), L(n), R(n), WD(n), W(n), weighted(0) {
    dfs(G);
    rmq.init(ET);
  }

  LCA(const vector<vector<pair<int, int>>> &G) : n(G.size()), D(n), P(n), L(n), R(n), WD(n), W(n), weighted(1) {
    vector<vector<int>> H(n);
    for (int i = 0; i < n; i++) for (pii x : G[i]) {
      H[i].emplace_back(x.first);
      W[i].emplace_back(x.second);
    }
    dfs(H);
    rmq.init(ET);
  }

  void dfs(const vector<vector<int>> &G, int root = 0) {
    vector<int> count(n);
    stack<int> S; S.push(root);
    while (!S.empty()) {
      int v = S.top(); S.pop();
      if (count[v] == 1) {
        count[v] = 2;
        R[v] = ET.size() - 1;
        if (P[v] >= 0) ET.emplace_back(D[P[v]], P[v]);
      }
      else if (count[v] == 0) {
        S.push(v);
        count[v] = 1;
        L[v] = ET.size();
        ET.emplace_back(D[v], v);
        for (int i = 0; i < (int)G[v].size(); i++) if (!count[G[v][i]]) {
          D[G[v][i]] = D[v] + 1;
          WD[G[v][i]] = WD[v] + (weighted ? W[v][i] : 1);
          P[G[v][i]] = v;
          S.push(G[v][i]);
        }
      }
    }
  }

  int query(int u, int v) {
    u = L[u]; v = L[v];
    if (u > v) swap(u, v);
    return rmq.query(u, v).second;
  }

  long long dist(int u, int v) {
    return WD[u] + WD[v] - 2 * WD[query(u, v)];
  }
};

void Main() {
  ll n = ri();

  Trie trie;

  vi V(n);
  vi L(n);

  rep(i, n) {
    string s = rs();
    V[i] = trie.add_word(s);
    L[i] = sz(s);
  }

  LCA<SparseTable<pii>> lca(trie.E);

  ll m = ri();
  ll x = ri();
  ll d = ri();

  ll ans = 0;

  rep(k, 1, m+1) {
    ll i = (x / (n - 1));
    ll j = (x % (n - 1));
    if (i > j) swap(i, j);
    else j++;
    x = (x + d) % (n * (n - 1));

    int u = V[i];
    int v = V[j];
    int d = lca.dist(u, v);
    int a = (L[i] + L[j] - d) / 2;
    ans += a;
  }
  cout << ans << endl;
}
int main() { cin.tie(nullptr); ios::sync_with_stdio(false); Main(); return 0; }
0