QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#310604 | #4996. Icy Itinerary | lefy | WA | 3ms | 13128kb | C++14 | 1.5kb | 2024-01-21 16:02:55 | 2024-01-21 16:02:55 |
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;
}
for(int i=now+1;i<=n;i++){
int o1=hav(i,now);
if(o1!=op){
o1=hav(i,pre[now]);
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(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: 0ms
memory: 13128kb
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: 11684kb
input:
5 0
output:
1 2 3 4 5
result:
ok qwq
Test #3:
score: -100
Wrong Answer
time: 3ms
memory: 12996kb
input:
10 10 7 8 7 5 5 2 6 1 10 7 4 6 5 8 3 2 10 5 1 10
output:
8 9 10 7
result:
wrong output format Unexpected end of file - int32 expected