QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#593178#4996. Icy ItineraryhuaxiamengjinML 11ms29472kbC++143.2kb2024-09-27 12:20:512024-09-27 12:20:53

Judging History

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

  • [2024-09-27 12:20:53]
  • 评测
  • 测评结果：ML
  • 用时：11ms
  • 内存：29472kb
查看
  • [2024-09-27 12:20:51]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
bool used[300300];
int col[300300];
int fa[300300];
vector<int>g[300300],h[300300],v[300300];
int n,m,tot;
int deg[300300];
priority_queue<pair<int,int> >q;
vector<int>ans;
queue<int>qq;
void dfs(int x,int pa){
	used[x]=1;col[x]=col[pa];fa[x]=pa;
	for (auto y:g[x])if(y!=pa){
		if(used[y]==1);
		else h[x].push_back(y),dfs(y,x);
	}
}
int main(){
	cin>>n>>m;
	for (int i=1,x,y;i<=m;i++)
	cin>>x>>y,g[x].push_back(y),g[y].push_back(x);
	for (int i=1;i<=n;i++)
	if(used[i]==0)col[i]=++tot,dfs(i,i);
	for (int i=1;i<=n;i++)
	v[col[i]].push_back(i);

	for (int i=2;i<=tot;i++)
	if(v[i].size()>=(n+1)/2){
		vector<int>zong;
		for (int j=1;j<=tot;j++)
		if(j!=i)for (auto k:v[j])
		zong.push_back(k);
		reverse(zong.begin(),zong.end());
		for(int j=1;j<=n;j++)
		if(col[j]==i){
			deg[j]=h[j].size();
			if(!deg[j])qq.push(j);
		}
		while(qq.size()&&v[i].size()){
			int x=qq.front();qq.pop();
			ans.push_back(zong.back());
			ans.push_back(x);
			zong.pop_back();
			deg[fa[x]]--;
			if(deg[fa[x]]==0)qq.push(fa[x]);
			if(!zong.size())break;
			
		}
		while(qq.size()>1){
			int x=qq.front();qq.pop();
			if(ans.size()&&fa[ans.back()]==x){
				qq.push(x);
				if(qq.size()==1)break;
				else continue; 
			}
			ans.push_back(x);
			deg[fa[x]]--;
			if(deg[fa[x]]==0)qq.push(fa[x]);
		}
		if(qq.size()){
		int x=qq.front();
		while(x!=ans.back()){
			ans.push_back(x);
			x=fa[x];
		}}
//		cout<<i<<"&&&\n";
		for (auto i:ans)
		cout<<i<<" ";cout<<"\n";
		return 0;
	}
	for (int i=2;i<=tot;i++)
	q.push({v[i].size(),i});
	while(q.size()>2){
		int x=q.top().second;q.pop();
		int y=q.top().second;q.pop();
		if(!v[x].size()||!v[y].size())break;
		ans.push_back(v[x].back());
		ans.push_back(v[y].back());
		v[x].pop_back(),v[y].pop_back();
		q.push({v[x].size(),x});
		q.push({v[y].size(),y}); 
	}
	for (int i=2;i<=tot;i++)
	if(v[i].size()){	
		for(int j=1;j<=n;j++)
		if(col[j]==1){
			deg[j]=h[j].size();
			if(!deg[j])qq.push(j);
		}
		while(qq.size()&&v[i].size()){
			int x=qq.front();qq.pop();
			ans.push_back(x);
			ans.push_back(v[i].back());
			v[i].pop_back();
			deg[fa[x]]--;
			if(deg[fa[x]]==0)qq.push(fa[x]);
			if(!v[i].size())break;
			
		}
		while(qq.size()>1){
			int x=qq.front();qq.pop();
			if(ans.size()&&fa[ans.back()]==x){
				qq.push(x);
				if(qq.size()==1)break;
				else continue; 
			}
			ans.push_back(x);
			deg[fa[x]]--;
			if(deg[fa[x]]==0)qq.push(fa[x]);
		}
		int x=qq.front();
		while(x!=1){
			ans.push_back(x);
			x=fa[x];
		}
		ans.push_back(1);
		for (int i=ans.size()-1;~i;i--)
		cout<<ans[i]<<" ";cout<<"\n";
	
		return 0;
	}
	for(int j=1;j<=n;j++)
	if(col[j]==1){
		deg[j]=h[j].size();
		if(!deg[j])qq.push(j);
	}

	while(qq.size()>1){
		int x=qq.front();
//		if(x==1)break;
		qq.pop();
		if(ans.size()&&fa[ans.back()]==x){
			qq.push(x);
			if(qq.size()==1)break;
			else continue; 
		}
		ans.push_back(x);
		deg[fa[x]]--;
		if(deg[fa[x]]==0)qq.push(fa[x]);
	}
	int x=qq.front();
	while(x!=1){
		ans.push_back(x);
		x=fa[x];
	}
	ans.push_back(1);
	for (int i=ans.size()-1;~i;i--)
	cout<<ans[i]<<" ";cout<<"\n";
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 26352kb

input:

4 4
1 2
1 3
1 4
3 4

output:

1 3 4 2

result:

ok qwq

Test #2:

score: 0
Accepted
time: 0ms
memory: 26064kb

input:

5 0

output:

1 2 3 4 5

result:

ok qwq

Test #3:

score: 0
Accepted
time: 6ms
memory: 26572kb

input:

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

output:

1 10 7 8 5 6 2 4 9 3

result:

ok qwq

Test #4:

score: 0
Accepted
time: 3ms
memory: 26100kb

input:

2 1
1 2

output:

1 2

result:

ok qwq

Test #5:

score: 0
Accepted
time: 3ms
memory: 26056kb

input:

2 0

output:

1 2

result:

ok qwq

Test #6:

score: 0
Accepted
time: 3ms
memory: 26404kb

input:

3 1
1 3

output:

1 2 3

result:

ok qwq

Test #7:

score: 0
Accepted
time: 0ms
memory: 26044kb

input:

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

output:

1 8 9 10 5 4 3 7 2 6

result:

ok qwq

Test #8:

score: 0
Accepted
time: 3ms
memory: 26424kb

input:

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

output:

1 5 10 7 2 6 3 4 8 9

result:

ok qwq

Test #9:

score: 0
Accepted
time: 3ms
memory: 26232kb

input:

15 40
12 11
11 6
5 11
15 14
10 14
15 5
1 11
10 12
4 3
6 4
4 9
2 11
6 12
13 7
7 9
10 9
1 2
9 11
2 6
7 14
2 9
3 13
9 1
2 7
8 11
1 10
13 1
4 15
3 7
2 15
6 5
10 15
4 14
15 6
2 4
3 11
1 14
2 8
1 8
10 7

output:

1 11 12 10 14 15 5 6 4 3 13 7 9 2 8

result:

ok qwq

Test #10:

score: 0
Accepted
time: 5ms
memory: 26672kb

input:

15 1
13 6

output:

1 2 3 4 5 6 7 8 9 10 11 12 14 15 13

result:

ok qwq

Test #11:

score: 0
Accepted
time: 0ms
memory: 26928kb

input:

150 150
110 99
80 122
55 67
24 47
73 68
150 13
94 140
146 59
136 28
94 134
131 2
26 105
65 79
57 37
116 102
84 16
110 78
72 5
34 8
8 43
83 57
49 146
43 112
54 139
95 13
11 95
75 29
29 30
52 14
118 56
4 51
18 146
31 113
56 69
44 14
63 123
44 66
101 122
52 10
16 118
71 93
22 113
28 88
5 108
16 48
84 1...

output:

1 141 8 34 108 5 45 41 135 136 28 88 57 37 61 121 69 56 118 16 48 40 129 93 71 96 75 29 30 38 14 52 74 95 79 68 59 146 49 13 66 150 110 119 137 27 53 21 50 63 116 134 10 6 117 80 102 139 22 84 83 94 97 81 43 87 111 122 99 109 55 54 113 78 131 148 144 140 133 128 126 123 120 115 114 112 106 104 101 9...

result:

ok qwq

Test #12:

score: 0
Accepted
time: 6ms
memory: 26400kb

input:

1500 1500
370 639
1046 375
1191 907
782 923
1369 196
998 194
640 331
309 631
1053 1076
887 1112
650 1437
2 1133
847 302
647 81
22 691
772 14
1112 62
266 1399
865 980
1302 1146
1007 575
1448 261
1489 1189
1134 1009
7 1175
1369 942
709 365
675 514
1021 1250
1415 2
976 746
564 388
431 326
43 147
385 81...

output:

1 1278 459 1314 80 260 96 877 271 596 412 544 451 858 1139 453 1490 112 346 204 1078 1208 168 1225 1457 1246 361 1070 1029 1367 1267 531 1132 1451 382 1083 1131 1468 1303 448 10 1133 2 1415 790 1370 759 1116 1194 417 927 1429 273 948 1154 610 499 1444 367 1390 906 1059 932 293 472 1044 1167 148 990 ...

result:

ok qwq

Test #13:

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

input:

15000 15000
11602 9990
5492 14226
2633 14599
7956 12544
1258 1198
13788 3283
171 3770
8226 10782
915 6735
7186 14219
12806 1549
8783 5596
3692 9668
370 4654
13811 4032
835 12990
14273 14020
8902 7798
7405 4524
7476 1864
7786 14984
4367 13552
2927 2463
1929 3198
97 5800
14012 5674
6283 827
13860 1139...

output:

1 12454 8912 763 10890 8114 6698 14603 5262 10877 6872 13145 13284 620 13068 13113 1693 8545 418 14975 8924 837 14071 3745 5073 12146 3905 9260 11283 7229 11719 10431 8688 2213 14509 8426 10961 4614 6899 9636 1472 4306 1549 12806 2814 7182 2271 2973 1986 2884 9279 193 464 8416 7639 1588 12127 10209 ...

result:

ok qwq

Test #14:

score: -100
Memory Limit Exceeded

input:

300000 0

output:

result:
English 繁體中文 简体中文

服务器时间: 2024-12-05 04:50:56 | 开源项目