結果

問題 No.515 典型LCP
ユーザー miyo2580miyo2580
提出日時 2023-10-31 22:24:58
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,359 bytes
コンパイル時間 2,205 ms
コンパイル使用メモリ 186,720 KB
実行使用メモリ 143,640 KB
最終ジャッジ日時 2024-09-25 17:44:13
合計ジャッジ時間 7,261 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
using Graph = vector<vec>;
const long long INF = 1LL<<60;
const long long MOD = 1000000007;

/* LCA(G, root): 木 G に対する根を root として Lowest Common Ancestor を求める構造体
    query(u,v): u と v の LCA を求める。計算量 O(logn)
    前処理: O(nlogn)時間, O(nlogn)空間
*/
struct LCA {
    vector<vector<int>> parent;  // parent[k][u]:= u の 2^k 先の親
    vector<int> dist;            // root からの距離
    LCA(const Graph& G, int root) { init(G, root); }

    // 初期化
    void init(const Graph& G, int root) {
        int V = G.size();
        int K = 1;
        while ((1 << K) < V) K++; //KはK>=log2(V)を満たす最小の整数
        parent.assign(K, vector<int>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (int k = 0; k + 1 < K; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                }
                else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    // 根からの距離と1つ先の頂点を求める
    void dfs(const Graph& G, int v, int p, int d) {
        parent[0][v] = p;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e!= p) dfs(G, e, v, d + 1);
        }
    }

    int query(int u, int v) {
        if (dist[u] < dist[v]) swap(u, v);  // u の方が深いとする
        int K = parent.size();
        // LCA までの距離を同じにする
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        // 二分探索で LCA を求める
        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
};

using F=array<int,26>;

int main()
{  
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;cin>>n;
    vector<F> to(1);
    Graph g(1);
    vec memo(n);
    vec cnt(1);
    rep(i,n){
        string s;cin>>s;
        ll v=0;
        ll d=0;
        for(char c:s){
            ll x=c-'a';
            if(to[v][x]==0){
                g.push_back(vec());
                cnt.push_back(0);
                to[v][x]=to.size();
                g[v].push_back(to[v][x]);
                g[to[v][x]].push_back(v);
                to.push_back(F());   
            }
            v=to[v][x];
            cnt[v]=++d;

        }
        memo[i]=v;
    }
    ll m,x,d;
    cin>>m>>x>>d;
    LCA lc(g,0);
    ll ans=0;
    rep(i,m){
        ll I=(x/(n-1))+1;
        ll J=(x%(n-1))+1;
        if(I>J)swap(I,J);
        else J++;
        I--;J--;
        ans+=cnt[lc.query(memo[I],memo[J])];
        x=(x+d)%(n*(n-1));
    }
    cout<<ans<<endl;
    return 0;
}
0