QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #593169 | #4996. Icy Itinerary | huaxiamengjin | WA | 3ms | 27028kb | C++14 | 3.1kb | 2024-09-27 12:17:12 | 2024-09-27 12:17:13 |
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;
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);
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(x);
ans.push_back(zong.back());
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];
}}
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";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 27028kb
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: 26796kb
input:
5 0
output:
1 2 3 4 5
result:
ok qwq
Test #3:
score: 0
Accepted
time: 0ms
memory: 26328kb
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: 26140kb
input:
2 1 1 2
output:
1 2
result:
ok qwq
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 26132kb
input:
2 0
output:
2 1
result:
wrong answer The first number wasn't 1