QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491320#8757. 图yqh2025RE 51ms7356kbC++141.2kb2024-07-25 18:47:152024-07-25 18:47:16

Judging History

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

  • [2024-07-25 18:47:16]
  • 评测
  • 测评结果：RE
  • 用时：51ms
  • 内存：7356kb
查看
  • [2024-07-25 18:47:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,k,fa[N];
int find(int x){return (fa[x]==x)?x:(fa[x]=find(fa[x]));}
void add(int x,int y){if(find(x)!=find(y))fa[find(x)]=find(y);}
#define id(i,j) ((i-1)*n+j)
vector<int>E[N];
int vis[N],st[N],top,flag;
void dfs(int u,int goal){
	st[++top]=u;vis[u]=1;
	if(u==goal){
		printf("%d ",top);
		for(int i=1;i<=top;i++){
			int x=st[i]%n;if(x==0)x=n;
			printf("%d ",x);
		}
		puts("");
		return;
	}
	for(int v:E[u]){
		if(vis[v])continue;
		dfs(v,goal);
	}
	top--;
}
void sol(){
	scanf("%d%d",&n,&m);k=(m+n-2)/(n-1);
	for(int i=1;i<=k*n;i++)fa[i]=i,E[i].clear(),vis[i]=0;
	int s,t;s=t=0;
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		int ans=0;
		for(int j=12;j>=0;j--){
			int mid=ans+(1<<j);
			if(mid>k)continue;
			if(find(id(mid,x))==find(id(mid,y)))ans=mid;
		}
		ans++;
		add(id(ans,x),id(ans,y));
		if(ans==k)s=x,t=y;
		E[id(ans,x)].push_back(id(ans,y));
		E[id(ans,y)].push_back(id(ans,x));
	}
	if(!s){
		puts("-1");
		return;
	}
	printf("%d %d\n",s,t);
	for(int i=1;i<=k;i++){
		int x=id(i,s),y=id(i,t);
		flag=0;	dfs(x,y);top=0;
	}
}
signed main(){
	int t;cin>>t;
	while(t--)sol();
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 51ms
memory: 6584kb

input:

10000
2 20
1 2
1 2
2 1
1 2
1 2
2 1
1 2
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
1 2
2 1
2 20
2 1
2 1
2 1
2 1
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
1 2
2 20
1 2
2 1
1 2
1 2
2 1
2 1
1 2
1 2
2 1
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
1 2
2 1
2 1
2 20
1 2
2 1
2 1
1 2
1 2
1 2
2 1
1 2
2 ...

output:

2 1
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
1 2
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1 2 
2 1
2 2 1 
2...

result:

ok Answer correct. (10000 test cases)

Test #2:

score: 0
Accepted
time: 36ms
memory: 6688kb

input:

10000
5 20
2 1
2 5
5 3
3 1
4 5
1 4
4 3
4 5
3 5
5 4
2 3
5 2
3 4
3 5
1 4
4 3
4 2
2 1
1 3
5 1
5 20
4 2
1 3
1 2
4 5
2 4
3 1
5 3
5 1
4 5
4 3
2 4
1 4
4 3
5 2
1 2
3 5
1 5
4 1
3 4
4 3
5 20
1 4
1 3
1 5
5 1
4 5
3 4
4 5
2 3
1 2
2 4
4 5
4 5
2 4
2 5
4 2
4 3
4 2
2 5
2 1
3 1
5 20
2 5
2 3
4 5
4 2
3 4
2 1
5 4
2 5
2 ...

output:

1 3
4 1 2 5 3 
2 1 3 
3 1 4 3 
4 1 2 4 3 
2 1 3 
3 4
4 3 1 2 4 
3 3 5 4 
2 3 4 
2 3 4 
2 3 4 
2 5
4 2 3 1 5 
3 2 1 5 
3 2 4 5 
3 2 4 5 
2 2 5 
5 2
2 5 2 
3 5 4 2 
2 5 2 
2 5 2 
2 5 2 
5 1
2 5 1 
2 5 1 
2 5 1 
2 5 1 
2 5 1 
3 2
3 3 5 2 
5 3 5 1 4 2 
4 3 1 5 2 
4 3 1 5 2 
2 3 2 
4 2
3 4 3 2 
2 4 2 
3 ...

result:

ok Answer correct. (10000 test cases)

Test #3:

score: 0
Accepted
time: 34ms
memory: 6284kb

input:

10000
10 20
9 4
8 6
2 10
2 9
7 10
4 6
9 4
2 1
4 7
1 5
7 2
4 1
5 9
7 6
8 2
9 4
5 9
9 8
7 3
2 4
10 20
3 8
8 9
8 7
9 2
3 10
9 3
8 1
9 4
8 9
4 7
7 5
5 10
1 3
3 4
3 7
3 8
3 9
1 4
3 6
2 4
10 20
7 6
8 10
3 8
2 8
4 8
4 8
4 6
4 1
1 7
4 6
5 9
5 2
4 7
10 9
6 7
10 5
2 4
4 1
3 2
4 9
10 20
2 1
9 8
7 6
2 10
9 5
4 ...

output:

2 4
3 2 9 4 
3 2 7 4 
2 2 4 
1 4
4 1 8 9 4 
3 1 3 4 
2 1 4 
4 1
2 4 1 
3 4 7 1 
2 4 1 
6 2
7 6 4 3 9 5 1 2 
3 6 8 2 
2 6 2 
3 10
5 3 2 7 4 10 
4 3 9 2 10 
2 3 10 
1 8
3 1 7 8 
6 1 10 3 2 6 8 
2 1 8 
6 9
4 6 4 7 9 
5 6 5 7 3 9 
2 6 9 
1 10
2 1 10 
3 1 5 10 
2 1 10 
10 8
3 10 6 8 
4 10 9 7 8 
2 10 8 
...

result:

ok Answer correct. (10000 test cases)

Test #4:

score: 0
Accepted
time: 15ms
memory: 6180kb

input:

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

output:

21 38
4 21 41 34 38 
2 21 38 
7 10
6 7 36 24 9 37 10 
2 7 10 
23 26
13 23 21 24 14 36 10 1 8 40 28 3 43 26 
2 23 26 
39 16
2 39 16 
2 39 16 
37 11
8 37 12 43 50 17 19 35 11 
2 37 11 
38 46
11 38 45 19 30 9 22 41 12 31 3 46 
2 38 46 
3 11
10 3 6 2 13 7 31 15 22 32 11 
2 3 11 
46 17
9 46 42 36 26 27 2...

result:

ok Answer correct. (2000 test cases)

Test #5:

score: 0
Accepted
time: 36ms
memory: 6564kb

input:

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

output:

31 38
7 31 16 30 15 22 27 38 
17 31 32 25 33 34 23 24 6 27 1 47 36 8 2 4 10 38 
10 31 47 43 34 27 30 50 29 17 38 
9 31 30 13 7 24 29 17 48 38 
10 31 5 32 40 29 9 49 37 2 38 
6 31 1 25 6 37 38 
3 31 43 38 
8 31 35 33 22 6 43 8 38 
8 31 41 10 47 45 14 8 38 
8 31 20 22 41 11 14 3 38 
5 31 23 29 15 38 
...

result:

ok Answer correct. (200 test cases)

Test #6:

score: 0
Accepted
time: 37ms
memory: 7356kb

input:

20
100 10000
77 84
14 62
84 5
4 67
99 44
54 18
39 53
58 88
32 3
61 19
76 14
28 72
92 34
20 1
14 66
98 25
53 99
55 40
13 70
42 62
32 41
93 14
74 66
92 62
42 12
94 35
26 65
82 85
100 34
79 47
87 59
4 92
46 4
77 63
17 62
32 23
46 76
61 26
89 41
10 18
17 64
55 61
89 42
8 71
75 89
2 81
9 63
42 32
23 34
7...

output:

39 61
11 39 53 99 20 89 42 62 92 4 26 61 
3 39 69 61 
14 39 52 25 66 96 91 72 46 98 31 22 19 73 61 
2 39 61 
10 39 69 17 47 100 88 44 49 11 61 
23 39 9 79 88 20 80 12 63 44 99 40 4 73 100 14 76 27 29 43 28 15 93 61 
10 39 31 65 86 15 10 13 48 12 61 
15 39 75 93 47 69 87 16 88 99 57 49 1 46 43 61 
11...

result:

ok Answer correct. (20 test cases)

Test #7:

score: 0
Accepted
time: 32ms
memory: 6472kb

input:

100
1000 1999
527 98
626 570
505 814
510 660
334 873
893 329
51 818
256 113
165 543
515 780
905 200
560 363
385 813
82 324
661 719
3 624
175 120
22 480
662 730
701 676
124 107
820 707
288 412
596 842
285 574
209 109
897 789
37 371
399 502
715 361
877 504
68 73
919 671
685 732
866 390
975 122
994 263...

output:

183 97
14 183 906 447 101 368 216 113 256 645 629 510 660 786 97 
19 183 942 643 548 798 886 89 569 820 999 313 278 968 756 703 946 253 732 97 
2 183 97 
906 933
8 906 48 943 924 937 197 39 933 
28 906 536 924 307 206 369 443 827 692 304 774 614 529 778 163 87 339 691 830 268 491 960 464 559 853 648...

result:

ok Answer correct. (100 test cases)

Test #8:

score: 0
Accepted
time: 11ms
memory: 6088kb

input:

1000
100 100
8 93
14 86
43 53
73 87
9 5
30 87
23 88
9 18
89 75
49 53
39 91
58 22
86 27
75 1
57 90
20 40
71 55
58 77
63 46
97 95
6 71
19 92
54 24
50 96
30 50
11 79
70 20
79 24
88 33
8 86
18 60
51 58
66 39
93 31
1 47
41 65
45 12
3 93
62 33
38 49
29 91
3 29
15 51
37 56
54 6
85 95
2 81
36 28
10 98
57 26...

output:

78 56
24 78 23 88 33 62 9 70 20 40 43 53 76 27 86 8 93 3 29 91 87 30 50 96 56 
2 78 56 
18 45
11 18 85 59 69 1 23 75 47 13 93 45 
2 18 45 
9 92
9 9 69 24 30 15 34 85 57 92 
2 9 92 
7 60
23 7 99 61 63 43 84 78 26 13 98 55 72 15 42 76 21 75 23 88 86 67 87 60 
2 7 60 
13 57
16 13 70 19 71 4 74 86 93 46...

result:

ok Answer correct. (1000 test cases)

Test #9:

score: 0
Accepted
time: 31ms
memory: 6340kb

input:

500
200 399
181 137
41 68
61 54
32 10
41 136
85 112
127 111
51 107
143 189
21 69
149 109
107 120
21 158
175 53
31 48
80 170
46 108
163 85
110 142
2 30
117 128
109 114
142 178
76 43
118 63
36 149
45 74
165 123
43 72
87 185
70 173
132 79
130 163
187 10
189 114
70 22
12 184
200 175
65 169
23 27
1 14
19...

output:

98 125
15 98 24 75 59 104 110 142 188 170 80 79 200 175 78 125 
20 98 90 189 53 150 190 132 45 186 61 178 116 14 157 160 20 17 198 13 125 
2 98 125 
83 102
16 83 112 13 28 10 128 64 33 57 124 31 4 120 167 107 102 
12 83 88 176 50 89 78 161 127 132 87 172 102 
2 83 102 
28 7
10 28 58 45 17 140 75 170...

result:

ok Answer correct. (500 test cases)

Test #10:

score: 0
Accepted
time: 27ms
memory: 6976kb

input:

2197
10 91
7 3
7 9
9 2
1 10
7 1
6 8
4 8
2 10
7 6
5 3
4 10
9 3
1 4
2 9
5 4
5 6
3 7
6 1
1 9
2 6
3 4
6 9
8 7
6 7
7 4
8 7
9 3
10 7
10 6
2 5
2 7
8 10
10 1
7 4
10 4
9 2
7 6
3 10
6 4
1 8
8 9
6 7
10 9
3 2
2 5
10 5
4 7
5 3
9 4
1 5
1 4
8 4
4 10
7 3
6 7
4 2
3 4
9 2
1 10
6 1
8 3
2 9
9 10
9 5
3 4
5 8
9 3
7 1
6 1...

output:

2 4
6 2 9 7 6 8 4 
3 2 10 4 
4 2 6 7 4 
3 2 7 4 
3 2 9 4 
5 2 3 5 1 4 
2 2 4 
2 2 4 
5 2 10 5 6 4 
2 2 4 
2 2 4 
4 7
3 4 2 7 
3 4 2 7 
3 4 2 7 
2 4 7 
4 4 8 2 7 
3 4 9 7 
4 4 5 8 7 
4 4 8 1 7 
3 4 2 7 
2 4 7 
2 4 7 
2 5
3 2 8 5 
6 2 6 7 1 9 5 
3 2 6 5 
3 2 6 5 
3 2 1 5 
5 2 1 7 8 5 
5 2 4 9 3 5 
5 2...

result:

ok Answer correct. (2197 test cases)

Test #11:

score: 0
Accepted
time: 39ms
memory: 6164kb

input:

1980
5 101
3 5
4 2
5 1
1 4
2 5
1 3
2 5
3 2
4 2
3 1
1 2
5 3
3 4
3 1
1 3
5 3
1 4
2 4
2 3
4 2
4 5
4 5
1 2
3 1
3 4
1 2
3 5
4 1
2 4
3 5
4 3
4 1
2 1
2 1
5 4
5 3
3 5
2 5
4 1
5 3
2 3
3 4
3 4
5 2
3 2
4 3
2 3
4 3
1 5
2 1
1 3
1 4
1 4
2 5
2 1
1 3
3 5
5 3
1 5
3 4
4 2
3 5
4 2
2 4
4 1
3 5
3 5
5 4
1 4
5 3
5 1
5 3
1...

output:

1 3
3 1 5 3 
2 1 3 
2 1 3 
2 1 3 
2 1 3 
2 1 3 
4 1 4 5 3 
3 1 4 3 
4 1 2 5 3 
3 1 2 3 
3 1 5 3 
3 1 2 3 
2 1 3 
3 1 4 3 
2 1 3 
3 1 4 3 
4 1 4 5 3 
3 1 5 3 
3 1 4 3 
3 1 5 3 
2 1 3 
4 1 2 5 3 
2 1 3 
2 1 3 
2 1 3 
2 1 3 
2 4
4 2 1 3 4 
3 2 3 4 
3 2 3 4 
4 2 5 1 4 
2 2 4 
2 2 4 
4 2 3 1 4 
3 2 5 4 
...

result:

ok Answer correct. (1980 test cases)

Test #12:

score: -100
Runtime Error

input:

1
100000 200000
34863 14128
21925 31963
32836 60679
64214 73508
66150 45252
9601 33518
33904 58681
94179 37263
91962 58845
44150 57595
75389 55087
95549 80645
35339 82663
93639 89411
91288 79966
6158 91046
34153 16675
38098 20451
49822 20670
34821 40807
67167 98424
75186 55129
47388 80048
47576 3327...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-05 04:56:54 | OpenSource Project