QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#311986#8161. 捉迷藏Segment_Tree100 ✓1393ms159408kbC++142.2kb2024-01-23 08:14:312024-01-23 08:14:32

Judging History

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

  • [2024-01-23 08:14:32]
  • 评测
  • 测评结果:100
  • 用时:1393ms
  • 内存:159408kb
  • [2024-01-23 08:14:31]
  • 提交

answer

#include <bits/stdc++.h>

//#define int long long
#define LL long long
#define I ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define mem(a, v) memset(a, v, sizeof a)
#define re read()

const int N = 1e6 + 7, M = 16;

using namespace std;

inline LL read()
{
	int num = 0;char c;bool flag = false;
    while((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if(c == '-') flag = true;else num = c - '0';
    while(isdigit(c = getchar())) num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
} 

const int mod = 998244353, inf = 0x3f3f3f3f3f3fll;

int d, t;

int n, q;

int head[N], cnt;

int depth[N];

int jump[N][35], Log2[N];

struct Graph
{
	int to, nxt;
}edge[N << 1];

void init()
{
	cnt = 0;
	for (int i = 1; i <= n; i ++ )
	{
		head[i] = 0;
		depth[i] = 0;
		for (int p = 30; p >= 0; p -- )
			jump[i][p] = 0;
	}	
}

void add(int x, int y)
{
	edge[++ cnt].to = y, edge[cnt].nxt = head[x], head[x] = cnt;
}

void dfs(int u, int father)
{
	for (int i = head[u]; i; i = edge[i].nxt)
	{
		int j = edge[i].to;
		if (j == father) continue;
		depth[j] = depth[u] + 1;
		jump[j][0] = u;
		dfs(j, u);
	}
}

void Pre_For_LCA()
{
	for (int k = 1; k <= 30; k ++ )
		for (int i = 1; i <= n; i ++ )
			jump[i][k] = jump[jump[i][k - 1]][k - 1];
}

int Get_LCA(int x, int y)
{
	if (depth[x] < depth[y]) swap(x, y);
	for (int p = 30; p >= 0; p -- )
	{
		if (depth[jump[x][p]] >= depth[y]) x = jump[x][p];
	}
	if (x == y) return x;
	for (int p = 30; p >= 0; p -- )
	{
		if (jump[x][p] != jump[y][p]) x = jump[x][p], y = jump[y][p];
	}
	return jump[x][0];
}

signed main()
{
	I;
	
	d = re, t = re;
	while (t -- )
	{
		n = re, q = re;
		init();
		for (int i = 1; i < n; i ++ )
		{
			int u = re, v = re;
			add(u, v), add(v, u);
		}
		dfs(1, 1);//Get the father and depth
		Pre_For_LCA();
		while (q -- )
		{
			int a = re, b = re, da = re, db = re;
			int dist = depth[a] + depth[b] - 2 * depth[Get_LCA(a, b)];
			//Conclusion
			if (dist <= da) cout << "Zayin\n";
			else if (da > db) cout << "Zayin\n";
			else if (da < db) cout << "Ziyin\n";
			else cout << "Draw\n";//da = db 
		}
	}
}

詳細信息

Test #1:

score: 10
Accepted
time: 214ms
memory: 9816kb

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: 31ms
memory: 9808kb

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: 251ms
memory: 9864kb

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: 58ms
memory: 9916kb

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: 277ms
memory: 9888kb

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: 288ms
memory: 46240kb

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: 376ms
memory: 14396kb

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: 10
Accepted
time: 936ms
memory: 56620kb

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:

ok 1000000 lines

Test #9:

score: 10
Accepted
time: 696ms
memory: 31564kb

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:

ok 1000000 lines

Test #10:

score: 10
Accepted
time: 1393ms
memory: 159408kb

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:

ok 1000000 lines