QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#319187#8161. 捉迷藏Yuics70 2912ms40064kbC++202.1kb2024-02-02 08:32:432024-02-02 08:32:44

Judging History

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

  • [2024-02-02 08:32:44]
  • 评测
  • 测评结果:70
  • 用时:2912ms
  • 内存:40064kb
  • [2024-02-02 08:32:43]
  • 提交

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];

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].clear();
	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: 10
Accepted
time: 2862ms
memory: 19964kb

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:

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
Zayin
Zayin
Zayin
Draw
Zayin
Ziyin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Ziyin
Zayin
Zayin
Ziyin
Z...

result:

ok 1000000 lines

Test #2:

score: 10
Accepted
time: 2802ms
memory: 20052kb

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:

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
Zayin
Zayin
Zayin
Ziyin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Ziyin
Zayin
Zayin
...

result:

ok 10000 lines

Test #3:

score: 10
Accepted
time: 2881ms
memory: 19980kb

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:

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
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
...

result:

ok 1000000 lines

Test #4:

score: 10
Accepted
time: 2836ms
memory: 20104kb

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:

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
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Ziyin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Ziyin
...

result:

ok 10000 lines

Test #5:

score: 10
Accepted
time: 2912ms
memory: 20128kb

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:

Zayin
Zayin
Ziyin
Ziyin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Ziyin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Ziyin
Zayin
Zayin
Ziyin
Zayin
Ziyin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
...

result:

ok 1000000 lines

Test #6:

score: 10
Accepted
time: 180ms
memory: 40064kb

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:

Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin
Zayin

result:

ok 10 lines

Test #7:

score: 10
Accepted
time: 2340ms
memory: 22084kb

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:

ok 1000000 lines

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
Time 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
...

result: