QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#405633#8630. 字符树strcmp#0 5ms4080kbC++141.6kb2024-05-06 11:24:182024-05-06 11:24:20

Judging History

你现在查看的是最新测评结果

  • [2024-05-06 11:24:20]
  • 评测
  • 测评结果：0
  • 用时：5ms
  • 内存：4080kb
查看
  • [2024-05-06 11:24:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn = 2e5 + 10;
int fa[maxn], dep[maxn], n, m, X; char a[maxn], b[maxn], c[maxn], d[maxn], f[maxn];
inline int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] != dep[y]) x = fa[x];
    while (x != y) x = fa[x], y = fa[y];
    return x;
}
int main() {
    scanf("%d%d%d", &n, &m, &X);
    for (int i = 2; i <= n; i++) scanf("%d", &fa[i]);
    scanf("%s", a + 2);
    for (int i = 1; i <= n; i++) dep[i] = dep[fa[i]] + 1;
    while (m--) {
        int o, x, y;
        scanf("%d%d%d%s", &o, &x, &y, b + 1);
        int l = lca(x, y), p = 0, q = 0;
        if (o == 1) {
            int pre = 1, nxt = X;
            while (x != l) a[x] = b[pre], x = fa[x], ++pre;
            while (y != l) a[y] = b[nxt], y = fa[y], --nxt;
        }
        else {
            while (x != l) c[++p] = a[x], x = fa[x];
            while (y != l) d[++q] = a[y], y = fa[y];
            for (int i = q; i >= 1; i--) c[++p] = d[i];
            for (int i = 1; i <= p; i++) f[i] = 0;
            for (int i = 2, j = 0; i <= p; i++) {
                while (j && c[i] != c[j + 1]) j = f[j];
                if (c[i] == c[j + 1]) ++j;
                f[i] = j;
            }
            int ans = 0;
            for (int i = 1, j = 0; i <= p; i++) {
                while (j && b[j + 1] != c[i]) j = f[j];
                if (b[j + 1] == c[i]) ++j;
                if (j == X) ++ans;
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3792kb

input:

250 250 62
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 30 67 68 8 70 16 72 3 74 75 32 77 75 31 80 81 65 83 30 19 49 4 1 89 57 91 92 43 94 95 96 85 51 32 100 8...

output:

1
1
1
1
1
1
1
1
0
0
1
1
0
0
0
1
1
1
1
1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
2
3
0
0
0
4
4
0
0
0
0
0
2
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
1
0
0
10
0
0
0
0
0
0
2
0
0
0
0
0
0
0
1
0
2
0
1
0
0
7

result:

wrong answer 10th numbers differ - expected: '1', found: '0'

Subtask #2:

score: 0
Runtime Error

Test #11:

score: 0
Runtime Error

input:

500000 650 769
1 2 3 4 5 6 7 8 9 10 11 12 7 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

result:

Subtask #3:

score: 0
Runtime Error

Test #21:

score: 0
Runtime Error

input:

500000 499998 1
1 2 3 4 5 6 7 8 1 1 11 12 13 14 15 16 1 1 19 20 21 22 23 24 1 26 1 28 29 30 1 32 33 34 35 1 37 38 39 40 41 42 43 1 45 46 47 48 49 50 1 52 53 54 55 56 57 1 1 60 61 62 63 64 65 66 67 68 69 1 71 1 73 1 75 76 77 78 79 80 81 82 83 1 1 86 87 88 89 1 91 92 93 94 95 96 97 98 99 100 101 102 1...

output:

result:

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Runtime Error

Test #41:

score: 0
Runtime Error

input:

499997 9 40060
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

result:

Subtask #6:

score: 0
Runtime Error

Test #51:

score: 0
Runtime Error

input:

500000 62500 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

result:

Subtask #7:

score: 0
Runtime Error

Test #61:

score: 0
Runtime Error

input:

500000 100000 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

result:

Subtask #8:

score: 0
Wrong Answer

Test #71:

score: 0
Wrong Answer
time: 5ms
memory: 4080kb

input:

25000 2500 10
1 2 3 4 5 6 7 8 9 10 1 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

0
0
1
1
1
75
1
3
0
3
8
0
1
1
1
0
1
1
3
0
57
0
0
1
1
1
0
1
0
2
0
0
0
5
0
0
1
0
1
2
0
1
81
3
1
0
0
0
19
0
0
0
0
0
0
0
0
0
0
1
0
2
0
1
1
0
0
0
1
0
0
0
3
0
1
0
0
0
3
5
0
0
0
0
0
1
0
0
0
5
2
0
5
6
4
1
0
1
0
22
0
0
0
1
1
0
0
1
5
0
0
0
41
2
1
0
1
1
0
0
0
1
4
0
0
0
0
1
0
0
3
2
0
0
2
0
39
2
0
0
3
0
0
61
0
1
...

result:

wrong answer 1st numbers differ - expected: '1', found: '0'

Subtask #9:

score: 0
Skipped

Dependency #8:

0%

Subtask #10:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2024-12-03 23:38:27 | OpenSource Project