結果
問題 | No.515 典型LCP |
ユーザー | pekempey |
提出日時 | 2017-05-06 05:51:07 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,884 bytes |
コンパイル時間 | 267 ms |
コンパイル使用メモリ | 44,612 KB |
実行使用メモリ | 231,820 KB |
最終ジャッジ日時 | 2023-10-12 14:11:15 |
合計ジャッジ時間 | 4,073 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 339 ms
199,944 KB |
testcase_01 | AC | 109 ms
142,692 KB |
testcase_02 | AC | 98 ms
142,368 KB |
testcase_03 | AC | 59 ms
142,256 KB |
testcase_04 | AC | 59 ms
142,304 KB |
testcase_05 | AC | 217 ms
229,504 KB |
testcase_06 | AC | 219 ms
229,632 KB |
testcase_07 | AC | 217 ms
229,592 KB |
testcase_08 | AC | 224 ms
229,548 KB |
testcase_09 | AC | 80 ms
142,520 KB |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | AC | 83 ms
144,672 KB |
testcase_14 | WA | - |
testcase_15 | AC | 214 ms
231,792 KB |
testcase_16 | AC | 214 ms
231,820 KB |
ソースコード
#include <cstdio> #include <algorithm> #include <ctime> constexpr int N = 800001; char buf[N]; int trie[N][26]; int pos[100000]; bool marked[N]; int eulerID[N]; int now; int rmq[22][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() { clock_t beg, end; beg = clock(); 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 < N * 2; i++) { lg[i] = lg[i / 2] + 1; } for (int i = 0; i < 21; i++) { for (int j = 0; j + (1 << i) < N * 2; j++) { rmq[i + 1][j] = std::min(rmq[i][j], rmq[i][j + (1 << i)]); } } end = clock(); fprintf(stderr, "%.20f\n", (double)(end - beg) / CLOCKS_PER_SEC); const int m = readint(); const long long x = readlong(); const long long d = readlong(); int ii = x % (n - 1); int jj = x / (n - 1); const int di = d % (n - 1); const int dj = d / (n - 1); long long ans = 0; for (int foo = 0; foo < m; foo++) { int i = jj; int j = ii; if (i > j) { std::swap(i, j); } else { j++; } ii += di; if (ii >= n - 1) { ii -= n - 1; jj++; } jj += dj; if (jj >= n) { jj -= n; } int l = eulerID[pos[i]]; int r = eulerID[pos[j]] + 1; if (l > r) { std::swap(l, r); } const int k = lg[r - l]; ans += std::min(rmq[k][l], rmq[k][r - (1 << k)]); } printf("%lld\n", ans); end = clock(); fprintf(stderr, "%.20f\n", (double)(end - beg) / CLOCKS_PER_SEC); }