QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491546#8757. 图weiguoliangWA 30ms9764kbC++141.8kb2024-07-25 20:10:362024-07-25 20:10:37

Judging History

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

  • [2024-07-25 20:10:37]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:9764kb
  • [2024-07-25 20:10:36]
  • 提交

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";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 30ms
memory: 9712kb

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:

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 
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 
1 2
2 1 2 
2...

result:

ok Answer correct. (10000 test cases)

Test #2:

score: -100
Wrong Answer
time: 23ms
memory: 9764kb

input:

10000
5 20
2 1
2 5
5 3
3 1
4 5
1 4
4 3
4 5
3 5
5 4
2 3
5 2
3 4
3 5
1 4
4 3
4 2
2 1
1 3
5 1
5 20
4 2
1 3
1 2
4 5
2 4
3 1
5 3
5 1
4 5
4 3
2 4
1 4
4 3
5 2
1 2
3 5
1 5
4 1
3 4
4 3
5 20
1 4
1 3
1 5
5 1
4 5
3 4
4 5
2 3
1 2
2 4
4 5
4 5
2 4
2 5
4 2
4 3
4 2
2 5
2 1
3 1
5 20
2 5
2 3
4 5
4 2
3 4
2 1
5 4
2 5
2 ...

output:

1 5
3 1 2 5 
3 1 4 5 
4 1 4 3 5 
4 1 2 4 5 
3 1 3 5 
1 5
4 1 2 4 5 
3 1 3 5 
2 1 5 
3 1 2 5 
2 1 5 
2 5
4 2 3 1 5 
3 2 1 5 
3 2 4 5 
3 2 4 5 
2 2 5 
1 2
2 1 2 
2 1 2 
4 1 3 5 2 
4 1 3 4 2 
2 1 2 
1 2
4 1 5 3 2 
4 1 5 3 2 
3 1 3 2 
3 1 4 2 
4 1 5 3 2 
1 5
3 1 4 5 
2 1 5 
2 1 5 
2 1 5 
4 1 3 2 5 
2 3
...

result:

FAIL End in t. (test case 13)