对数据范围的疑问(轻喷)
查看原帖
对数据范围的疑问(轻喷)
983702
lrj3247楼主2024/8/1 11:32

题目不是说的n<1e4,m<5e4吗,为什么n开到1e4+15,m开到5e4+15过不去

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+15,M=5e4+15;
int n,m,q,fa[N],top,dep[N],f[N][55],minn[N][55];
bool vis[N];
inline int read(){
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		w=w*10+ch-'0';
		ch=getchar();
	}
	return w*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
struct City{
	int to,w;
};
struct Edge{
	int u,v,w;
}ed[N];
bool cmp(Edge b1,Edge b2){
	return b1.w>b2.w;
}
vector<City> g[N];
int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void kruskal(){
	sort(ed+1,ed+top+1,cmp);
	for(int i = 1 ; i<=n ; i++){
		fa[i]=i;
	}
	for(int i = 1 ; i<=top ; i++){
		int x=ed[i].u,y=ed[i].v,w=ed[i].w;
		int fx=find(x),fy=find(y);
		if(fx!=fy){
			fa[fx]=fy;
			g[x].push_back({y,w});
			g[y].push_back({x,w});
		}
	}
}
void dfs(int rt,int fat){
	vis[rt]=1;
	dep[rt]=dep[fat]+1; 
	f[rt][0]=fat;
	for(int i = 1 ; i<=50 ; i++){
		f[rt][i]=f[f[rt][i-1]][i-1];
		if(f[rt][i]!=0)
		minn[rt][i]=min(minn[rt][i-1],minn[f[rt][i-1]][i-1]);
		else
		break;
	}
	int len=g[rt].size();
	for(int i = 0 ; i<len ; i++){
		int to=g[rt][i].to;
		if(!vis[to]){
			minn[to][0]=g[rt][i].w;
			dfs(to,rt);
		}
	}
}
inline int MIN(int b1,int b2,int b3){
	if(b1<=b2&&b1<=b3) return b1;
	else if(b2<=b1&&b2<=b3) return b2;
	else return b3;
}
inline int LCA(int x,int y){
	if(dep[x]<=dep[y]) swap(x,y);
	int ret=1e9;
	for(int i = 50 ; i>=0 ; i--){
		if(dep[f[x][i]]>=dep[y])
		ret=min(ret,minn[x][i]),x=f[x][i];
	}
	if(x==y)
	return ret;
	for(int i = 50 ; i>=0 ; i--){
		if(f[x][i]!=f[y][i]){
			ret=MIN(ret,minn[x][i],minn[y][i]),x=f[x][i],y=f[y][i];
		}
	}
	ret=MIN(ret,minn[x][0],minn[y][0]);
	return ret;
}
int main(){
	n=read(),m=read();
	for(int i = 1 ; i<=m ; i++){
		int x=read(),y=read(),z=read();
		ed[++top]={x,y,z};
	}
	kruskal();
	for(int i = 1 ; i<=n ; i++)
	if(!vis[i]){
		dfs(i,0);
	}
	q=read();
	for(int i = 1 ; i<=q ; i++){
		int x=read(),y=read();
		if(find(x)!=find(y)){
			write(-1);
			putchar('\n');
		}
		else{
			write(LCA(x,y));
			putchar('\n');
		}
	}
	return 0;
}

而要开到1e5+15和5e5+15才行

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+15,M=5e5+15;
int n,m,q,fa[N],top,dep[N],f[N][55],minn[N][55];
bool vis[N];
inline int read(){
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		w=w*10+ch-'0';
		ch=getchar();
	}
	return w*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
struct City{
	int to,w;
};
struct Edge{
	int u,v,w;
}ed[N];
bool cmp(Edge b1,Edge b2){
	return b1.w>b2.w;
}
vector<City> g[N];
int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
void kruskal(){
	sort(ed+1,ed+top+1,cmp);
	for(int i = 1 ; i<=n ; i++){
		fa[i]=i;
	}
	for(int i = 1 ; i<=top ; i++){
		int x=ed[i].u,y=ed[i].v,w=ed[i].w;
		int fx=find(x),fy=find(y);
		if(fx!=fy){
			fa[fx]=fy;
			g[x].push_back({y,w});
			g[y].push_back({x,w});
		}
	}
}
void dfs(int rt,int fat){
	vis[rt]=1;
	dep[rt]=dep[fat]+1; 
	f[rt][0]=fat;
	for(int i = 1 ; i<=50 ; i++){
		f[rt][i]=f[f[rt][i-1]][i-1];
		if(f[rt][i]!=0)
		minn[rt][i]=min(minn[rt][i-1],minn[f[rt][i-1]][i-1]);
		else
		break;
	}
	int len=g[rt].size();
	for(int i = 0 ; i<len ; i++){
		int to=g[rt][i].to;
		if(!vis[to]){
			minn[to][0]=g[rt][i].w;
			dfs(to,rt);
		}
	}
}
inline int MIN(int b1,int b2,int b3){
	if(b1<=b2&&b1<=b3) return b1;
	else if(b2<=b1&&b2<=b3) return b2;
	else return b3;
}
inline int LCA(int x,int y){
	if(dep[x]<=dep[y]) swap(x,y);
	int ret=1e9;
	for(int i = 50 ; i>=0 ; i--){
		if(dep[f[x][i]]>=dep[y])
		ret=min(ret,minn[x][i]),x=f[x][i];
	}
	if(x==y)
	return ret;
	for(int i = 50 ; i>=0 ; i--){
		if(f[x][i]!=f[y][i]){
			ret=MIN(ret,minn[x][i],minn[y][i]),x=f[x][i],y=f[y][i];
		}
	}
	ret=MIN(ret,minn[x][0],minn[y][0]);
	return ret;
}
int main(){
	n=read(),m=read();
	for(int i = 1 ; i<=m ; i++){
		int x=read(),y=read(),z=read();
		ed[++top]={x,y,z};
	}
	kruskal();
	for(int i = 1 ; i<=n ; i++)
	if(!vis[i]){
		dfs(i,0);
	}
	q=read();
	for(int i = 1 ; i<=q ; i++){
		int x=read(),y=read();
		if(find(x)!=find(y)){
			write(-1);
			putchar('\n');
		}
		else{
			write(LCA(x,y));
			putchar('\n');
		}
	}
	return 0;
}
2024/8/1 11:32
加载中...