QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#491126 | #8757. 图 | peter | TL | 48ms | 7980kb | C++14 | 1.8kb | 2024-07-25 17:18:26 | 2024-07-25 17:18:29 |
Judging History
answer
// Problem: H - 图
// Contest: Virtual Judge - 2024-07-25 杂题选讲 jly
// URL: https://vjudge.net/contest/643391#problem/H
// Memory Limit: 507 MB
// Time Limit: 1000 ms
#include <bits/stdc++.h>
using namespace std;
const int maxn=4e5+5;
struct edge{
int to,nxt;
}e[maxn<<1];
int head[maxn],len,st[maxn],top=0;
vector<vector<int> > fa;
inline void init(int n){
for(int i=1;i<=n;i++) head[i]=-1;
len=0;
}
void add(int u,int v){
e[++len].to=v;
e[len].nxt=head[u];
head[u]=len;
}
int find(int id,int x){
if(fa[id][x]==x) return x;
return fa[id][x]=find(id,fa[id][x]);
}
void dfs(int u,int f,int ed){
st[++top]=u;
if(u==ed) return;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].to;
if(v==f) continue;
dfs(v,u,ed);
if(st[top]==ed) return;
}
top--;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d %d",&n,&m);
int k=(m+n-2)/(n-1);
init(n*k);
fa.resize(k+1);
for(int i=1;i<=k;i++){
fa[i].resize(n+1);
for(int j=1;j<=n;j++) fa[i][j]=j;
}
for(int i=1;i<=m;i++){
int u,v;
scanf("%d %d",&u,&v);
int l=1,r=k,ret=k;
while(l<=r){
int mid=(l+r)>>1;
if(find(mid,u)==find(mid,v)) l=mid+1;
else{
ret=mid;
r=mid-1;
}
}
int fu=find(ret,u),fv=find(ret,v);
if(fu!=fv){
fa[ret][fv]=fu;
add((ret-1)*k+u,(ret-1)*k+v);
add((ret-1)*k+v,(ret-1)*k+u);
}
}
bool flag=0;
for(int i=1;i<=n;i++){
if(find(k,i)!=i){
int u=i,v=find(k,i);
printf("%d %d\n",u,v);
for(int j=1;j<=k;j++){
top=0;
dfs((j-1)*k+u,0,(j-1)*k+v);
printf("%d ",top);
for(int i=1;i<=top;i++) printf("%d ",st[i]-(j-1)*k);
puts("");
}
flag=1;
break;
}
}
if(!flag) puts("-1");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 48ms
memory: 5812kb
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 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 1 2 2 1 2 2...
result:
ok Answer correct. (10000 test cases)
Test #2:
score: 0
Accepted
time: 34ms
memory: 7980kb
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:
3 1 4 3 5 2 1 2 3 1 3 3 4 1 4 3 4 2 1 2 3 1 1 3 2 1 3 2 1 3 3 1 4 3 4 1 2 5 3 3 1 4 3 4 2 4 4 1 3 2 4 4 5 1 2 2 4 2 2 4 2 3 4 5 2 1 5 3 1 2 5 4 1 2 4 5 3 1 3 5 5 1 3 4 2 5 3 1 2 5 1 4 3 1 5 4 3 1 5 4 2 1 4 2 1 4 4 1 5 3 4 2 1 4 2 5 4 1 3 2 4 1 3 2 5 1 3 2 5 1 3 2 3 1 2 ...
result:
ok Answer correct. (10000 test cases)
Test #3:
score: -100
Time Limit Exceeded
input:
10000 10 20 9 4 8 6 2 10 2 9 7 10 4 6 9 4 2 1 4 7 1 5 7 2 4 1 5 9 7 6 8 2 9 4 5 9 9 8 7 3 2 4 10 20 3 8 8 9 8 7 9 2 3 10 9 3 8 1 9 4 8 9 4 7 7 5 5 10 1 3 3 4 3 7 3 8 3 9 1 4 3 6 2 4 10 20 7 6 8 10 3 8 2 8 4 8 4 8 4 6 4 1 1 7 4 6 5 9 5 2 4 7 10 9 6 7 10 5 2 4 4 1 3 2 4 9 10 20 2 1 9 8 7 6 2 10 9 5 4 ...
output:
4 2 400014 4 7 10 8 12 7 4 6 8 10 15 11 5 10 8 12 7 4 6 8 10 15 11 5 10 8 12 7 4 6 8 10 15 11 5 10 8 12 7 4 6 8 10 15 11 5 10 8 12 7 4 6 8 10 15 11 5 10 8 12 7 4 6 8 10 15 11 5 10 8 12 7 4 6 8 10 15 11 5 10 8 12 7 4 6 8 10 15 11 5 10 8 12 7 4 6 8 10 15 11 5 10 8 12 7 4 6 8 10 15 11 5 10 8 12 7 4 6 8...