首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#5259 #1037. 一棵树 Runtime Error 0 6572 ms 21796 K C++ 17 / 1.9 K YMD233 2024-02-29 10:55:41
显示原始代码 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
int n, q;
struct Nod {
    int to, nex;
    char val;
} edge[MAXN << 1];
int cnt, head[MAXN], u, v, lg[MAXN];
char w, val[MAXN];
string str;
void add(int u, int v, char w) {
    edge[++cnt].to = v;
    edge[cnt].val = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}
void merage(int u, int v, char w) {
    add(u, v, w);
    add(v, u, w);
}
int st[30][MAXN], dep[MAXN];
void dfs(int f, int x) {
    dep[x] = dep[f] + 1;
    st[0][x] = f;
    for (int i = head[x]; i; i = edge[i].nex) {
        int v = edge[i].to;
        if (f == v)
            continue;
        val[v] = edge[i].val;
        dfs(x, v);
    }
}
void init() {
    for (int k = 1; k < 30; ++k)
        for (int i = 1; i <= n; ++i) st[k][i] = st[k - 1][st[k - 1][i]];
    for (int i = 1; i < MAXN; ++i) lg[i] = lg[i - 1] + ((1 << (lg[i - 1] + 1)) == i);
}
int LCA(int x, int y) {
    if (x == y)
        return x;
    if (dep[x] < dep[y])
        swap(x, y);
    while (dep[x] > dep[y]) x = st[lg[dep[x] - dep[y]]][x];
    if (x == y)
        return x;
    for (int i = lg[dep[x]]; i >= 0; --i)
        if (st[i][x] != st[i][y]) {
            x = st[i][x];
            y = st[i][y];
        }
    return st[0][x];
}
string dis(int x, int y) {
    string temp = "";
    while (dep[x] > dep[y]) {
        temp = temp + val[x];
        x = st[0][x];
    }
    return temp;
}
string cov(string temp) {
    for (int i = 0; i < temp.size() / 2; ++i) {
        swap(temp[i], temp[temp.size() - i - 1]);
    }
    return temp;
}
string create(int x, int y) {
    string temp = "";
    int lca = LCA(x, y);
    temp = temp + dis(x, lca) + cov(dis(y, lca));
    return temp;
}
string sub(string o, int i, int len) {
    string temp = "";
    while (len) {
        temp = temp + o[i++];
        len--;
    }
    return temp;
}
int ans(string t, string str) {
    int temp = 0, len = str.size();
    for (int i = 0; i <= t.size() - str.size(); ++i)
        if (str == sub(t, i, len))
            temp++;
    return temp;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i < n; ++i) {
        cin >> u >> v >> w;
        merage(u, v, w);
    }
    dfs(0, 1);
    init();
    for (int i = 1; i <= q; ++i) {
        cin >> u >> v >> str;
        cout << ans(create(u, v), str) << endl;
        //		cout<<create(u,v)<<endl;
    }
    return 0;
}
子任务 #1
Runtime Error
得分：0
测试点 #1
Runtime Error
得分：0
用时：10 ms
内存：1780 KiB

输入文件（b1.in） 

50 49
6 14 k
2 4 k
36 39 k
44 18 k
22 8 k
15 24 k
22 40 d
3 2 k
32 26 k
46 23 k
11 20 k
4 12 k
41 50
<691 bytes omitted>

答案文件（b1.out） 

3
6
2
5
0
4
2
3
4
1
3
7
5
4
0
5
5
5
0
4
3
0
2
3
4
3
0
5
5
1
0
4
0
3
5
2
3
0
8
5
0
0
1
1
0
4
5
5
6

用户输出 

3
6
2
5
0
4
2
3
4
1
3
7
5
4

系统信息 

Killed: Segmentation fault
测试点 #2
Runtime Error
得分：0
用时：13 ms
内存：1908 KiB

输入文件（b2.in） 

499 500
433 349 z
228 286 k
412 251 k
359 361 k
51 43 k
46 50 k
27 53 k
169 188 k
79 67 k
12 54 k
25
<10413 bytes omitted>

答案文件（b2.out） 

0
12
7
0
17
0
0
13
24
10
24
22
16
0
19
14
0
21
13
23
0
25
13
0
0
11
0
6
18
24
21
17
10
0
0
9
16
0
15
<1136 bytes omitted>

用户输出 

0
12
7
0
17
0
0
13
24
10
24
22
16
0
19
14
0
21
13
23
0
25
13
0
0
11
0
6
18
24
21
17
10
0
0
9
16
0
15
17
13
19
27
16
21
0
1
1
3
0
<104 bytes omitted>

系统信息 

Killed: Segmentation fault
测试点 #3
Runtime Error
得分：0
用时：16 ms
内存：2060 KiB

输入文件（b3.in） 

999 998
192 193 k
32 33 k
78 79 k
434 433 k
106 105 k
465 464 k
791 809 k
448 624 k
282 281 v
638 63
<21383 bytes omitted>

答案文件（b3.out） 

0
301
285
117
93
1
192
168
116
55
345
174
327
0
2
169
285
42
59
295
216
88
25
120
133
227
69
3
0
197
<2908 bytes omitted>

用户输出 

0
301
285
117
93
1
192
168
116
55
345
174
327
0
2
169
285
42
59
295
216
88
25
120
133
227
69
3
0
197
75
68
190
154
31
292
16

系统信息 

Killed: Segmentation fault
测试点 #4
Time Limit Exceeded
得分：0
用时：1051 ms
内存：7052 KiB

输入文件（b4.in） 

29998 29999
27106 172 k
26614 26615 k
13826 13827 k
3676 3675 k
17580 338 k
18415 25107 k
15961 4891
<818567 bytes omitted>

答案文件（b4.out） 

1842
0
2312
3853
165
2879
3840
5270
11634
334
1360
107
1
951
10820
221
5393
465
328
4441
453
2441
31
<136681 bytes omitted>

用户输出 

1842
0
2312
3853
165
2879
3840
5270
11634
334
1360
107
1
951
10820
221
5393
465
328
4441
453
2441
314
2798
5245
8762
3773
6397
7
<1140 bytes omitted>
测试点 #5
Time Limit Exceeded
得分：0
用时：1004 ms
内存：7872 KiB

输入文件（b5.in） 

29999 29998
24958 24957 k
15893 15894 k
8605 8604 k
3364 3365 k
8358 8359 k
5260 5261 k
10075 10076 
<825238 bytes omitted>

答案文件（b5.out） 

10226
334
4280
16650
10897
2748
4165
6601
16580
9106
798
14774
15118
17092
5201
3484
2435
433
24267

<151979 bytes omitted>

用户输出 

10226
334
4280
16650
10897
2748
4165
6601
16580
9106
798
14774
15118
17092
5201
3484
2435
433
24267
11916
5971
6548
242
1138
269
<202 bytes omitted>
测试点 #6
Time Limit Exceeded
得分：0
用时：1055 ms
内存：20312 KiB

输入文件（b6.in） 

100000 100000
92093 97351 k
21424 99965 l
37869 72508 k
17250 72685 l
86348 1373 k
85798 95605 q
333
<2952117 bytes omitted>

答案文件（b6.out） 

68
1151
22143
1432
132
0
9295
400
76
0
287
63
715
120
8528
4
2335
0
313
3717
631
89
39
9
13
5
315
0

<361793 bytes omitted>

用户输出 

68
1151
22143
1432
132
0
9295
400
76
0
287
63
测试点 #7
Time Limit Exceeded
得分：0
用时：1007 ms
内存：21796 KiB

输入文件（b7.in） 

99998 99999
76581 76582 k
78930 78931 k
62222 62223 k
17883 17884 x
48420 48419 k
94485 94484 k
9530
<2955380 bytes omitted>

答案文件（b7.out） 

16054
12
0
114
366
1
358
29786
7903
900
6059
2325
171
5
23451
255
61
429
0
320
1735
516
2157
3260
14
<363949 bytes omitted>

用户输出 

16054
12
0
114
测试点 #8
Time Limit Exceeded
得分：0
用时：1051 ms
内存：18516 KiB

输入文件（b8.in） 

99999 100000
82369 83327 k
73396 97239 k
25906 25905 k
53413 90940 k
68205 44751 k
49865 60019 k
632
<2950540 bytes omitted>

答案文件（b8.out） 

8355
7823
1036
14662
21541
13609
551
2551
1157
1744
4298
0
11922
0
2145
457
16361
2704
18184
13630
1
<431243 bytes omitted>

用户输出 

8355
7823
1036
14662
21541
13609
551
2551
1157
1744
4298
0
11922
0
2145
457
16361
2704
18184
13630
13742
2911
1527
27
2971
2334

<6 bytes omitted>
测试点 #9
Time Limit Exceeded
得分：0
用时：1003 ms
内存：19356 KiB

输入文件（b9.in） 

99999 99999
10246 10247 k
67700 40923 k
61828 25931 k
75232 85195 n
45659 83881 k
81519 33578 i
4874
<2948282 bytes omitted>

答案文件（b9.out） 

124
16
3661
7081
4058
2383
6203
589
1170
16580
10
15853
86
8042
18329
1162
0
4325
1293
10638
23
1451
<408036 bytes omitted>

用户输出 

124
16
3661
7081
4058
2383
6203
589
1170
16580
10
15853
86
8042
18329
1162
0
4325
1293
10638
23
测试点 #10
Runtime Error
得分：0
用时：362 ms
内存：16968 KiB

输入文件（b10.in） 

99999 99998
30169 30168 b
54618 54617 k
41687 41688 k
93051 93052 k
80026 80025 k
97661 97662 z
7533
<2955125 bytes omitted>

答案文件（b10.out） 

0
649
0
0
4
1544
1162
5
2216
901
545
0
854
802
6
567
1059
0
1408
10
151
0
1
2577
1
1883
42
1869
17
2
<348298 bytes omitted>

用户输出 

0
649
0
0
4
1544
1162
5
2216
901
545
0
854
802
6
567
1059
0
1408
10
151
0
1
2577
1
1883
42
1869
17
2052
151
363
3
9
250
572
1492
<978 bytes omitted>

系统信息 

Killed: Segmentation fault
BNBU Online Judge System Powered by SYZOJ.