QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#165446#6560. Broken Minimum Spanning TreePhantomThreshold#WA 2ms3848kbC++201.3kb2023-09-05 18:14:322023-09-05 18:14:33

Judging History

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

  • [2023-09-05 18:14:33]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3848kb
  • [2023-09-05 18:14:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	vector<tuple<int,int,int,int>> edges;
	vector<set<tuple<int,int,int>>> G(n+5);
	auto addedge=[&](int u,int v,int w,int id)
	{
		G[u].emplace(v,w,id);
		G[v].emplace(u,w,id);
	};
	auto deledge=[&](int u,int v,int w,int id)
	{
		G[u].erase({v,w,id});
		G[v].erase({u,w,id});
	};
	vector<int> in(m+5);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		edges.emplace_back(w,u,v,i);
		if(i<n)addedge(u,v,w,i),in[i]=1;
	}
	vector<pair<int,int>> ans;
	sort(edges.begin(),edges.end());
	vector<int> vis(n+5),maxx(n+5),maxp(n+5);
	function<void(int)> dfs=[&](int u)
	{
//		cerr<<"dfs "<<u<<endl;
		vis[u]=1;
		for(auto [v,w,id]:G[u])
		{
			if(not vis[v])
			{
				if(maxx[u]<w)maxx[v]=w,maxp[v]=id;
				else maxx[v]=maxx[u],maxp[v]=maxp[u];
				dfs(v);
			}
		}
	};
	for(auto [w,u,v,id]:edges)
	{
		if(in[id])continue;
		fill(vis.begin(),vis.end(),0);
		dfs(u);
//		cerr<<w<<' '<<maxx[v]<<endl;
		if(maxx[v]>w)
		{
			ans.emplace_back(id,maxp[v]);
			auto [ww,uu,vv,ii]=edges[maxp[v]-1];
			deledge(uu,vv,ww,ii);
			addedge(u,v,w,id);
		}
	}
	cout<<ans.size()<<endl;
	for(auto [x,y]:ans)
		cout<<x<<' '<<y<<endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3612kb

input:

4 4
1 2 10
2 3 3
3 4 1
1 4 4

output:

1
4 1

result:

ok correct!

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 3848kb

input:

6 8
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10
1 3 1
4 6 1

output:

2
7 1
8 1

result:

wrong answer bad swap 8 1