QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#491533 | #8757. 图 | lefy | WA | 72ms | 96988kb | C++14 | 1.7kb | 2024-07-25 20:07:03 | 2024-07-25 20:07:03 |
Judging History
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)