QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#859634#9678. 网友小 Z 的树HuTao16 17ms17996kbC++141.5kb2025-01-17 21:18:092025-01-17 21:18:44

Judging History

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

  • [2025-01-17 21:18:44]
  • 评测
  • 测评结果:16
  • 用时:17ms
  • 内存:17996kb
  • [2025-01-17 21:18:09]
  • 提交

answer

#include "diameter.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, dis[N];

inline void Find(int a, int b, int &c, int &d)
{
    c = d = 0;
    for(int i = 1; i <= n; i ++ )
    {
        if(i == a || i == b)
        {
            dis[i] = -1;
        }
        else
        {
            dis[i] = query(a, b, i);
            if(!c)
            {
                c = d = i;
            }
            else
            {
                if(dis[i] > dis[c]) c = i;
                if(dis[i] < dis[d]) d = i;
            }
        }
    }
}

std::pair<int, int> find_diameter(int subid, int _n)
{
    n = _n;
    if(n == 1) return make_pair(1, 1);
    if(n == 2) return make_pair(1, 2);
    if(n == 3)
    {
        if(in(1, 2, 3)) return make_pair(2, 3);
        if(in(2, 1, 3)) return make_pair(1, 3);
        return make_pair(1, 2);
    }

    int a = 1, b = 2, c, d = 0;
    Find(a, b, c, d);
    Find(a, c, b, d);
    Find(b, c, a, d);

    if(!in(d, b, c)) return make_pair(a, d);
    if(dis[a] == dis[d]) return make_pair(b, c);
    int dab, dac, dbc = dis[d] / 2;
    if(in(d, a, b))
    {
        dab = query(d, a, b) / 2;
        dac = dis[a] - dab - dbc;
    }
    else
    {
        dac = query(d, a, c) / 2;
        dab = dis[a] - dac - dbc;
    }

    if(dab > dac && dab > dbc) return make_pair(a, b);
    if(dac > dbc) return make_pair(a, c);
    return make_pair(b, c);
}

详细

Subtask #1:

score: 16
Accepted

Test #1:

score: 16
Accepted
time: 1ms
memory: 14292kb

input:

1 100
25
1 3
2 18
3 8
4 18
5 14
6 22
7 18
8 10
9 11
10 12
11 25
12 16
13 11
14 17
15 17
16 25
17 2
18 20
19 18
20 12
21 1
22 17
23 14
24 1
50
1 37
2 27
3 10
4 25
5 16
6 17
7 10
8 36
9 16
10 6
11 48
12 2
13 28
14 30
15 10
16 44
17 31
18 1
19 6
20 7
21 30
22 42
23 45
24 23
25 27
26 39
27 45
28 48
29 4...

output:

correct

result:

ok Correct

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #2:

score: 0
Wrong Answer
time: 17ms
memory: 17996kb

input:

2 2006
42
1 32
2 4
3 6
4 29
5 1
6 42
7 10
8 16
9 6
10 25
11 42
12 8
13 36
14 8
15 17
16 3
17 6
18 21
19 23
20 31
21 42
22 6
23 32
24 7
25 27
26 34
27 31
28 6
29 41
30 20
31 9
32 7
33 3
34 5
35 5
36 1
37 8
38 14
39 15
40 12
41 22
95
1 94
2 88
3 13
4 71
5 37
6 45
7 87
8 24
9 76
10 54
11 69
12 95
13 90...

output:

WA

result:

wrong answer Wrong Answer

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%

Subtask #8:

score: 0
Skipped

Dependency #7:

0%

Subtask #9:

score: 0
Skipped

Dependency #8:

0%

Subtask #10:

score: 0
Skipped

Dependency #9:

0%

Subtask #11:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%