QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#490750#8757. 图yhdddRE 38ms20924kbC++141.8kb2024-07-25 16:20:432024-07-25 16:20:44

Judging History

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

  • [2024-07-25 16:20:44]
  • 评测
  • 测评结果：RE
  • 用时：38ms
  • 内存：20924kb
查看
  • [2024-07-25 16:20:43]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
using namespace std;
const int maxn=200010;
const int inf=1e18;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
	return x*f;
}
bool Mbe;

int n,m;
vector<int> f[maxn];
int fd(int id,int x){
	if(f[id][x]==x)return x;
	return f[id][x]=fd(id,f[id][x]);
}
vector<int> id[maxn];int idx,val[maxn];
vector<int> e[maxn];
int st[maxn],tp;
void dfs(int u,int fa,int ed){
	st[++tp]=val[u];
	if(st[tp]==ed)return ;
	for(int v:e[u])if(v!=fa){
		dfs(v,u,ed);
		if(st[tp]==ed)return ;
	}
	tp--;
}
void work(){
	n=read();m=read();idx=0;
	int k=(m+n-2)/(n-1);
	for(int i=1;i<=k;i++){
		f[i].resize(n+1);id[i].resize(n+1);
		for(int j=1;j<=n;j++)f[i][j]=j,val[id[i][j]=++idx]=j,e[idx].clear();
	}
	while(m--){
		int u=read(),v=read();
		int l=1,r=k,res=k+1;
		while(l<=r){
			int mid=l+r>>1;
			if(fd(mid,u)!=fd(mid,v))r=mid-1,res=mid;
			else l=mid+1;
		}
		if(res<=k){
			f[res][fd(res,u)]=fd(res,v);
			e[id[res][u]].push_back(id[res][v]),e[id[res][v]].push_back(id[res][u]);
		}
	}
	for(int i=1;i<=n;i++)if(fd(k,i)!=i){
		int u=i,v=fd(k,i);
		printf("%lld %lld\n",u,v);
		for(int j=1;j<=k;j++){
			tp=0;dfs(id[j][u],0,v);
			printf("%lld ",tp);
			for(int l=1;l<=tp;l++)printf("%lld ",st[l]);printf("\n");
		}
		return ;
	}
	puts("-1");
}

// \
444

bool Med;
int T;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	
//	cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
	
	T=read();
	while(T--)work();
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 38ms
memory: 19896kb

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: 23ms
memory: 20580kb

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 5
3 1 2 5 
3 1 4 5 
4 1 4 3 5 
4 1 2 4 5 
3 1 3 5 
1 5
4 1 2 4 5 
3 1 3 5 
2 1 5 
3 1 2 5 
2 1 5 
2 5
4 2 3 1 5 
3 2 1 5 
3 2 4 5 
3 2 4 5 
2 2 5 
1 2
2 1 2 
2 1 2 
4 1 3 5 2 
4 1 3 4 2 
2 1 2 
2 1
4 2 3 5 1 
4 2 3 5 1 
3 2 3 1 
3 2 4 1 
4 2 3 5 1 
1 5
3 1 4 5 
2 1 5 
2 1 5 
2 1 5 
4 1 3 2 5 
3 2
...

result:

ok Answer correct. (10000 test cases)

Test #3:

score: 0
Accepted
time: 21ms
memory: 19392kb

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 8
5 2 9 4 6 8 
2 2 8 
4 2 4 9 8 
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 
4 2
6 4 3 9 5 1 2 
2 4 2 
3 4 10 2 
2 10
4 2 7 4 10 
2 2 10 
3 2 3 10 
1 3
3 1 7 3 
3 1 10 3 
4 1 8 6 3 
3 9
2 3 9 
2 3 9 
3 3 4 9 
1 10
2 1 10 
3 1 5 10 
2 1 10 
7 8
3 7 5 8 
2 7 8 
2 7 8 
4 9
7 4 6 10 1 8 ...

result:

ok Answer correct. (10000 test cases)

Test #4:

score: 0
Accepted
time: 8ms
memory: 19460kb

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:

2 15
8 2 17 31 33 3 28 44 15 
2 2 15 
7 10
6 7 36 24 9 37 10 
2 7 10 
15 24
9 15 34 5 8 1 10 36 14 24 
2 15 24 
4 19
17 4 10 31 1 47 24 36 28 22 3 13 21 26 42 14 49 19 
2 4 19 
20 11
4 20 47 35 11 
2 20 11 
1 45
11 1 24 3 31 12 41 22 9 30 19 45 
2 1 45 
1 13
3 1 2 13 
2 1 13 
18 19
7 18 46 42 36 26 ...

result:

ok Answer correct. (2000 test cases)

Test #5:

score: 0
Accepted
time: 26ms
memory: 20552kb

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:

2 9
10 2 31 16 30 15 22 27 6 33 9 
12 2 8 36 47 1 27 6 24 23 11 35 9 
6 2 44 15 46 36 9 
12 2 37 23 3 36 13 7 24 22 25 34 9 
4 2 37 49 9 
7 2 44 42 37 14 35 9 
6 2 44 41 15 32 9 
8 2 42 21 10 39 28 14 9 
6 2 1 42 10 41 9 
7 2 44 5 11 41 22 9 
13 2 5 20 1 33 24 35 21 28 32 10 22 9 
10 2 16 29 40 8 20...

result:

ok Answer correct. (200 test cases)

Test #6:

score: 0
Accepted
time: 30ms
memory: 20924kb

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:

5 6
14 5 84 77 63 76 14 62 42 89 20 99 48 91 6 
7 5 64 41 87 60 67 6 
12 5 66 96 91 72 46 98 31 76 94 69 6 
12 5 73 39 68 71 72 98 36 63 65 74 6 
11 5 47 17 76 20 42 26 78 33 95 6 
12 5 18 96 29 27 76 14 57 62 71 91 6 
12 5 31 65 86 15 10 13 43 99 88 80 6 
9 5 41 77 43 46 1 49 40 6 
14 5 29 36 98 30...

result:

ok Answer correct. (20 test cases)

Test #7:

score: 0
Accepted
time: 17ms
memory: 20004kb

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:

2 50
7 2 316 806 355 20 721 50 
52 2 361 111 758 966 773 539 479 541 257 684 483 185 866 910 515 571 724 450 216 614 552 757 26 902 429 57 716 598 876 90 315 972 546 312 703 756 968 278 313 999 820 569 89 357 407 67 453 937 517 532 50 
2 2 50 
1 945
10 1 411 850 668 346 821 513 813 746 945 
27 1 258...

result:

ok Answer correct. (100 test cases)

Test #8:

score: 0
Accepted
time: 7ms
memory: 19976kb

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: 18ms
memory: 19492kb

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:

11 27
4 11 16 23 27 
20 11 144 37 192 106 17 20 160 157 14 114 161 44 2 26 64 167 164 10 27 
2 11 27 
2 71
25 2 97 105 127 43 95 139 100 3 185 98 121 173 191 167 120 4 31 124 57 33 64 128 10 71 
26 2 13 197 67 100 177 159 138 24 27 25 162 83 88 176 50 89 78 161 127 142 125 147 133 193 71 
2 2 71 
8 ...

result:

ok Answer correct. (500 test cases)

Test #10:

score: 0
Accepted
time: 21ms
memory: 19452kb

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

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 05:07:39 | OpenSource Project