QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#777938#8757. 图hotdogsellerTL 0ms0kbC++142.4kb2024-11-24 11:27:342024-11-24 11:27:35

Judging History

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

  • [2024-11-24 11:27:35]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-11-24 11:27:34]
  • 提交

answer

#include<bits/stdc++.h>

#define INF 1e18
#define int long long
#define maxn 100005

using namespace std;

inline int read(){
	int lre=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		lre=(lre<<3)+(lre<<1)+(c-'0');
		c=getchar();
	}
	return lre*f;
} 

struct edge{
	int to;
	int val;
	int next;
}e[4*maxn];

int e_cnt=1,head[maxn];

int add(int u,int v,int w){
	e[e_cnt].to=v;
	e[e_cnt].val=w;
	e[e_cnt].next=head[u];
	head[u]=e_cnt++;
}

int n,m;
//vector<vector<int> > root;
int cnt=0;
map<int,map<int,int> > root;

bool okay=false;
bool visited[maxn];
vector<int> ans;//遍历路径 

int f_f(int x,int y){
	if(root[y][x]==0)root[y][x]=x;
	if(root[y][x]!=x){
		root[y][x]=f_f(root[y][x],y);
	}
	return root[y][x];
}

void merge(int u,int v,int y){
	if(root[y][u]==0)root[y][u]=u;
	if(root[y][v]==0)root[y][v]=v;
	root[y][f_f(u,y)]=f_f(v,y);
}

void dfs(int x,int color,int goal){
//	cout<<"x="<<x<<endl;
	visited[x]=true;
	ans.push_back(x);
	if(x==goal){
		okay=true;
		printf("%lld ",ans.size());
		for(int i=0;i<ans.size();++i){
			printf("%lld ",ans[i]);
		}
		putchar('\n');
	}else{
		for(int i=head[x];i;i=e[i].next){
			int v=e[i].to,w=e[i].val;
			if(w!=color)continue;
			if(visited[v])continue;
			dfs(v,color,goal);
			if(okay)break;
		}
	}
	visited[x]=false;
	ans.pop_back();
}

void solve(){
	e_cnt=1;root.clear();cnt=0;
	n=read();m=read();
	for(int i=0;i<=n;i++){
		head[i]=0;visited[i]=false;
	}
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		if(cnt==0){
			cnt++;
			merge(u,v,cnt);
			add(u,v,cnt);add(v,u,cnt); 
		}else if(f_f(u,cnt)==f_f(v,cnt)){
			cnt++;
			merge(u,v,cnt);
			add(u,v,cnt);add(v,u,cnt); 
		}else{
			int l=1,r=cnt,mid,ind;
			while(l<=r){
				mid=l+r>>1;
				if(f_f(u,mid)==f_f(v,mid)){
					l=mid+1;
				}else{
					ind=mid;
					r=mid-1;
				}
			}
		//	cout<<"merge in "<<ind<<endl;
			merge(u,v,ind);
			add(u,v,ind);add(v,u,ind);
		}
	}
	int x,y;
	for(int i=1;i<=n;i++){
		x=f_f(i,cnt);
		if(x!=i){
			y=x;x=i;
			break;
		}
	}
	swap(x,y);
	printf("%lld %lld\n",x,y);
	int k=(n+m-2)/(n-1);
	if(cnt<k)printf("-1\n");
	else{
		for(int i=1;i<=k;i++){
			okay=false;
			dfs(x,i,y);
		}	
	}
}

signed main(){
	
	int t=read();
	while(t--){
		solve();
	}
	return 0;
}
/*
1
100000 1
55772 64101
*/

详细

Test #1:

score: 0
Time Limit Exceeded

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:


result: