QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #593181 | #4996. Icy Itinerary | huaxiamengjin | ML | 14ms | 27400kb | C++14 | 3.3kb | 2024-09-27 12:22:15 | 2024-09-27 12:22:15 |
Judging History
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;
if(m==0){
for (int i=1;i<=n;i++)
cout<<i<<" ";
cout<<"\n";
return 0;
}
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";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 26176kb
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: 3ms
memory: 26124kb
input:
5 0
output:
1 2 3 4 5
result:
ok qwq
Test #3:
score: 0
Accepted
time: 2ms
memory: 26504kb
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: 0ms
memory: 26360kb
input:
2 1 1 2
output:
1 2
result:
ok qwq
Test #5:
score: 0
Accepted
time: 3ms
memory: 26932kb
input:
2 0
output:
1 2
result:
ok qwq
Test #6:
score: 0
Accepted
time: 3ms
memory: 26364kb
input:
3 1 1 3
output:
1 2 3
result:
ok qwq
Test #7:
score: 0
Accepted
time: 3ms
memory: 26092kb
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: 26232kb
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: 0ms
memory: 26144kb
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: 6ms
memory: 26076kb
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: 7ms
memory: 26144kb
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: 3ms
memory: 26252kb
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: 7ms
memory: 27400kb
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: 0
Accepted
time: 14ms
memory: 26472kb
input:
300000 0
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok qwq
Test #15:
score: -100
Memory Limit Exceeded
input:
300000 1 80856 110687