QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#491690#8757. 图lefyRE 43ms10920kbC++141.6kb2024-07-25 21:04:012024-07-25 21:04:01

Judging History

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

  • [2024-07-25 21:04:01]
  • 评测
  • 测评结果:RE
  • 用时:43ms
  • 内存:10920kb
  • [2024-07-25 21:04:01]
  • 提交

answer

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

详细

Test #1:

score: 100
Accepted
time: 43ms
memory: 10920kb

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

result:

ok Answer correct. (10000 test cases)

Test #2:

score: -100
Runtime Error

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

result: