QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#491533#8757. 图lefyWA 72ms96988kbC++141.7kb2024-07-25 20:07:032024-07-25 20:07:03

Judging History

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

  • [2024-07-25 20:07:03]
  • 评测
  • 测评结果:WA
  • 用时:72ms
  • 内存:96988kb
  • [2024-07-25 20:07:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10;
int n;
struct node{
    vector<int>e[N];
    int fa[N];
    int find(int x){
        if(x==fa[x])return x;
        return fa[x]=find(fa[x]);
    }
    void init(){
        for(int i=1;i<=n;i++)fa[i]=i,e[i].clear();
    }
    int pd(int x,int y){
        x=find(x);y=find(y);
        if(x^y)return 1;
        return 0;
    }
    void merge(int x,int y){
        if(!pd(x,y))return;
        e[x].push_back(y);e[y].push_back(x);
        fa[find(x)]=find(y);
    }
    int las[N];
    void dfs(int x,int f){
        las[x]=f;
        for(int v:e[x])if(v^f)dfs(v,x);
    }
};
vector<node>T;
void solve(){
    int m;scanf("%d%d",&n,&m);
    T.resize(m/(n-1)+10);
    int tot=1;
    T[tot].init();
    for(int i=1;i<=m;i++){
        int x,y;scanf("%d%d",&x,&y);
        int l=1,r=tot,p=tot+1;
        while(l<=r){
            int mid=l+r>>1;
            if(T[mid].pd(x,y))p=mid,r=mid-1;
            else l=mid+1;
        }
        if(p<=tot)T[p].merge(x,y);
        else tot++,T[tot].init(),T[tot].merge(x,y);
    }
    if(tot!=ceil(1.0*m/(n-1)))printf("-1\n");
    else{
        int x,y;
        for(int i=1;i<=n;i++)if(T[tot].e[i].size()){
            x=i,y=T[tot].e[i].back();
        }
        printf("%d %d\n",x,y);
        for(int i=1;i<=tot;i++){
            T[i].dfs(y,0);
            vector<int>ans;for(int t=x;t!=y;t=T[i].las[t])ans.push_back(t);
            ans.push_back(y);
            printf("%d ",(int)ans.size());
            for(int t:ans)printf("%d ",t);
            printf("\n");
        }
    }
}
int main(){
    int t;scanf("%d",&t);
    while(t--)solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 72ms
memory: 96988kb

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

result:

ok Answer correct. (10000 test cases)

Test #2:

score: -100
Wrong Answer
time: 26ms
memory: 49948kb

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
-1
-1
-1
5 1
2 5 1 
2 5 1 
2 5 1 
2 5 1 
2 5 1 
-1
-1
-1
5 1
3 5 3 1 
2 5 1 
3 5 3 1 
2 5 1 
2 5 1 
-1
-1
-1
-1
-1
-1
5 1
2 5 1 
3 5 4 1 
2 5 1 
4 5 2 4 1 
2 5 1 
-1
-1
-1
5 3
2 5 3 
4 5 4 1 3 
3 5 4 3 
3 5 4 3 
2 5 3 
-1
-1
-1
-1
-1
-1
-1
-1
5 3
4 5 1 2 3 
2 5 3 
2 5 3 
2 5 3 
2 5 3 
5 3
4 5 4 1...

result:

wrong answer Integer -1 violates the range [1, 5] (test case 1)