80pts WAon#2#14#16#17求调
查看原帖
80pts WAon#2#14#16#17求调
1010629
qwqSW楼主2024/8/5 11:08

#14#16#17都显示"read 0,expected "-"" 没见过这种的
#2 是read "-" expected 2
蒟蒻不懂求助

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int M=5e5+5;
const int N=1e5+5;
int n,m,k,h[N+M],tot,fa[N+M],doc,f[28][N+M],dep[N+M],quan[N+M],hh[N+M],totot,vis[N+M];
struct sw{
	int u,v,w,nxt;
}e[2*M],ee[4*M];
void add(int u,int v,int w){
	tot++;
	e[tot].u=u;
	e[tot].v=v;
	e[tot].w=w;
	e[tot].nxt=h[u];
	h[u]=tot;
}
void addd(int u,int v,int w){
	//cout<<u<<"-->>"<<v<<endl;
	totot++;
	ee[totot].u=u;
	ee[totot].v=v;
	ee[totot].w=w;
	ee[totot].nxt=hh[u];
	hh[u]=totot;
}
bool cmp(sw a,sw b){
	return a.w>b.w;
}
int Find(int x){
	return (fa[x]==x?x:Find(fa[x]));
}
void dfs(int u,int fath){
	f[0][u]=fath;
	//cout<<"u="<<u<<" fa="<<fath<<endl;
	//cout<<u<<"->"<<fath<<endl;
	//for(int i=1;i<=n;i++){
	//	cout<<"i="<<i<<" fa[i]="<<fa[i]<<" ";
	//}
	//cout<<endl;
	vis[u]=1;
	//for(int i=1;i<=n;i++) cout<<dep[i]<<" ";
	//cout<<endl;
	for(int i=hh[u];i;i=ee[i].nxt){
		int v=ee[i].v;
		if(v==fath) continue;
		//cout<<"v="<<v<<endl;
		dep[v]=dep[u]+1;
		dfs(v,u); 
	}
	//cout<<u<<"->";
	//for(int i=hh[u];i;i=ee[i].nxt){
		//int v=ee[i].v;
		//if(v==fath) continue;
		//cout<<v<<" ";
	//}
	//cout<<endl;
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=28;i>=0;i--){
		if(dep[f[i][x]]>=dep[y]){
			x=f[i][x];
		}
		//cout<<"i="<<i<<" x="<<x<<endl;
	}
	if(x==y) return x;
	for(int i=28;i>=0;i--){
		if(f[i][x]!=f[i][y]){
			x=f[i][x];y=f[i][y];
		}
		//cout<<"x="<<x<<" y="<<y<<endl;
	}
	return f[0][x];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	sort(e+1,e+tot+1,cmp);
	for(int i=1;i<=tot;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		int fu=Find(u),fv=Find(v);
		if(fu==fv) continue;
		n++;
		fa[fu]=fa[fv]=fa[n]=n;
		addd(n,fu,w);addd(fu,n,w);
		addd(n,fv,w);addd(fv,n,w);
		quan[n]=w;
	}
	//cout<<"--------doc="<<n<<"--------"<<endl;
	for(int i=1;i<=n;i++){
		if(fa[i]!=i) continue;
		dep[i]=1;
		dfs(i,0);
	}
	for(int i=1;i<=28;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=f[i-1][f[i-1][j]];
		}
	}
	//for(int i=0;i<=28;i++){
	//	for(int j=1;j<=n;j++){
	//		cout<<f[i][j]<<" ";	
	//	}
	//	cout<<endl; 
	//}
	scanf("%d",&k);
	for(int i=1;i<=k;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		if(Find(x)!=Find(y)){
			printf("-1\n");
			continue;
		}
		int LCA=lca(x,y);
		printf("%d\n",quan[LCA]);
	}
	return 0;
}
2024/8/5 11:08
加载中...