QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604722#8757. 图UESTC_DebugSimulator#WA 75ms14528kbC++172.9kb2024-10-02 13:30:232024-10-02 13:30:25

Judging History

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

  • [2024-10-02 13:30:25]
  • 评测
  • 测评结果:WA
  • 用时:75ms
  • 内存:14528kb
  • [2024-10-02 13:30:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define int long long
int n,m,k,deg[N],d[N],f[N];
int p1,p2;
map<pair<int,int>,int> mp;
struct edge{
	int u,v;
}a[N];
vector<vector<int>> g;
vector<vector<int>> ans;
int vis[N],ch;
int cmp(edge x,edge y)
{
	return x.u<y.u||x.u==y.u&&x.v<y.v;
}
void dfs(int u)
{
	if(ch) return;
	if(u==p2)
	{
		ch=1;
		vector<int> ans1;
		int x=p2;
		while(x!=p1)
		{
			ans1.push_back(x);
			mp[{x,f[x]}]--;
			mp[{f[x],x}]--;
			x=f[x];
		}
		ans1.push_back(p1);
		ans.push_back(ans1);
		return;
	}
	for(auto v:g[u])
	{
		if(vis[v]) continue;
		if(mp[{u,v}]==0) continue;
//		for(int i=1;i<=mp[{u,v}];i++)
		{
			f[v]=u;
			vis[u]=1;
			dfs(v);
			vis[u]=0;
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		g.resize(n+1);
		g.clear();
		mp.clear();
		ans.clear();
		for(int i=1;i<=n;i++)
		{
			d[i]=deg[i]=vis[i]=0;
		}
		if(m%(n-1)==0) k=m/(n-1);
		else k=m/(n-1)+1;
		for(int i=1;i<=m;i++)
		{
			cin>>a[i].u>>a[i].v;
			if(a[i].u>a[i].v) swap(a[i].u,a[i].v);
		}
		if(m==1)
		{
			cout<<a[1].u<<" "<<a[1].v<<"\n";
			cout<<"2 "<<a[1].u<<" "<<a[1].v<<"\n";
			continue;
		}
		sort(a+1,a+m+1,cmp);
		int x1=0,x2=0;
		for(int i=1;i<=m;i++)
		{
			deg[a[i].u]++;deg[a[i].v]++;
			if(a[i].u==a[i-1].u&&a[i].v==a[i-1].v)
			{
				mp[{a[i].u,a[i].v}]++;mp[{a[i].v,a[i].u}]++;
				if(mp[{a[i].u,a[i].v}]>=k)
				{
					x1=a[i].u;
					x2=a[i].v;
				}
				continue;
			}
			g[a[i].u].push_back(a[i].v);
			g[a[i].v].push_back(a[i].u);
			mp[{a[i].u,a[i].v}]=mp[{a[i].v,a[i].u}]=1;
		}
		if(x1)
		{
			cout<<x1<<" "<<x2<<"\n";
			for(int i=1;i<=k;i++)
			{
				cout<<"2 "<<x1<<" "<<x2<<"\n";
			}
			continue;
		}
		queue<int> q;
		for(int i=1;i<=n;i++)
		{
			d[i]=g[i].size();
			if(g[i].size()==1)
			{
				q.push(i);
				continue;
			}
		}
		while(q.size())
		{
			int u=q.front();q.pop();
			vis[u]=1;
			for(auto v:g[u])
			{
				if(vis[v]) continue;
				deg[v]=deg[v]-mp[{u,v}];
				d[v]--;
				if(d[v]==1) q.push(v);
				break;
			}
		}
		int mx=0;
		p1=p2=0;
		for(int i=1;i<=n;i++)
		{
			if(vis[i]) continue;
			if(deg[i]>mx)
			{
				mx=deg[i];
				p1=i;
			}
		}
		mx=0;
		for(int i=1;i<=n;i++)
		{
			if(vis[i]) continue;
			if(deg[i]>mx&&i!=p1)
			{
				mx=deg[i];
				p2=i;
			}
		}
//		cout<<p1<<" "<<p2<<"\n";
//		for(int i=1;i<=n;i++)
//		{
//			for(int j=1;j<=n;j++)
//			{
//				
//				cout<<mp[{i,j}]<<" ";
//			}
//			cout<<"\n";
//		}
		for(int i=1;i<=k;i++)
		{
			ch=0;
			dfs(p1);
		}
		if(ans.size()<k)
		{
			cout<<"-1\n";
			continue;
		}
		cout<<p1<<" "<<p2<<"\n";
		for(int i=0;i<ans.size();i++)
		{
			cout<<ans[i].size();
			for(int j=ans[i].size()-1;j>=0;j--) cout<<" "<<ans[i][j];
			cout<<"\n";
		}
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 35ms
memory: 10380kb

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: 53ms
memory: 11944kb

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

result:

ok Answer correct. (10000 test cases)

Test #3:

score: -100
Wrong Answer
time: 75ms
memory: 14528kb

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

result:

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