結果
問題 | No.515 典型LCP |
ユーザー | pekempey |
提出日時 | 2017-05-06 06:17:02 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 632 ms / 1,000 ms |
コード長 | 1,498 bytes |
コンパイル時間 | 273 ms |
コンパイル使用メモリ | 42,764 KB |
実行使用メモリ | 225,244 KB |
最終ジャッジ日時 | 2023-10-12 14:29:25 |
合計ジャッジ時間 | 5,255 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 632 ms
166,108 KB |
testcase_01 | AC | 125 ms
17,692 KB |
testcase_02 | AC | 113 ms
25,564 KB |
testcase_03 | AC | 4 ms
15,296 KB |
testcase_04 | AC | 4 ms
15,272 KB |
testcase_05 | AC | 271 ms
222,852 KB |
testcase_06 | AC | 272 ms
222,976 KB |
testcase_07 | AC | 272 ms
222,860 KB |
testcase_08 | AC | 283 ms
222,912 KB |
testcase_09 | AC | 82 ms
27,776 KB |
testcase_10 | AC | 83 ms
30,160 KB |
testcase_11 | AC | 82 ms
29,888 KB |
testcase_12 | AC | 82 ms
27,824 KB |
testcase_13 | AC | 88 ms
38,308 KB |
testcase_14 | AC | 26 ms
42,948 KB |
testcase_15 | AC | 263 ms
225,224 KB |
testcase_16 | AC | 266 ms
225,244 KB |
ソースコード
#include <cstdio> #include <algorithm> constexpr int N = 800001; char buf[N]; int trie[N][26]; int pos[100000]; int eulerID[N]; int now; int rmq[21][N * 2]; int lg[N * 2]; int readint() { int n; scanf("%d", &n); return n; } long long readlong() { long long n; scanf("%lld", &n); return n; } void dfs(int u, int depth) { eulerID[u] = now; rmq[0][now++] = depth; for (int i = 0; i < 26; i++) { if (!trie[u][i]) { continue; } dfs(trie[u][i], depth + 1); rmq[0][now++] = depth; } } int main() { const int n = readint(); int cnt = 1; for (int i = 0; i < n; i++) { scanf("%s", buf); int u = 0; for (int j = 0; buf[j] != 0; j++) { char c = buf[j] - 'a'; if (!trie[u][c]) { trie[u][c] = cnt++; } u = trie[u][c]; } pos[i] = u; } dfs(0, 0); for (int i = 2; i <= now; i++) { lg[i] = lg[i / 2] + 1; } for (int i = 0; i + 1 <= lg[now]; i++) { for (int j = 0; j + (1 << i) < now; j++) { rmq[i + 1][j] = std::min(rmq[i][j], rmq[i][j + (1 << i)]); } } const int m = readint(); long long x = readlong(); const long long d = readlong(); long long ans = 0; for (int foo = 0; foo < m; foo++) { int i = x / (n - 1); int j = x % (n - 1); if (i > j) { std::swap(i, j); } else { j++; } x = (x + d) % (1LL * n * (n - 1)); int l = eulerID[pos[i]]; int r = eulerID[pos[j]]; if (l > r) { std::swap(l, r); } r++; const int k = lg[r - l]; ans += std::min(rmq[k][l], rmq[k][r - (1 << k)]); } printf("%lld\n", ans); }