QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#863652#9678. 网友小 Z 的树cooluo16 1375ms17580kbC++231.5kb2025-01-19 20:47:002025-01-19 20:47:01

Judging History

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

  • [2025-01-19 20:47:01]
  • 评测
  • 测评结果:16
  • 用时:1375ms
  • 内存:17580kb
  • [2025-01-19 20:47:00]
  • 提交

answer

#include <bits/stdc++.h>
#include <bits/extc++.h>
#include "diameter.h"
using namespace std;

#define ll long long
#define pii pair<int, int>
#define mkpr make_pair
#define vi vector<int>
#define all(c) (c).begin(), (c).end()
#define rep(i, l, r) for (int i(l), i##End(r); i <= i##End; i = -~i)

int n, m;
__gnu_pbds::gp_hash_table<ll, int> mp;

int qry(int u, int v, int w) {
    if (u > v) swap(u, v);
    if (v > w) swap(v, w);
    if (u > v) swap(u, v);
    ll x = u * 1000000000000 + v * 1000000 + w;
    if (mp[x]) return mp[x];
    return mp[x] = query(u, v, w);
}

pii find_diameter(int task_id, int n) {
    mp.clear();
    if (n <= 2) return mkpr(1, n);
    int u = 1, v = 2, w = 3;
    rep(i, 1, n) if (i != u && i != v && i != w)
        if (qry(u, v, w) < qry(i, v, w)) u = i;
    rep(i, 1, n) if (i != u && i != v && i != w)
        if (qry(u, v, w) < qry(u, i, w)) v = i;
    rep(i, 1, n) if (i != u && i != v && i != w)
        if (qry(u, v, w) < qry(u, v, i)) w = i;
    int x = 0;
    rep(i, 1, n) if (i != u && i != v && i != w)
        if (!x || qry(u, v, i) < qry(u, v, x)) x = i;
    if (!x) {
        if (in(u, v, w)) return mkpr(v, w);
        if (in(v, u, w)) return mkpr(u, w);
        return mkpr(u, v);
    }
    if (in(u, v, x)) return mkpr(v, w);
    if (in(x, u, w)) swap(u, v);
    int a = qry(u, v, x) >> 1, b = qry(v, w, x) >> 1, c = qry(u, v, w) - a - b;
    int d = max({a, b, c});
    if (d == a) return mkpr(u, v);
    if (d == b) return mkpr(v, w);
    return mkpr(u, w);
}

详细

Subtask #1:

score: 16
Accepted

Test #1:

score: 16
Accepted
time: 4ms
memory: 10052kb

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
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #2:

score: 15
Accepted
time: 1375ms
memory: 17580kb

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:

correct

result:

ok Correct

Test #3:

score: 0
Time Limit Exceeded

input:

2 100
10000
5442 1084
1084 8984
8984 3299
3299 6385
6385 6079
6079 6806
6806 2300
2300 2996
2996 1765
1765 257
257 5537
5537 2337
2337 5445
5445 2873
2873 336
336 6307
6307 4968
4968 8078
8078 9944
9944 5675
5675 7896
7896 5943
5943 2412
2412 7448
7448 7852
7852 1684
1684 3437
3437 3980
3980 1919
19...

output:


result:


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%