QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#491402#8757. 图liujunyi123WA 36ms3808kbC++171.2kb2024-07-25 19:18:212024-07-25 19:18:22

Judging History

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

  • [2024-07-25 19:18:22]
  • 评测
  • 测评结果:WA
  • 用时:36ms
  • 内存:3808kb
  • [2024-07-25 19:18:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int T,n,m,k;
struct node{int x,y;}e[N];
struct dsu{vector<int> f;vector<vector<int> > g;
	void init(int x){f.resize(x+1),g.resize(x+1);
		for(int i=1;i<=x;i++)f[i]=i;
	}
	int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
	void merge(int x,int y){
		g[x].push_back(y),g[y].push_back(x);
		f[find(y)]=find(x);
	}
	bool dfs(int u,int fa,int rt,int ed,int d){
		if(u==ed){
			printf("%d %d ",d,u);
			return 1;
		}
		for(auto v:g[u])if(v!=fa){
			if(dfs(v,u,rt,ed,d+1)){
				printf("%d ",u);
				return 1;
			}
		}
		return 0;
	}
};
vector<dsu> a;
void solve(){
	scanf("%d%d",&n,&m),k=(m+n-1)/(n-1),a.resize(k);
	for(int i=1;i<=m;i++)scanf("%d%d",&e[i].x,&e[i].y);
	for(int i=0;i<k;i++)a[i].init(n);
	for(int i=1;i<=m;i++){
		int l=0,r=k-1,res=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(a[mid].find(e[i].x)==a[mid].find(e[i].y))l=mid+1;
			else r=mid-1;
		}
		if(l<k)a[l].merge(e[i].x,e[i].y);
	}bool fl=0;
	for(int i=1;i<=n;i++)if(a[k-1].find(i)!=i){
		printf("%d %d\n",a[k-1].find(i),i);
		for(int j=0;j<k;j++)a[j].dfs(i,0,i,a[k-1].find(i),1),puts("");
		fl=1;break ;
	} 
	if(!fl)printf("-1\n");
	a.clear();
}
int main(){
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 36ms
memory: 3808kb

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

result:

wrong answer Integer -1 violates the range [1, 2] (test case 1)