QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#491690 | #8757. 图 | lefy | RE | 43ms | 10920kb | C++14 | 1.6kb | 2024-07-25 21:04:01 | 2024-07-25 21:04:01 |
Judging History
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 ...