QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#491509 | #8757. 图 | weiguoliang | WA | 28ms | 7724kb | C++14 | 1.8kb | 2024-07-25 20:01:38 | 2024-07-25 20:01:41 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define N 200005
using namespace std;
struct node{
ll t,n;
}edge[N<<2];
ll n,m,ca[N<<1],head[N<<1],u,v,cn=-1,ji[N],cnt=0;
bool p=true;
ll read(){char c=getchar();
ll n=0;
while(c<'0'||c>'9')c=getchar();
while(c<='9'&&c>='0')n=(n<<1)+(n<<3)+c-'0',c=getchar();
return n;
}
void add(ll a,ll b){
edge[++cn]={b,head[a]};
head[a]=cn;
edge[++cn]={a,head[b]};
head[b]=cn;
}
ll found(ll n){
return ca[n]==n?n:ca[n]=found(ca[n]);
}
ll suan(ll k,ll i){
return n*(k-1)+i;
}
void dfs(ll f,ll la,ll j){ll i;
ji[++cnt]=f;
if(f==suan(j,v)){p=false;
cout<<cnt<<' ';
for(i=1;i<=cnt;i++)cout<<ji[i]%n+1<<" ";
cout<<'\n';
return;
}
for(i=head[f];i!=-1;i=edge[i].n){
if(edge[i].t==la)continue;
dfs(edge[i].t,f,j);
if(!p)return;
}
cnt--;
}
int main(){ll t,l,r,mid,k,i,j;
ios::sync_with_stdio(0);
cout.tie(0);
t=read();
while(t--){n=read(),m=read(),k=0,p=true,cn=-1;
while(k*(n-1)<m)k++;
for(i=0;i<=max(m*2,n);i++)ca[i]=i,head[i]=-1;
for(i=1;i<=m;i++){u=read()-1,v=read()-1;
l=1,r=k;
while(l<=r){mid=l+r>>1;
if(found(suan(mid,u))!=found(suan(mid,v)))r=mid-1;
else l=mid+1;
}
ca[found(suan(l,u))]=found(suan(l,v)),add(suan(l,u),suan(l,v));
}
for(i=0;i<n;i++){
if(found(suan(k,i))!=suan(k,i)){u=i,v=found(suan(k,i))%n;
cout<<u+1<<' '<<v+1<<'\n';
for(j=1;j<=k;j++){cnt=0,p=true;
dfs(suan(j,u),0,j);
}
break;
}
}
if(p)cout<<"-1\n";
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 28ms
memory: 7724kb
input:
10000 2 20 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 20 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 20 1 2 2 1 1 2 1 2 2 1 2 1 1 2 1 2 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 20 1 2 2 1 2 1 1 2 1 2 1 2 2 1 1 2 2 ...
output:
2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2...
result:
FAIL End in t. (test case 1)