QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #319186 | #8161. 捉迷藏 | Yuics | 0 | 0ms | 0kb | C++20 | 2.1kb | 2024-02-02 08:31:57 | 2024-02-02 08:31:58 |
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e6 + 7;
int d, t, n, q, a, b, da, db, tot;
int tr[N << 2], dep[N], dfn[N], son[N], siz[N], top[N], fa[N];
vector<int> g[N << 2], ev[N << 2];
template <typename T> T read() {
T sum = 0, fl = 1;
int ch = getchar();
for (; !isdigit(ch); ch = getchar()) { if (ch == '-') fl = -1; }
for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
return sum * fl;
}
template <typename T> void write(T x) {
if (x < 0) { x = -x; putchar('-'); }
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
void init() {
for (int i = 1; i <= n; i++)
g[i].swap(ev[i]);
memset(son, 0, sizeof(son));
memset(siz, 0, sizeof(siz));
tot = 0;
}
int oDis(int x, int y) {
int fx = x, fy = y;
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]])
x = fa[top[x]];
else
y = fa[top[y]];
}
int lca = 0;
if (dep[x] < dep[y])
lca = x;
else
lca = y;
if (lca == fx) return dep[fy] - dep[lca];
else if (lca == fy) return dep[fx] - dep[lca];
return dep[fx] + dep[fy] - 2 * dep[lca];
}
void dfs1(int now, int p, int depth) {
fa[now]= p;
siz[now] = 1;
dep[now] = depth;
int cot = 0;
for (auto i : g[now]) {
if (siz[i]) continue;
dfs1(i, now, depth + 1);
siz[now] += siz[i];
if (siz[i] > cot) {
cot = siz[i];
siz[now] = i;
}
}
}
void dfs2(int now, int rt) {
dfn[now] = ++tot;
top[now] = rt;
if (son[now])
dfs2(son[now], rt);
for (auto i : g[now])
if (i != fa[now] && i != son[now])
dfs2(i, i);
}
int main() {
d = read<int>(), t = read<int>();
while (t--) {
n = read<int>(), q = read<int>();
init();
for (int i = 1; i < n; i++) {
int x = read<int>(), y = read<int>();
g[x].emplace_back(y);
g[y].emplace_back(x);
}
dfs1(1, 1, 1);
dfs2(1, 1);
for (int i = 1; i <= q; i++) {
a = read<int>(), b = read<int>(), da = read<int>(), db = read<int>();
int dis = oDis(a, b);
if (da >= dis)
puts("Zayin");
else if (da > db)
puts("Zayin");
else if (da < db)
puts("Ziyin");
else
puts("Draw");
}
}
return 0;
}
詳細信息
Test #1:
score: 0
Memory Limit Exceeded
input:
1 10000 10 39 3 6 4 2 8 1 3 4 8 10 9 8 5 8 6 7 8 3 3 2 7 6 5 7 9 5 7 9 7 7 10 7 8 4 1 10 4 4 6 4 8 1 3 4 8 2 4 2 3 6 1 3 4 9 2 5 6 4 6 4 5 9 9 1 8 2 1 5 2 3 7 8 4 5 6 9 9 2 5 2 3 8 5 7 6 2 9 10 4 8 7 6 3 7 10 1 5 4 2 3 6 4 8 1 3 8 10 3 4 2 9 8 4 9 6 4 6 5 9 5 1 7 2 1 5 2 7 1 6 7 6 7 5 6 2 3 9 7 2 6 ...
output:
result:
Test #2:
score: 0
Memory Limit Exceeded
input:
2 10000 67 1 30 43 6 53 2 1 5 18 36 44 10 13 34 11 56 27 62 42 35 31 25 52 22 2 32 33 13 47 19 2 14 58 5 25 14 9 32 2 53 67 14 16 63 13 15 52 62 24 43 25 49 57 58 25 28 11 2 53 28 48 51 66 59 25 2 62 9 8 37 39 13 62 5 42 47 12 59 23 4 9 31 45 63 46 43 66 55 60 17 39 50 53 17 35 33 29 28 3 7 61 49 38...
output:
result:
Test #3:
score: 0
Memory Limit Exceeded
input:
3 10000 100 47 11 77 48 82 5 99 2 92 3 59 55 28 33 96 43 3 81 15 87 7 92 59 77 91 86 84 87 37 91 39 58 5 51 48 31 49 67 68 4 36 97 60 90 48 22 72 18 11 83 29 30 59 41 79 32 19 71 78 26 85 23 85 46 91 97 32 1 59 96 81 41 16 34 80 41 84 82 67 11 98 45 67 32 82 87 49 65 82 85 91 64 6 58 22 69 93 59 17 ...
output:
result:
Test #4:
score: 0
Memory Limit Exceeded
input:
4 10000 52 1 52 16 10 49 12 9 10 39 33 13 40 41 35 46 36 23 45 34 10 37 15 12 19 3 41 47 3 50 26 16 7 29 20 49 4 24 1 21 4 25 43 35 6 24 41 5 52 34 8 51 29 40 31 33 49 24 28 2 34 24 27 16 52 40 40 14 41 15 35 49 14 30 28 6 42 48 36 52 17 20 8 19 12 18 19 12 38 13 44 36 22 38 36 21 16 42 52 13 11 46 ...
output:
result:
Test #5:
score: 0
Memory Limit Exceeded
input:
5 10000 122 86 101 30 95 102 74 111 97 78 70 49 80 59 9 4 46 41 12 80 102 51 57 79 81 73 120 100 9 61 86 38 7 13 58 67 36 29 17 66 85 37 99 69 93 51 68 20 8 6 119 56 43 75 102 108 2 96 115 104 85 28 107 73 47 26 64 60 12 68 80 11 18 78 50 75 48 39 35 67 49 122 23 91 85 90 100 67 18 100 19 16 32 106 ...
output:
result:
Test #6:
score: 0
Memory Limit Exceeded
input:
6 10 171533 1 27781 140891 34524 61242 123531 28085 55228 156200 76909 100609 56500 146846 169350 95862 100902 18874 19082 156163 74993 123457 3351 58196 121654 13912 49615 87507 35702 149699 64490 24084 110628 68493 42356 37165 128487 165923 94483 147367 109654 147615 115709 83252 98599 22850 83679...
output:
result:
Test #7:
score: 0
Memory Limit Exceeded
input:
7 200 7411 2955 6024 2924 6114 3540 4356 6189 2791 4008 441 1984 6359 4757 5648 2370 5165 6568 1127 6177 1723 6301 5444 2224 702 4095 4369 4652 6890 641 7411 3504 3073 3310 3824 1619 2846 178 1033 2308 636 2519 4165 3576 5493 5521 582 5989 5005 1336 3864 6242 3737 3560 6875 6383 1397 2756 4734 4536 ...
output:
Zayin Zayin Zayin Zayin Zayin Ziyin Zayin Zayin Zayin Ziyin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Ziyin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Ziyin Zayin Zayin Zayin Zayin Zayin ...
result:
Test #8:
score: 0
Time Limit Exceeded
input:
8 20 75348 104987 40941 58887 18150 54706 32360 27789 2534 24455 27071 58083 60814 12560 65570 10184 3042 34484 46838 62081 60761 19011 20878 11746 10503 20391 18992 74862 15041 13347 57504 15446 55636 44756 55034 45227 24955 43011 662 55071 18249 26933 31581 6903 15485 71130 2941 27859 46550 45110 ...
output:
Zayin Zayin Zayin Zayin Ziyin Ziyin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Ziyin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Ziyin Ziyin Zayin Zayin Ziyin Zayin Zayin Zayin Zayin Zayin ...
result:
Test #9:
score: 0
Memory Limit Exceeded
input:
9 20 5165 30036 3967 1316 2138 2978 604 2656 1298 4001 2274 4044 2635 2667 2647 1022 4464 36 3757 1299 194 967 478 4938 3078 2728 1596 3705 2796 4534 3514 30 665 2114 283 66 421 2095 185 2362 4128 962 3193 1377 3601 3236 1389 4335 2289 4698 3609 5001 4548 1335 2046 2984 1457 2286 1606 4805 2402 2346...
output:
Zayin Zayin Zayin Zayin Ziyin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Ziyin Zayin Zayin Zayin Zayin Ziyin Zayin Zayin Ziyin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin ...
result:
Test #10:
score: 0
Time Limit Exceeded
input:
10 2 48946 385893 40405 17572 6254 23829 39339 37960 37682 17464 9044 39920 12763 3185 34466 44346 537 17596 17227 48074 17972 41463 29781 39672 40328 11313 46733 39689 19093 2364 37585 20713 7580 35477 23504 17559 43991 22685 40278 45615 21701 44716 28957 22036 11079 48071 16589 41881 43330 1266 35...
output:
Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Ziyin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin Zayin ...