QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#435628#8757. 图qzezWA 135ms6636kbC++142.1kb2024-06-08 20:54:372024-06-08 20:54:37

Judging History

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

  • [2024-06-08 20:54:37]
  • 评测
  • 测评结果:WA
  • 用时:135ms
  • 内存:6636kb
  • [2024-06-08 20:54:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned ll;
const int N=1e5+10;
int T,n,m,s,t;
vector<int>to[N];
vector<vector<int>>ans;
int fa[N],cnt[N],siz[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void link(int x,int y,int w){
	x=find(x),y=find(y);
	if(x==y)cnt[x]+=w;
	else cnt[y]+=cnt[x]+w,siz[y]+=siz[x],fa[x]=y;
}
vector<int>stk;
bool dfs(int u,int fa=0){
	stk.push_back(u);
	if(u==t)return ans.push_back(stk),1;
	for(int v:to[u])if(v^fa){
		if(dfs(v,u))return 1;
	}
	stk.pop_back();
	return 0;
}
void solve(const vector<tuple<int,int,int>> &E,int k){
	if(k==1){
		auto [u,v,w]=E[0];
		s=u,t=v,ans={{u,v}};
		return;
	}
	iota(fa,fa+1+n,0);
	fill(cnt,cnt+1+n,0);
	fill(siz+1,siz+1+n,1);
	for(auto [u,v,w]:E)link(u,v,w);
	int rt=0,mx=0;
	for(int i=1;i<=n;i++)if(fa[i]==i&&siz[i]>1){
		int val=(cnt[i]-1)/(siz[i]-1)+1;
		if(val>mx)mx=val,rt=i;
	}
	vector<tuple<int,int,int>>ne,ret;
	for(auto [u,v,w]:E){
		if(find(u)==rt)ne.push_back({u,v,w});
	}
	iota(fa,fa+1+n,0);
	vector<pair<int,int>>cur;
	for(auto [u,v,w]:ne){
		int x=find(u),y=find(v);
		if(x!=y){
			fa[x]=y;
			cur.push_back({u,v});
			if(w>1)ret.push_back({u,v,w-1});
		}else ret.push_back({u,v,w});
	}
	solve(ret,k-1);
	for(auto [u,v]:cur){
		to[u].push_back(v),to[v].push_back(u);
	}
	stk.clear(),dfs(s);
	for(int i=1;i<=n;i++)to[i].clear();
}
void get(){
	scanf("%d%d",&n,&m);
	vector<tuple<int,int,int>>E(m);
	for(auto &[u,v,w]:E){
		scanf("%d%d",&u,&v),w=1;
		if(u>v)swap(u,v);
	}
	sort(all(E));
	int len=0;
	for(int i=1;i<E.size();i++){
		auto &[u1,v1,w1]=E[len];
		auto &[u2,v2,w2]=E[i];
		if(u1==u2&&v1==v2)w1++;
		else E[++len]=E[i];
	}
	solve(E,(m-1)/(n-1)+1);
	printf("%d %d\n",s,t);
	for(const auto &x:ans){
		printf("%ld",x.size());
		for(int y:x)printf(" %d",y);
		puts("");
	}
}
int main(){
	for(scanf("%d",&T);T--;)get();
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif

詳細信息

Test #1:

score: 100
Accepted
time: 135ms
memory: 6152kb

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

result:

ok Answer correct. (10000 test cases)

Test #2:

score: 0
Accepted
time: 58ms
memory: 6172kb

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 4
2 3 4
2 3 4
3 3 2 4
3 3 1 4
3 3 1 4
2 4
2 2 4
2 2 4
2 2 4
3 2 1 4
3 2 1 4
2 4
2 2 4
2 2 4
2 2 4
2 2 4
3 2 1 4
3 4
2 3 4
2 3 4
3 3 2 4
4 3 1 2 4
3 3 1 4
1 5
2 1 5
2 1 5
2 1 5
2 1 5
2 1 5
2 5
2 2 5
2 2 5
4 2 4 1 5
4 2 3 1 5
3 2 1 5
3 4
2 3 4
3 3 2 4
3 3 2 4
4 3 1 2 4
3 3 1 4
2 4
2 2 4
2 2 4
2 2 4
...

result:

ok Answer correct. (10000 test cases)

Test #3:

score: -100
Wrong Answer
time: 52ms
memory: 6636kb

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 9
2 4 9
2 4 9
4 4 1 2 9
3 8
2 3 8
2 3 8
3 3 1 8
4 8
2 4 8
2 4 8
3 4 2 8
5 9
2 5 9
2 5 9
4 5 1 2 9
3 10
2 3 10
3 3 2 10
5 3 2 7 1 10
3 10
2 3 10
2 3 10
4 3 2 1 10
4 7
2 4 7
3 4 3 7
3 4 1 7
5 6
2 5 6
2 5 6
6 5 1 2 9 4 6
6 10
2 6 10
5 6 8 5 2 10
4 6 3 2 10
5 9
2 5 9
2 5 9
5 5 8 1 4 9
4 8
2 4 8
2 4 8
...

result:

FAIL No edge cross. (test case 292)