QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#310611#4996. Icy ItinerarylefyWA 3ms13228kbC++141.7kb2024-01-21 16:09:332024-01-21 16:09:33

Judging History

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

  • [2024-01-21 16:09:33]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:13228kb
  • [2024-01-21 16:09:33]
  • 提交

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