QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#863652 | #9678. 网友小 Z 的树 | cooluo | 16 | 1375ms | 17580kb | C++23 | 1.5kb | 2025-01-19 20:47:00 | 2025-01-19 20:47:01 |
Judging History
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%