QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#310604#4996. Icy ItinerarylefyWA 3ms13128kbC++141.5kb2024-01-21 16:02:552024-01-21 16:02:55

Judging History

你现在查看的是最新测评结果

  • [2024-01-21 16:02:55]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:13128kb
  • [2024-01-21 16:02:55]
  • 提交

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