QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#75361 | #4996. Icy Itinerary | WJL | WA | 5ms | 15252kb | C++14 | 1.4kb | 2023-02-04 22:01:04 | 2023-02-04 22:01:06 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+3;
int n,m,pre[N],nex[N],fen,vis[N],vis2[N],las;
vector<int>vec[N];
void change(int x,int y,int z){
pre[x]=y;
nex[y]=x;
nex[z]=y;
pre[y]=z;
}
int main(){
scanf("%d%d",&n,&m);
int u,v;
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
vec[u].push_back(v);
vec[v].push_back(u);
}
int flag=0;
if(!vec[1].size())nex[1]=2,pre[2]=1,fen=2,vis2[1]=1,vis2[2]=1,flag=1,las=2;
else pre[vec[1][0]]=1,nex[1]=vec[1][0],fen=vec[1][0],vis2[1]=1,vis2[vec[1][0]]=1,las=fen;
for(int i=1;i<=n;i++){
if(vis2[i])continue;
for(int j=0;j<(int)vec[i].size();j++){
vis[vec[i][j]]=i;
}
if(vis[fen]==i){
if(!flag){
change(nex[fen],i,fen);
if(!nex[i])las=i;
if(vis[nex[i]]==i){
fen=nex[i];
if(fen==0)fen=i;
}
else fen=i;
}
else{
change(fen,i,pre[fen]);
if(!nex[i])las=i;
if(vis[pre[i]]==i)fen=las,flag=0;
else fen=i;
}
}
else{
if(!flag){
change(fen,i,pre[fen]);
if(!nex[i])las=i;
if(vis[pre[i]]==i)fen=i;
else fen=las,flag=1;
}
else{
change(nex[fen],i,fen);
if(!nex[i])las=i;
if(vis[nex[i]]==i)fen=i;
else{
fen=nex[i];
if(fen==0)fen=i;
}
if(!nex[i])las=i;
}
}
// cout<<pre[i]<<" "<<i<<" "<<nex[i]<<" "<<fen<<endl;
}
int x=1;
while(x!=0){
printf("%d ",x);
x=nex[x];
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 5ms
memory: 13980kb
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: 12984kb
input:
5 0
output:
1 2 3 4 5
result:
ok qwq
Test #3:
score: 0
Accepted
time: 1ms
memory: 13624kb
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 2 6 3 4 8 9 10 7 5
result:
ok qwq
Test #4:
score: 0
Accepted
time: 4ms
memory: 14628kb
input:
2 1 1 2
output:
1 2
result:
ok qwq
Test #5:
score: 0
Accepted
time: 1ms
memory: 13368kb
input:
2 0
output:
1 2
result:
ok qwq
Test #6:
score: 0
Accepted
time: 2ms
memory: 14028kb
input:
3 1 1 3
output:
1 2 3
result:
ok qwq
Test #7:
score: 0
Accepted
time: 1ms
memory: 14436kb
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 2 3 4 6 7 5 9 10
result:
ok qwq
Test #8:
score: 0
Accepted
time: 2ms
memory: 15076kb
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 2 3 4 6 7 8 9 10
result:
ok qwq
Test #9:
score: -100
Wrong Answer
time: 4ms
memory: 15252kb
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 3 4 5 6 2 9 10 13 12 8 15 14 7
result:
wrong answer Changed color too many times (4)