首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#4873 #1027. 艾泽拉斯的灾难 Wrong Answer 0 3592 ms 15076 K C++ 17 / 1.4 K rabbitdit 2024-02-20 21:03:06
显示原始代码 
#include <bits/stdc++.h>
using namespace std;
int n;
struct node {
    node* fa[20];
    int depth;
    vector<node*> gra;
    bool vis;
    int mx;
} tree[100005];
void make_tree(node* lo) {
    lo->vis = 1;
    for (int i = 1; i < 20; i++) lo->fa[i] = NULL;
    for (int i = 2, ind = 1; i < lo->depth; i *= 2, ind++) lo->fa[ind] = lo->fa[ind - 1]->fa[ind - 1];
    for (int i = 0; i < lo->gra.size(); i++) {
        if (lo->gra[i]->vis)
            continue;
        node* to = lo->gra[i];
        to->depth = lo->depth + 1;
        to->fa[0] = lo;
        make_tree(to);
        lo->mx = max((to->mx) + 1, lo->mx);
    }
    return;
}
int ans(node* a, node* b) {
    if (a->depth < b->depth)
        swap(a, b);
    node* ca = a;
    node* cb = b;
    int dt = a->depth - b->depth;
    int rt = dt;
    for (int ind = pow(2, int(log2(dt) + 1)), i = log2(dt) + 1; dt > 0; ind /= 2, i--) {
        if (dt >= ind) {
            dt -= ind;
            a = a->fa[i];
        }
    }
    if (a == b)
        return max(max(max(rt / 2, (ca->mx) - 1), cb->depth), (cb->mx) - 1);
    for (int i = log2(dt) + 1, path = pow(2, i); i >= 0; i--, path /= 2) {
        if (path >= a->depth)
            continue;
        if (a->gra[i] != b->gra[i]) {
            a = a->gra[i];
            b = b->gra[i];
            rt += 2 * path;
        }
    }
    return max(max(max(rt / 2, (ca->mx) - 1), cb->depth), (cb->mx) - 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        tree[u].gra.push_back(v + tree);
        tree[v].gra.push_back(u + tree);
    }
    tree[1].depth = 1;
    make_tree(tree + 1);
    int m, x, y;
    scanf("%d%d%d", &m, &x, &y);
    long long out = 0;
    while (m--) {
        long long cans = ans(tree + x, tree + y);
        out ^= cans * cans;
        x = (x ^ cans + cans) % n + 1;
    }
    cout << out;
}
子任务 #1
Wrong Answer
得分：0
测试点 #1
Wrong Answer
得分：0
用时：27 ms
内存：10604 KiB

输入文件（1.in） 

5000
1 2
1 3
1 4
2 5
5 6
5 7
5 8
7 9
4 10
8 11
11 12
12 13
10 14
13 15
7 16
10 17
9 18
1 19
19 20
20
<45608 bytes omitted>

答案文件（1.out） 

137

用户输出 

92

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #2
Wrong Answer
得分：0
用时：31 ms
内存：10636 KiB

输入文件（2.in） 

5000
1 2
2 3
3 4
2 5
5 6
5 7
5 8
5 9
2 10
1 11
8 12
10 13
9 14
1 15
1 16
11 17
16 18
3 19
3 20
9 21

<45718 bytes omitted>

答案文件（2.out） 

761

用户输出 

68

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #3
Wrong Answer
得分：0
用时：26 ms
内存：10636 KiB

输入文件（3.in） 

5000
1 2
1 3
3 4
4 5
2 6
2 7
5 8
4 9
3 10
8 11
3 12
1 13
4 14
5 15
1 16
13 17
16 18
14 19
9 20
15 21
<45570 bytes omitted>

答案文件（3.out） 

349

用户输出 

0

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #4
Wrong Answer
得分：0
用时：129 ms
内存：12572 KiB

输入文件（4.in） 

100000
1 2
2 3
1 4
1 5
3 6
6 7
7 8
7 9
6 10
6 11
10 12
8 13
11 14
9 15
7 16
7 17
10 18
4 19
8 20
18 
<1149345 bytes omitted>

答案文件（4.out） 

876

用户输出 

0

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #5
Wrong Answer
得分：0
用时：93 ms
内存：15076 KiB

输入文件（5.in） 

100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19
<1177707 bytes omitted>

答案文件（5.out） 

4049854893

用户输出 

10705585036

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #6
Wrong Answer
得分：0
用时：173 ms
内存：13400 KiB

输入文件（6.in） 

100000
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1
<1051036 bytes omitted>

答案文件（6.out） 

260293561

用户输出 

611304928

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #7
Wrong Answer
得分：0
用时：70 ms
内存：13356 KiB

输入文件（7.in） 

100000
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1
<1050922 bytes omitted>

答案文件（7.out） 

211943169

用户输出 

0

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #8
Wrong Answer
得分：0
用时：173 ms
内存：13464 KiB

输入文件（8.in） 

100000
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1
<1051051 bytes omitted>

答案文件（8.out） 

1337740188

用户输出 

1474327028

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #9
Wrong Answer
得分：0
用时：1074 ms
内存：13500 KiB

输入文件（9.in） 

100000
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1
<1050939 bytes omitted>

答案文件（9.out） 

335272065

用户输出 

0

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #10
Wrong Answer
得分：0
用时：1796 ms
内存：13484 KiB

输入文件（10.in） 

100000
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1
<1050947 bytes omitted>

答案文件（10.out） 

743458136

用户输出 

212188144

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
BNBU Online Judge System Powered by SYZOJ.