結果

問題 No.515 典型LCP
コンテスト
ユーザー nebukuro09
提出日時 2017-05-06 00:32:32
言語 D
(dmd 2.109.1)
結果
TLE  
実行時間 -
コード長 2,471 bytes
コンパイル時間 879 ms
コンパイル使用メモリ 123,156 KB
実行使用メモリ 293,280 KB
最終ジャッジ日時 2024-06-12 19:02:44
合計ジャッジ時間 6,178 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;


struct Trie {
    int num;
    Trie*[26] children;
}

Trie root;
int global_num = 0;

int trie_insert(string s) {
    int n = s.length.to!int;
    Trie* tmp = &root;

    foreach (i; 0..n) {
        if (tmp.children[s[i]-'a'] is null) {
            global_num++;
            tmp.children[s[i]-'a'] = new Trie(global_num);
        }
        tmp = tmp.children[s[i]-'a'];
    }
    return tmp.num;
}

int[][] edges, doubling;
int[] depth;

void dfs(Trie* t, int d, int prev) {
    int n = t.num;
    doubling[n][0] = prev;
    depth[n] = d;
    foreach (i; 0..26) {
        if (t.children[i] is null) continue;
        edges[n] ~= t.children[i].num;
        edges[t.children[i].num] ~= n;
        dfs(t.children[i], d+1, n);
    }
}


int lca(int a, int b) {
    if (a == b) return a;

    if (depth[b] < depth[a]) swap(a, b);
    int diff = depth[b] - depth[a];
    foreach (i; 0..30) {
        if ((1 << i) & diff)
            b = doubling[b][i];
    }

    while (a != b) {
        foreach (i; 0..30-1) {
            if (doubling[a][i+1] == doubling[b][i+1]) {
                a = doubling[a][i];
                b = doubling[b][i];
                break;
            }
        }
    }

    return a;
}


void main() {
    auto N = readln.chomp.to!long;
    auto S = N.iota.map!(_ => readln.chomp).array;
    auto ttt = readln.split.map!(to!long);
    auto M = ttt[0];
    auto x = ttt[1];
    auto d = ttt[2];

    auto I = new long[](M);
    auto J = new long[](M);
    foreach (k; 0..M) {
        I[k] = (x / (N - 1)) + 1;
        J[k] = (x % (N - 1)) + 1;
        if (I[k] > J[k]) swap(I[k], J[k]);
        else J[k] += 1;
        x = (x + d) % (N * (N - 1));
    }

    auto s_to_v = new int[](N);
    foreach (i; 0..N) {
        s_to_v[i] = trie_insert(S[i]);
    }

    edges = new int[][](global_num+1);
    doubling = new int[][](global_num+1, 30);
    depth = new int[](global_num+1);
    dfs(&root, 0, -1);

    fill(doubling[0], -1);
    foreach (j; 1..30) {
        foreach (i; 1..global_num+1) {
            doubling[i][j] = doubling[max(0, doubling[i][j-1])][j-1];
        }
    }

    long ans = 0;
    foreach (k; 0..M) {
        int i = I[k.to!int].to!int;
        int j = J[k.to!int].to!int;
        ans += depth[lca(s_to_v[i-1], s_to_v[j-1])];
    }
    ans.writeln;
}
0