TLE#8#10求调
查看原帖
TLE#8#10求调
1336631
enter_prise楼主2025/7/26 20:18
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e4+5,MAXM=105;
int read(){
    int x=0,zhubi=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')zhubi=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*zhubi;
}
struct wzy{
	int to;
	int nxt;
	int length;
}edge[MAXN<<1];
int n,m,h[MAXN],u,v,w,size[MAXN],weight[MAXN],rt,que[MAXM],a[MAXN],b[MAXN],d[MAXN],cnt=0;
bool vis[MAXN],done[MAXM];
bool f(int x,int y){
	return d[x]<d[y];
}
void get(int start,int fa,int zong){
	size[start]=1;
	weight[start]=0;
	for(int i=h[start];i!=-1;i=edge[i].nxt){
		v=edge[i].to;
		if(v!=fa&&!vis[v]){
			get(v,start,zong);
			size[start]+=size[v];
			weight[start]=max(weight[start],size[v]);
		}
	}
	weight[start]=max(weight[start],zong-size[start]);
	if(weight[start]<weight[rt]||rt==0) rt=start;
	return ;
}
void getdis(int start,int fa,int disnow,int from){
	if(disnow>1e7) return ;
	a[++cnt]=start;
	d[start]=disnow;
	b[start]=from;
	for(int i=h[start];i!=-1;i=edge[i].nxt){
		v=edge[i].to;
		if(!vis[v]&&v!=fa){
			getdis(v,start,disnow+edge[i].length,from);
		}
	}
	return ;
}
void cal(int start){
	cnt=0;
	a[++cnt]=start;
	d[start]=0;
	b[start]=start;
	for(int i=h[start];i!=-1;i=edge[i].nxt){
		v=edge[i].to;
		if(!vis[v]){
			getdis(v,start,edge[i].length,v);
		}
	}
	sort(a+1,a+cnt+1,f);
	for(int i=1;i<=m;i++){
		if(done[i])  continue;
		int l=1,r=cnt;
		while(l<r){
			if(d[a[l]]+d[a[r]]>que[i]) r--;
			else if(d[a[l]]+d[a[r]]<que[i]) l++;
			else if(b[a[l]]==b[a[r]]){
				if(d[a[r]]==d[a[r-1]]) r--;
				else l++;
			}
			else{
				done[i]=true;
				break;
			}
		}
	}
	return ;
}
void fenzhi(int start){
	vis[start]=true;
	cal(start);
	/*memset(b,0,sizeof(b));
	memset(d,0,sizeof(d));
	memset(a,0,sizeof(a));*/
	for(int i=h[start];i!=-1;i=edge[i].nxt){
		if(!vis[edge[i].to]){
			rt=0;
            memset(weight,0,sizeof(weight));
			get(edge[i].to,0,size[edge[i].to]);
			fenzhi(rt);
		}
	}
	return ;
}
int main(){
	memset(h,-1,sizeof(h));
	//weight[0]=2147483647;
	//scanf("%d %d",&n,&m);
	n=read();m=read();
	for(int i=1;i<=(n-1)*2;i++){
		//scanf("%d %d %d",&u,&v,&w);
		u=read();v=read();w=read();
		edge[i].to=v;
		edge[i].nxt=h[u];
		edge[i].length=w;
		h[u]=i;
		i++;
		edge[i].to=u;
		edge[i].nxt=h[v];
		edge[i].length=w;
		h[v]=i;
	}
	for(int i=1;i<=m;i++){
		que[i]=read();
		//scanf("%d",&que[i]);
		if(!que[i]) done[i]=true;
	}
	rt=0;
	get(1,0,n);
	fenzhi(rt);
	for(int i=1;i<=m;i++){
		if(done[i]) printf("AYE\n");
		else printf("NAY\n");
	}
	return 0;
}
2025/7/26 20:18
加载中...