编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#4911 #1027. 艾泽拉斯的灾难 Time Limit Exceeded 40 17304 ms 15216 K C++ 17 / 1.1 K rabbitdit 2024-02-20 22:14:42
显示原始代码
#include <bits/stdc++.h>
using namespace std;
int n;
bool ok = 1;
int ot[100005][2];
struct node {
    node* fa[20];
    int depth;
    vector<node*> gra;
    bool vis;
    int mx;
} tree[100005];
void dfs(node* lo, bool ij, int dis) {
    ot[lo - tree][ij] = dis;
    for (int i = 0; i < lo->gra.size(); i++) {
        if (ot[lo->gra[i] - tree][ij] == -1)
            dfs(lo->gra[i], ij, dis + 1);
    }
}
int ans(node* a, node* b) {
    if (ok == 0) {
        for (int i = 1; i <= n; i++) {
            ot[i][0] = -1;
            ot[i][1] = -1;
        }
        dfs(a, 0, 0);
        dfs(b, 1, 0);
        int rt = 0;
        for (int i = 1; i <= n; i++) rt = max(rt, min(ot[i][0], ot[i][1]));
        return rt;
    }
    int ca = a - tree, cb = b - tree;
    if (ca > cb)
        swap(ca, cb);
    return max(ca - 1, max((cb - ca) / 2, n - cb));
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        if (u != v - 1)
            ok = 0;
        tree[u].gra.push_back(v + tree);
        tree[v].gra.push_back(u + tree);
    }
    tree[1].depth = 1;
    long long m, x, y;
    scanf("%lld%lld%lld", &m, &x, &y);
    long long out = 0;
    x %= n;
    x += 1;
    y %= n;
    y += 1;
    while (m--) {
        long long cans = ans(x + tree, y + tree);
        out ^= cans * cans;
        x = ((x ^ cans) + cans) % n + 1;
        y = ((y ^ cans) + cans) % n + 1;
    }
    cout << out;
    return 0;
}
子任务 #1
Time Limit Exceeded
得分:40
测试点 #1
Accepted
得分:100
用时:1565 ms
内存:10660 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

用户输出

137

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:1727 ms
内存:10652 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

用户输出

761

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:1833 ms
内存:10592 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

用户输出

349

系统信息

Exited with return code 0
测试点 #4
Time Limit Exceeded
得分:0
用时:2013 ms
内存:13280 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
测试点 #5
Accepted
得分:100
用时:90 ms
内存:12068 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

用户输出

4049854893

系统信息

Exited with return code 0
测试点 #6
Time Limit Exceeded
得分:0
用时:2009 ms
内存:15216 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
测试点 #7
Time Limit Exceeded
得分:0
用时:2047 ms
内存:15196 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
测试点 #8
Time Limit Exceeded
得分:0
用时:2007 ms
内存:15164 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
测试点 #9
Time Limit Exceeded
得分:0
用时:2006 ms
内存:15216 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
测试点 #10
Time Limit Exceeded
得分:0
用时:2007 ms
内存:15180 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