QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#310824 | #4996. Icy Itinerary | OFforest_1273 | WA | 2ms | 13140kb | C++14 | 1.5kb | 2024-01-21 18:34:39 | 2024-01-21 18:34:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
inline int read(){int s=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+(c^48),c=getchar();return s*f;}
const int N=3e5+10;
int n,m,p1[N]/*有边的前一段*/,p0[N]/*没边的后一段*/,c1,c0;
vector<int> G[N];
int main(){
n=read(),m=read();
for(int i=1;i<=m;++i){
int u=read(),v=read();
G[u].push_back(v),G[v].push_back(u);
}
for(int i=1;i<=n;++i)sort(G[i].begin(),G[i].end());/*方便二分*/
for(int i=n;i;--i/*先将两个p数组反着来 方便添加点*/){
if(!c1){p1[++c1]=i;continue;}/*第一个必须是1*/
if(!c0){p0[++c0]=i;continue;}
int u0=p0[c0],u1=p1[c1];
int pos=lower_bound(G[u1].begin(),G[u1].end(),i)-G[u1].begin();
if(pos<G[u1].size()&&G[u1][pos]==i){p1[++c1]=i;continue;}
pos=lower_bound(G[u0].begin(),G[u0].end(),i)-G[u0].begin();
if(pos>=G[u0].size()||(pos<G[u0].size()&&G[u0][pos]!=i)){p0[++c0]=i;continue;}
pos=lower_bound(G[u1].begin(),G[u1].end(),u0)-G[u1].begin();
cout<<i<<" "<<pos<<" "<<G[u0].size()<<" "<<c1<<" "<<c0<<"\n";
if(pos<G[u1].size()&&G[u1][pos]==u0)--c0,p1[++c1]=u0,p1[++c1]=i;/*用u0将u1和i连接起来*/
else --c1,p0[++c0]=u1,p0[++c0]=i;/*将u0和i隔开*/
}
reverse(p1+1,p1+1+c1),reverse(p0+1,p0+1+c0);
if(p0[1]==1)swap(p0,p1),swap(c0,c1);
for(int i=1;i<=c1;++i)printf("%d ",p1[i]);
for(int i=1;i<=c0;++i)printf("%d ",p0[i]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 11712kb
input:
4 4 1 2 1 3 1 4 3 4
output:
1 4 2 3
result:
ok qwq
Test #2:
score: 0
Accepted
time: 0ms
memory: 13140kb
input:
5 0
output:
1 2 3 4 5
result:
ok qwq
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 12608kb
input:
10 10 7 8 7 5 5 2 6 1 10 7 4 6 5 8 3 2 10 5 1 10
output:
4 1 2 3 3 2 0 1 2 6 1 10 2 7 3 4 5 6 8 9
result:
wrong answer Integer 0 violates the range [1, 10]