結果

問題 No.515 典型LCP
ユーザー parukiparuki
提出日時 2017-05-05 23:39:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,973 bytes
コンパイル時間 2,219 ms
コンパイル使用メモリ 183,440 KB
実行使用メモリ 198,956 KB
最終ジャッジ日時 2023-10-12 10:27:08
合計ジャッジ時間 6,716 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

class LCA {
public:
    LCA() { }
    LCA(const vector<vector<int>> &G, int root = 0) :V((int)G.size()), depth(V), parent(V) {
        rep(i, LG)ancestor[i] = vector<int>(V);
        // dfs(root, 0, 0, G);
        dfs_stk(root, G);
        rep(i, V)
            ancestor[0][i] = parent[i];
        rep(i, LG - 1)rep(v, V)
            ancestor[i + 1][v] = ancestor[i][ancestor[i][v]];
    }
    int get(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int dist = depth[u] - depth[v];
        for (int i = 0; i < LG; ++i)
            if ((dist >> i) & 1)
                u = ancestor[i][u];
        if (u == v) return u;
        for (int i = LG - 1; i >= 0; --i) {
            if (ancestor[i][u] != ancestor[i][v]) {
                u = ancestor[i][u];
                v = ancestor[i][v];
            }
        }
        return ancestor[0][u];
    }
    int getDepth(int u) {
        return depth[u];
    }
    int goUp(int u, int len) {
        for (int i = 0; i < LG; ++i)
            if (len >> i & 1)u = ancestor[i][u];
        return u;
    }
    int distance(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[get(u, v)];
    }
    int getParent(int u) {
        return parent[u];
    }
private:
    static const int LG = 18;
    int V;
    vector<int> depth, parent, ancestor[LG];
    void dfs(int v, int p, int d, const vector<vector<int>> &G) {
        depth[v] = d;
        parent[v] = p;
        for (int to : G[v]) {
            if (to != p) {
                dfs(to, v, d + 1, G);
            }
        }
    }

    void dfs_stk(int root, const vector<vector<int> > & G) {
        stack<tuple<int, int, int> > stk;
        stk.push(mt(root, 0, 0));
        while (sz(stk)) {
            int v, p, d;
            tie(v, p, d) = stk.top();
            stk.pop();
            depth[v] = d;
            parent[v] = p;
            for (int to : G[v]) {
                if (to != p) {
                    stk.push(mt(to, v, d + 1));
                }
            }
        }
    }
};

pair<string, int> si[100001];

int N;
int M, pos[100001];
ll X, D;
int I[3000000], J[3000000];
// tuple<int, int, int> T[3000000];
char s_[800010];
string S[100001];

void init() {
    rep(i, M) {
        I[i] = (int)(X / (N - 1)) + 1;
        J[i] = (int)(X % (N - 1)) + 1;
        if (I[i] > J[i])swap(I[i], J[i]);
        else J[i] = J[i] + 1;
        X = ((X + D) % (N*(N - 1ll)));

        --I[i];
        --J[i];
    }
}

vector<vi> G;
int st[800010][26];
int cur = 1;

int f(string &s) {
    int u = 0;
    rep(i, sz(s)) {
        int a = s[i] - 'a';
        if (st[u][a] != -1) {
            u = st[u][a];
        }
        else {
            st[u][a] = cur;
            G[u].push_back(cur);
            u = cur;
            cur++;
        }
    }
    return u;
}

int main(){
    cin >> N;
    MEM(st, -1);

    int V = 0;
    rep(i, N) {
        scanf("%s", s_);
        // si[i].first = string(s_);
        // si[i].second = i;
        S[i] = string(s_);
        V += sz(S[i]);
    }
    G.resize(V + 10);

    // sort(si, si + N);
    // rep(i, N) {
//        id[si[i].second] = i;
//    }

    cin >> M >> X >> D;
    init();

 
    rep(i, N) {
        pos[i] = f(S[i]);
    }
    G.resize(cur);

    LCA lca(G);

    ll ans = 0;
    rep(i, M) {
        int anc = lca.get(pos[I[i]], pos[J[i]]);
        int dep = lca.getDepth(anc);
        ans += dep;
    }
    cout << ans << endl;
}
0