这玩意为什么会超时???
查看原帖
这玩意为什么会超时???
152338
Accelerator_5楼主2022/12/21 16:23

RT,5—10全部TLE

#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
long long int n;
struct Edge{
	long long int u;
	long long int v;
	long long int w;
	Edge(long long int _u=0,long long int _v=0,long long int _w=0):u(_u),v(_v),w(_w){}
}edge[4000005];
long long int cnt;
void add(long long int u,long long int v,long long int w){
	edge[++cnt]=Edge(u,v,w);
}
bool cmp(Edge i,Edge j){
	return i.w>j.w;
}
long long int fa[4000005];
void init(){
	for(long long int i=1;i<=n;i++){
		fa[i]=i;
	}
}
int getfa(long long int i){
	if(fa[i]==i){
		return i;
	}
	return fa[i]=getfa(fa[i]);
}
void merge(long long int i,long long int j){
	fa[getfa(j)]=getfa(i);
}
long long int ans;
void krulskal(){
	sort(edge+1,edge+cnt+1,cmp);
	for(long long int i=1;i<=cnt;i++){
		int u=edge[i].u,v=edge[i].v;
		if(getfa(u)==getfa(v)){
			continue;
		}
		merge(u,v);
		ans+=edge[i].w;
	}
}
long long int p[4000005];
int main(){
	scanf("%lld",&n);
    init();
    for(long long int i=1;i<=n;i++){
    	scanf("%lld",&p[i]);
	}
	for(long long int i=1;i<=n;i++){
		for(long long int j=1;j<=n;j++){
			add(i,j,p[i]^p[j]);
		}
	}
	krulskal();
	printf("%lld",ans);
    return 0;
}
2022/12/21 16:23
加载中...