想知道map为什么会mle qaq
查看原帖
想知道map为什么会mle qaq
1084866
dead000楼主2024/3/24 21:41
#include<bits/stdc++.h>
using namespace std;
map<int,int> m;
int find(int x)
{
	if(m[x]==x) return x;
	m[x]=find(m[x]);
	return m[x];
}
bool cmp(pair<pair<int,int>,int> x,pair<pair<int,int>,int> y)
{
	return x.second>y.second;
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t;cin>>t;
	while(t--){
		int n,flag=1;cin>>n;
		vector<pair<pair<int,int>,int>> v(n+1);
		for(int i=0;i<n;i++){
			cin>>v[i].first.first>>v[i].first.second>>v[i].second;
		}
		sort(v.begin(),v.begin()+n,cmp);
		for(int i=0;i<n;i++){
			int a=v[i].first.first,b=v[i].first.second,op=v[i].second;
			if(op==1){
				if(!m[a]) m[a]=a;
				if(!m[b]) m[b]=b;
				m[find(a)]=m[b];
			}else{
				if(!m[a]) m[a]=a;
				if(!m[b]) m[b]=b;
				if(find(a)==find(b)) cout<<"NO\n",flag=0;
			}
		}
		if(flag) cout<<"YES\n";
		m.clear();
	}
	return 0;
}
2024/3/24 21:41
加载中...