QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#687061	#5015. 树	DaiRuiChen007	0	24ms	63272kb	C++17	975b	2024-10-29 16:57:08	2024-10-29 16:57:08

Judging History

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

[2024-10-29 16:57:08]
评测

测评结果：0
用时：24ms
内存：63272kb

查看

[2024-10-29 16:57:08]
提交

answer

#include<bits/stdc++.h>
//#include "grader.cpp"
#include "tree.h"
#define fi first
#define se second
using namespace std;
const int MAXN=1005;
mt19937 rnd(time(0));
int fa[MAXN],d[MAXN][MAXN];
vector <int> dep[MAXN];
void build(vector<int>&X,vector<int>&Y) {
	if(Y.empty()) return ;
	if(X.size()==1) {
		for(int o:Y) fa[o]=X[0];
		return ;
	}
	shuffle(X.begin(),X.end(),rnd);
	vector <int> S(X.begin(),X.begin()+X.size()/2);
	map <int,pair<vector<int>,vector<int>>> Z;
	for(int i:X) {
		int z=0;
		for(int j:S) z+=d[i][j];
		Z[z].fi.push_back(i);
	}
	for(int i:Y) Z[ask(i,S)-S.size()].se.push_back(i);
	for(auto it:Z) build(it.se.fi,it.se.se);
}
void solver(int n,int A,int B) {
	int rt=rnd()%n+1;
	for(int i=1;i<=n;++i) dep[ask(i,{rt})].push_back(i);
	vector <int> V;
	for(int i=1;i<=n;++i) {
		build(dep[i-1],dep[i]);
		for(int u:dep[i]) {
			answer(u,fa[u]);
			for(int v:V) d[u][v]=d[v][u]=d[fa[u]][v]+1;
			V.push_back(u);
		}
	}
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 3

Accepted

time: 13ms

memory: 11820kb

input:

1000 500000 500000
1 2
2 3
2 4
2 5
2 6
3 7
2 8
5 9
5 10
9 11
2 12
9 13
4 14
5 15
12 16
5 17
4 18
4 19
13 20
9 21
19 22
7 23
6 24
14 25
2 26
10 27
14 28
21 29
17 30
8 31
15 32
9 33
22 34
24 35
20 36
6 37
12 38
19 39
31 40
35 41
25 42
11 43
8 44
9 45
12 46
26 47
10 48
6 49
27 50
39 51
33 52
6 53
43 54...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #2:

score: 0

Wrong Answer

time: 24ms

memory: 63272kb

input:

1000 500000 500000
1 2
1 3
1 4
4 5
1 6
2 7
1 8
2 9
3 10
4 11
5 12
11 13
9 14
13 15
10 16
10 17
8 18
9 19
13 20
19 21
17 22
19 23
23 24
24 25
22 26
18 27
21 28
22 29
26 30
24 31
30 32
23 33
28 34
29 35
32 36
36 37
32 38
35 39
34 40
40 41
40 42
42 43
42 44
40 45
40 46
40 47
46 48
39 49
49 50
48 51
50 ...

output:

Too many queries

result:

wrong answer Wrong Answer

Subtask #2:

score: 0

Wrong Answer

Test #11:

score: 17

Accepted

time: 2ms

memory: 8232kb

input:

100 3000 40000
66 95
66 60
66 93
66 69
66 82
66 24
66 64
66 84
66 42
66 22
66 67
66 54
66 90
66 26
66 41
66 18
66 43
66 68
66 36
66 88
66 33
66 29
66 79
66 6
66 48
66 47
66 8
66 38
66 61
69 97
64 30
38 86
88 14
18 10
54 81
88 25
29 2
18 21
95 46
42 80
93 91
61 62
68 35
47 23
69 17
93 28
18 31
61 70
...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #12:

score: 17

Accepted

time: 1ms

memory: 6164kb

input:

100 3000 40000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #13:

score: 17

Accepted

time: 1ms

memory: 8232kb

input:

100 3000 40000
1 2
2 3
3 4
3 5
5 6
6 7
4 8
7 9
1 10
4 11
3 12
7 13
1 14
1 15
7 16
3 17
4 18
7 19
9 20
1 21
8 22
10 23
6 24
6 25
2 26
10 27
7 28
5 29
5 30
8 31
4 32
4 33
10 34
2 35
8 36
9 37
3 38
6 39
3 40
8 41
9 42
6 43
10 44
8 45
5 46
8 47
8 48
2 49
8 50
8 51
3 52
1 53
3 54
5 55
5 56
8 57
3 58
10 5...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #14:

score: 0

Wrong Answer

time: 0ms

memory: 7504kb

input:

100 3000 40000
13 50
17 13
62 17
5 62
74 5
83 74
98 83
37 98
80 37
23 80
87 23
27 87
40 27
95 40
52 95
54 52
67 54
42 67
18 42
34 18
81 34
59 81
12 59
30 12
64 30
15 64
92 15
61 92
1 61
72 1
16 72
3 16
48 3
31 48
41 31
77 41
93 77
33 93
96 33
53 96
28 53
90 28
25 90
26 25
57 55
85 57
45 85
20 45
22 ...

output:

Too many queries

result:

wrong answer Wrong Answer

Subtask #3:

score: 0

Wrong Answer

Test #111:

score: 0

Wrong Answer

time: 13ms

memory: 30716kb

input:

1000 50000 3000000
126 207
937 126
615 937
837 615
500 837
588 500
505 588
353 505
60 353
904 60
656 904
685 656
460 685
614 460
551 614
537 551
858 537
596 858
9 596
738 9
918 738
322 918
940 322
859 940
113 859
110 113
312 110
995 312
443 995
246 443
257 246
238 257
999 238
885 999
976 885
330 976...

output:

Too many queries

result:

wrong answer Wrong Answer

Subtask #4:

score: 0

Wrong Answer

Test #211:

score: 60

Accepted

time: 9ms

memory: 11728kb

input:

990 8500 300000
1 2
1 3
1 4
1 5
2 6
2 7
2 8
3 9
3 10
3 11
4 12
4 13
4 14
5 15
5 16
5 17
6 18
6 19
6 20
7 21
7 22
7 23
8 24
8 25
8 26
9 27
9 28
9 29
10 30
10 31
10 32
11 33
11 34
11 35
12 36
12 37
12 38
13 39
13 40
13 41
14 42
14 43
14 44
15 45
15 46
15 47
16 48
16 49
16 50
17 51
17 52
17 53
18 54
18...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #212:

score: 60

Accepted

time: 8ms

memory: 11808kb

input:

992 8500 300000
1 2
2 3
3 4
4 5
3 6
5 7
7 8
3 9
3 10
2 11
8 12
4 13
4 14
9 15
11 16
5 17
5 18
7 19
12 20
5 21
5 22
10 23
9 24
23 25
22 26
11 27
21 28
28 29
23 30
19 31
5 32
12 33
9 34
11 35
3 36
19 37
10 38
33 39
12 40
12 41
38 42
31 43
25 44
6 45
5 46
36 47
23 48
28 49
31 50
28 51
25 52
5 53
25 54
...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #213:

score: 60

Accepted

time: 4ms

memory: 12112kb

input:

999 8500 300000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 5...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #214:

score: 60

Accepted

time: 4ms

memory: 12096kb

input:

995 8500 300000
1 2
1 3
2 4
1 5
1 6
2 7
7 8
3 9
6 10
9 11
2 12
1 13
9 14
4 15
9 16
13 17
13 18
14 19
6 20
18 21
21 22
14 23
12 24
19 25
9 26
26 27
16 28
28 29
7 30
14 31
1 32
25 33
32 34
5 35
8 36
22 37
19 38
15 39
13 40
27 41
25 42
18 43
12 44
14 45
8 46
36 47
33 48
45 49
46 50
44 51
47 52
15 53
2 ...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #215:

score: 60

Accepted

time: 5ms

memory: 11824kb

input:

999 8500 300000
1 2
2 3
3 4
4 5
2 6
5 7
4 8
8 9
6 10
1 11
7 12
6 13
2 14
2 15
10 16
10 17
7 18
9 19
4 20
4 21
7 22
1 23
4 24
8 25
1 26
8 27
5 28
6 29
3 30
8 31
6 32
8 33
3 34
10 35
9 36
5 37
9 38
3 39
10 40
7 41
6 42
8 43
7 44
2 45
3 46
10 47
2 48
2 49
5 50
6 51
1 52
2 53
3 54
1 55
7 56
5 57
3 58
10...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #216:

score: 60

Accepted

time: 4ms

memory: 11788kb

input:

993 8500 300000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 5...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #217:

score: 60

Accepted

time: 8ms

memory: 11772kb

input:

995 8500 300000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 5...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #218:

score: 60

Accepted

time: 8ms

memory: 12100kb

input:

992 8500 300000
1 2
1 3
3 4
3 5
1 6
2 7
5 8
5 9
4 10
8 11
4 12
4 13
12 14
7 15
10 16
12 17
12 18
17 19
18 20
17 21
14 22
18 23
20 24
17 25
18 26
19 27
21 28
21 29
27 30
23 31
23 32
31 33
28 34
28 35
27 36
34 37
33 38
34 39
31 40
40 41
38 42
39 43
35 44
43 45
45 46
41 47
47 48
47 49
43 50
42 51
49 52...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #219:

score: 60

Accepted

time: 7ms

memory: 12092kb

input:

993 8500 300000
1 2
1 3
2 4
3 5
5 6
6 7
7 8
7 9
8 10
9 11
11 12
11 13
13 14
14 15
14 16
16 17
16 18
17 19
18 20
20 21
21 22
21 23
23 24
23 25
25 26
25 27
27 28
27 29
28 30
29 31
31 32
32 33
32 34
34 35
34 36
36 37
37 38
37 39
39 40
39 41
40 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
48 50
50 51
51...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #220:

score: 60

Accepted

time: 11ms

memory: 11852kb

input:

993 8500 300000
1 2
1 3
1 4
1 5
3 6
5 7
6 8
5 9
3 10
6 11
6 12
7 13
10 14
6 15
8 16
15 17
11 18
15 19
16 20
15 21
15 22
16 23
19 24
20 25
22 26
20 27
19 28
28 29
21 30
27 31
30 32
26 33
31 34
32 35
28 36
35 37
31 38
31 39
38 40
32 41
34 42
41 43
35 44
37 45
45 46
43 47
41 48
46 49
43 50
41 51
49 52
...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #221:

score: 60

Accepted

time: 3ms

memory: 11896kb

input:

997 8500 300000
1 2
2 3
1 4
2 5
2 6
1 7
1 8
1 9
1 10
2 11
2 12
1 13
2 14
1 15
1 16
2 17
1 18
1 19
1 20
1 21
2 22
1 23
1 24
1 25
2 26
2 27
2 28
1 29
2 30
1 31
2 32
2 33
1 34
2 35
2 36
1 37
1 38
1 39
1 40
2 41
2 42
1 43
2 44
1 45
1 46
1 47
2 48
1 49
2 50
1 51
2 52
1 53
2 54
1 55
1 56
1 57
1 58
1 59
2 ...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #222:

score: 60

Accepted

time: 12ms

memory: 11852kb

input:

991 8500 300000
1 2
1 3
2 4
1 5
1 6
1 7
7 8
6 9
9 10
4 11
5 12
9 13
9 14
9 15
13 16
9 17
16 18
11 19
11 20
12 21
17 22
21 23
21 24
17 25
17 26
25 27
24 28
27 29
25 30
27 31
31 32
26 33
28 34
28 35
29 36
30 37
31 38
30 39
34 40
31 41
37 42
34 43
36 44
41 45
43 46
41 47
47 48
41 49
47 50
42 51
42 52
5...

output:

areawavesuitbannerresortfatplasterdeclarationthesearejustrandomwords

result:

ok Orz..Orz..Orz..Orz..Orz

Test #223:

score: 0

Wrong Answer

time: 3ms

memory: 11800kb

input:

996 8500 300000
149 957
149 250
149 933
149 297
149 546
149 684
149 74
149 372
149 741
149 548
149 11
149 400
149 128
149 860
149 812
149 28
149 434
149 136
149 770
149 772
149 58
149 674
149 763
149 988
149 616
149 513
149 476
149 574
149 187
149 355
149 95
149 344
149 652
149 15
149 482
149 396
14...

output:

Too many queries

result:

wrong answer Wrong Answer