求dalao给我(蒟蒻)提点建议,这代码卡时间是为什么?
查看原帖
求dalao给我(蒟蒻)提点建议,这代码卡时间是为什么?
1058114
Clover_ZJ楼主2025/8/31 22:26
#include<bits/stdc++.h>
using namespace std;

const int MAXN=10010;
const int mod=1000007;

int n,m,maxk;

struct Edge{
	int to,nxt,val;
}edge[MAXN<<1];
int head[MAXN],edge_cnt; 

int	tree_size[MAXN];
bool removed[MAXN];

//哈希    ty(0=全局, 1=当前子树)
int hash_head[2][mod+10],hash_val[2][MAXN],hash_nxt[2][MAXN];
int hash_cnt[2];
int stack_top[2],hash_stack[2][MAXN];

int query[110];
bool query_ans[110];//判断是否存在k的距离


// 工具函数 ------------------------------------------------

// 插入一个值到哈希表 ty(0=全局, 1=当前子树)
inline void insert_hash(int val,int ty){
	int h=val%mod;
	for(int i=hash_head[ty][h];i;i=hash_nxt[ty][i]){
		if(hash_val[ty][i]==val) return;// 已经存在相同的,就不用存了 
	}
	int hnt=++hash_cnt[ty];
	hash_val[ty][hnt]=val;
	hash_nxt[ty][hnt]=hash_head[ty][h];
	if(!hash_head[ty][h]){//每次新建hash就记录一次位置,方便后面清空 
		int snt=stack_top[ty]++;
		hash_stack[ty][snt]=h;// 记录该桶,用于清空 !!!看solve的第7行!!! 
	}
	hash_head[ty][h]=hnt;
}

// 查询哈希表 0 中是否存在某个值
inline bool exist_in_hash(int val){
	int h=val%mod;
	for(int i=hash_head[0][h];i;i=hash_nxt[0][i]){
		if(hash_val[0][i]==val) return true;
	}
	return false;
}

//存图 // 添加边
inline void add_edge(int a,int b,int w){
	edge[++edge_cnt].nxt=head[a];
	head[a]=edge_cnt;
	edge[edge_cnt].to=b;
	edge[edge_cnt].val=w;
}

// 计算子树大小
void calculate_tree_size(int u,int fa){
	tree_size[u]=1;
	for(int i=head[u],v;i;i=edge[i].nxt){
		v=edge[i].to;
		if(v==fa||removed[v]) continue;
		calculate_tree_size(v,u);
		tree_size[u]+=tree_size[v];
	}
} 

// 找到某个子树的重心       max_size一般是的tree_size[x]/2 
int find_heavy(int u,int fa,int max_size){//因为每个点的tree_size是一样的,所有下面没有必要更新max_size 
	while(1){
		bool ok=true;
		for(int i=head[u],v;i;i=edge[i].nxt){
			v=edge[i].to;
			if(v==fa||removed[v])continue;
			if(tree_size[v]>=max_size){//当子节点大小>=tree_size[u]/2则重心不在这里 
				ok=false;
				fa=u;
				u=v;//类似于递归,都是while会更快,因为递归会不断的开栈 
				break;
			}
		}
		if(ok) return u;//找到了重心就返回 
	}
}

// 收集从某节点出发到子树内所有点的距离
void collect_dist_ans(int u,int fa,int dist,vector<int>& dist_list){
	if(dist>maxk) return;
	dist_list.push_back(dist);//记录所有距离(可能有相同的)
	for(int v,e=head[u];e;e=edge[e].nxt){
		v=edge[e].to;
		if(v==fa||removed[v])continue;
		collect_dist_ans(v,u,dist+edge[e].val,dist_list);
	}
} 

// 核心分治过程--------------
void solve(int x){
	//1找重心 
	calculate_tree_size(x,0);
	int heavy=find_heavy(x,0,tree_size[x]/2);//规定要所有子节点的size要小于当前size的二分之一 
	
	// 2. 清空全局哈希表 ty(0=全局, 1=当前子树)
	for(int i=1;i<=stack_top[0];++i)hash_head[0][hash_stack[0][i]]=0;
	stack_top[0]=0;hash_cnt[0]=0;
	
	insert_hash(0,0);// 重心自身到重心的距离 = 0
	
    // 3. 遍历每棵子树,检查跨子树路径
     for(int v,e=head[heavy];e;e=edge[e].nxt){
     	v=edge[e].to;
     	if(removed[v])continue;
     	
        // 临时哈希表清空 ty(0=全局, 1=当前子树)
        for (int i = 1; i <= stack_top[1]; i++) hash_head[1][hash_stack[1][i]] = 0;
        stack_top[1] = 0; hash_cnt[1] = 0;
		//存储距离
        vector<int> dist_list;//每次都新建,及初始化
		collect_dist_ans(v,heavy,edge[e].val,dist_list);//计算距离 
		
        // 先检查这些距离能否回答查询
		for(int d:dist_list){//d就是每个距离
			for(int qi=1;qi<=m;qi++){
				if(query_ans[qi])continue;
				if(d==query[qi])query_ans[qi]=true;
				else if(d<query[qi]&&exist_in_hash(query[qi]-d)){//找过该点的另一条边长度是否符合
					query_ans[qi]=true;
				}
			}
		}
        
		// 再把这些距离加入全局哈希
		for(int d:dist_list)insert_hash(d,0);
	}

    // 4. 标记重心并递归处理子树
	removed[heavy]=true;//已经遍历过了,就不用在遍历一遍其他点经过重心的距离
	for(int v,e=head[heavy];e;e=edge[e].nxt){
		v=edge[e].to;
		if(!removed[v]) solve(v);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int u,v,w,i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	for(int i=1;i<=m;++i){
		scanf("%d",&query[i]);
		maxk=max(query[i],maxk); 
	}
	solve(1);
	for(int i=1;i<=m;++i){
		if(query_ans[i]) puts("AYE");
		else puts("NAY");
	}
	
	return 0;
} 

2025/8/31 22:26
加载中...