QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#491126#8757. 图peterTL 48ms7980kbC++141.8kb2024-07-25 17:18:262024-07-25 17:18:29

Judging History

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

  • [2024-07-25 17:18:29]
  • 评测
  • 测评结果:TL
  • 用时:48ms
  • 内存:7980kb
  • [2024-07-25 17:18:26]
  • 提交

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

result: