QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#310611 | #4996. Icy Itinerary | lefy | WA | 3ms | 13228kb | C++14 | 1.7kb | 2024-01-21 16:09:33 | 2024-01-21 16:09:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
vector<int>e[N];
int hav(int x,int y){
int p=lower_bound(e[x].begin(),e[x].end(),y)-e[x].begin();
if(p>=e[x].size())return 0;
return e[x][p]==y;
}
int nxt[N],pre[N];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
for(int i=1;i<=n;i++)sort(e[i].begin(),e[i].end());
int now=2,op=hav(1,2);nxt[0]=1;nxt[1]=2;pre[2]=1;
for(int i=3;i<=n;i++){
if(hav(i,i-1)==op){
nxt[i-1]=i,pre[i]=i-1;
now=i;
}else break;
}
//~ cout<<now<<"\n";
for(int i=now+1;i<=n;i++){
int o1=hav(i,now);
if(o1!=op){
o1=hav(i,pre[now]);
if(!pre[now]){
pre[now]=i;nxt[i]=now;
now=i;
}
else if(o1!=op){
now=pre[now];
pre[nxt[now]]=i;nxt[i]=nxt[now];
nxt[now]=i;pre[i]=now;
}else{
nxt[pre[now]]=i;
pre[i]=pre[now];
nxt[i]=now;pre[now]=i;
now=i;
}
}else{
o1=hav(i,nxt[now]);
if(!nxt[now]){
nxt[now]=i;pre[i]=now;
now=i;
}else if(o1==op){
now=nxt[now];
nxt[pre[now]]=i;pre[i]=pre[now];
pre[now]=i;nxt[i]=now;
}else{
pre[nxt[now]]=i;nxt[i]=nxt[now];
nxt[now]=i,pre[i]=now;
now=i;
}
}
}
for(int i=nxt[0];i;i=nxt[i])printf("%d ",i);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 12420kb
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: 12948kb
input:
5 0
output:
1 2 3 4 5
result:
ok qwq
Test #3:
score: 0
Accepted
time: 2ms
memory: 12748kb
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 3 4 5 6 2 8 9 10 7
result:
ok qwq
Test #4:
score: 0
Accepted
time: 0ms
memory: 12784kb
input:
2 1 1 2
output:
1 2
result:
ok qwq
Test #5:
score: 0
Accepted
time: 2ms
memory: 11296kb
input:
2 0
output:
1 2
result:
ok qwq
Test #6:
score: 0
Accepted
time: 0ms
memory: 13228kb
input:
3 1 1 3
output:
1 2 3
result:
ok qwq
Test #7:
score: 0
Accepted
time: 0ms
memory: 13076kb
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 2 3 4 6 7 8 9 5 10
result:
ok qwq
Test #8:
score: 0
Accepted
time: 0ms
memory: 12716kb
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 2 3 4 5 6 7 8 9 10
result:
ok qwq
Test #9:
score: -100
Wrong Answer
time: 2ms
memory: 11888kb
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 3 2
result:
wrong output format Unexpected end of file - int32 expected