結果

問題 No.515 典型LCP
ユーザー nebukuro09nebukuro09
提出日時 2017-05-06 00:51:18
言語 D
(dmd 2.106.1)
結果
TLE  
実行時間 -
コード長 2,690 bytes
コンパイル時間 915 ms
コンパイル使用メモリ 119,644 KB
実行使用メモリ 414,076 KB
最終ジャッジ日時 2024-06-12 19:02:54
合計ジャッジ時間 5,429 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 # 

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;

immutable int MAX = 20;

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[0][n] = 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..MAX) {
        if ((1 << i) & diff)
            b = doubling[i][b];
    }

    while (a != b) {
        foreach (i; 0..MAX-1) {
            if (doubling[i+1][a] == doubling[i+1][b]) {
                a = doubling[i][a];
                b = doubling[i][b];
                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[][](MAX, global_num+1);
    depth = new int[](global_num+1);
    dfs(&root, 0, -1);

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

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