全RE求助
查看原帖
全RE求助
456455
kisshot楼主2021/7/16 10:28

全部RE,实在找不出来,求助。

#include<bits/stdc++.h>
using namespace std;

#define re register
#define ll long long
#define fo(i,e) for(re ll i=1;i<=e;++i)
#define r0 return 0;
#define e0 exit(0);

inline ll read(){
	ll x=0,f=0;char ch=getchar();
	while(ch>'9'||ch<'0')f|=ch=='-',ch=getchar();
	while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}

void print(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9)print(x/10);
    putchar(x%10+'0');
}

inline ll Max(ll a,ll b){return a>b?a:b;}
inline ll Min(ll a,ll b){return a<b?a:b;}

inline ll power(ll base,ll p){
	ll ans=1,tmp=base;
	while(p!=0){
		if(p&1)ans=(ans*tmp);
		tmp=(tmp*tmp);p=p>>1;
	} 
	return ans;
} 

const int N=200001;
ll n,m,head[N],tot,dep[N],t;
ll f[N],fa[N][41],ww[N][41];
ll v[N]={0};
struct node{
	ll to,next,w;
}e[N],best[N];

inline void add(ll u,ll v,ll w){
	tot++;
	best[tot].next=head[u];
	best[tot].w=w;
	head[u]=tot;
	best[tot].to=v;
}

bool cmp(node a,node b){
	return a.w>b.w;
}

inline ll find(ll x){
	x==f[x]?x:f[x]=find(f[x]);
}

void dfs(ll num){
	v[num]=1;
	for(re ll i=head[num];i;i=best[i].next){
		if(v[best[i].to])continue;
		dep[best[i].to]=dep[num]+1;
		fa[best[i].to][0]=num;
		ww[best[i].to][0]=best[i].w;
		dfs(best[i].to);
	}
	return;
}

inline ll lca(ll x,ll y){
	if(find(x)!=find(y))return -1;
	ll ans=999999999;
	if(dep[x]>dep[y])swap(x,y);
	for(re ll i=20;i>=0;--i){
		if(dep[fa[y][i]]>=dep[x]){
			ans=min(ans,ww[y][i]);
			y=fa[y][i];
		}
	}
	if(x==y)return ans;
	for(re ll i=20;i>=0;--i){
		if(fa[x][i]!=fa[y][i]){
			ans=min(ans,min(ww[x][i],ww[y][i]));
			x=fa[x][i];
			y=fa[y][i];
		}
		ans=min(ans,min(ww[x][0],ww[y][0]));
		return ans;
	}
	
}

int main(){
	n=read();m=read();
	fo(i,m){
		e[i].next=read();
		e[i].to=read();
		e[i].w=read();
	}
	sort(e+1,e+1+m,cmp);
	fo(i,n)f[i]=i;
	fo(i,m){
		if(find(e[i].next)!=find(e[i].to)){
			f[find(e[i].next)]=find(e[i].to);
			add(e[i].next,e[i].to,e[i].w);
			add(e[i].to,e[i].next,e[i].w);
		}
	}
	fo(i,n){
		if(!v[i]){
			dep[i]=1;
			dfs(i);
			fa[i][0]=i;
			ww[i][0]=999999999;
		}
	}
	fo(i,20){
		fo(j,n){
			fa[j][i]=fa[fa[j][i-1]][i-1];
			ww[j][i]=min(ww[j][i-1], ww[fa[j][i-1]][i-1]);
		}
	}
	t=read();
	while(t--){
		ll x=read(),y=read();
		printf("%lld\n",lca(x,y));
	}	
	return 0;
}
2021/7/16 10:28
加载中...