QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#491577#8757. 图weiguoliangWA 29ms9780kbC++141.8kb2024-07-25 20:18:092024-07-25 20:18:09

Judging History

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

  • [2024-07-25 20:18:09]
  • 评测
  • 测评结果:WA
  • 用时:29ms
  • 内存:9780kb
  • [2024-07-25 20:18:09]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define N 800005
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<min(N*2ll,max(m*10,n*10));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;
                // if(u>v)swap(u,v);
                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: 29ms
memory: 9780kb

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)