TLE 50 pts
查看原帖
TLE 50 pts
728459
HeYilin楼主2023/11/21 12:32

已 AC ,但是是开 O2 过的,不开的话是 TLE #6-#10,50pts,麻烦看一下代码还有哪有问题

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const ll maxn=2e6+10;
ll n,m,father[maxn],ans,p[maxn],top;
map<ll,ll>s;
ll find(ll x){
	if(father[x]!=x)return father[x]=find(father[x]);
	return father[x];
}
void unionn(ll x,ll y){
	x=find(x);
	y=find(y);
	if(x!=y)father[y]=x;
}
bool jug(ll x,ll y){
	x=find(x);
	y=find(y);
	return x==y;
}
struct node{
	ll u,v,w;
}e[maxn];
bool cmp(node x,node y){
	return x.w>y.w;
}
void kruskal(){
	for(ll i=1;i<=m;i++){
		if(e[i].u==e[i].v)continue;
		if(!jug(e[i].u,e[i].v)){
			unionn(e[i].u,e[i].v);
			ans+=e[i].w;
		}
	}
	return;
}
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>p[i];
		s[p[i]]=++top;
		father[i]=i;
	}
	for(ll i=1;i<=n;i++){
		for(ll j=i+1;j<=n;j++){
			m++;
			e[m].u=s[p[i]],e[m].v=s[p[j]],e[m].w=(p[i]^p[j]);
		}
	}
	sort(e+1,e+1+m,cmp);
	kruskal();
	cout<<ans;
    return 0;
}
/*
4
3
6
9
10

*/
2023/11/21 12:32
加载中...