求助 为什么么在线IDE上 60ms,评测直接超时了
查看原帖
求助 为什么么在线IDE上 60ms,评测直接超时了
222127
云岁月书楼主2020/7/20 21:04
# include <cstdio>
# include <algorithm>
# define N 10000
# define reg register

inline int Max(const int a,const int b){return a > b ? a : b;}

inline int Read()
{
	int x = 0;char ch = getchar();
	
	while(ch < '0' || ch > '9') ch = getchar();
	
	while(ch <= '9' && ch >= '0'){x = x*10+(ch^48);ch = getchar();}
	
	return x; 
}

struct edge
{
	int Next,to,wi;
	
	edge(const int Next_=0,const int To_=0,const int wi_=0):Next(Next_),to(To_),wi(wi_){}
} e[(N<<1) + 42];

bool vis[N + 42],It_is_OK[142];
int head[N + 42],edge_tot,U,g[N + 42],Size[N + 42],rt,dis[N + 42],id[N + 42],top,color[N + 42],Query[142],n,m;

inline void add_edge(const int wi,const int v,const int u)
{
	e[++edge_tot] = edge(head[u],v,wi);
	
	head[u] = edge_tot;
	
	e[++edge_tot] = edge(head[v],u,wi);
	
	head[v] = edge_tot;
}

inline bool comp(const int a__,const int b__){return dis[a__] < dis[b__];}

void Getgc(const int u,const int fa)
{
	Size[u] = 1;g[u] = 0;
	
	for(reg int i = head[u]; i ; i = e[i].Next)
		if(e[i].to != fa && !vis[e[i].to])
		{
			Getgc(e[i].to,u);
			
			Size[u] += Size[e[i].to];
			
			g[u] = Max(g[u],Size[e[i].to]);
		}
	
	g[u] = Max(g[u],U-Size[u]);
	
	if(g[u] < g[rt]) rt = u;
}

int Getdis(const int u,const int fa,const int col)
{
	id[++top] = u;color[u] = col;
	for(reg int i = head[u]; i ; i = e[i].Next)
		if(e[i].to != fa && !vis[e[i].to])
		{
			dis[e[i].to] = dis[u] + e[i].wi;
			
			Getdis(e[i].to,u,col);
		}
}

void Calc(const int u)
{
	id[top = 1] = u;dis[u] = 0;color[u] = u;
	
	for(reg int i = head[u]; i ; i = e[i].Next)
		if(!vis[e[i].to])
		{
			dis[e[i].to] = e[i].wi;
			
			Getdis(e[i].to,u,e[i].to);
		}
		
	std::sort(id+1,id+top+1,comp);//使原数组有序化,折半查找.
	
	for(reg int k = 1; k <= m ; ++k)
		if(!It_is_OK[k])
		{
			reg int l = 1,r = top;
			
			while(l < r)
			{
				if(dis[id[l]] + dis[id[r]] > Query[k]) --r;
				else if(dis[id[l]] + dis[id[r]] < Query[k]) ++l;
				else if(color[id[l]] == color[id[r]])
				{
					if(dis[id[r]] == dis[id[r-1]])r--;
					else l++;
				}
				else
				{
					It_is_OK[k] = 1;
					break;
				}
			}
		}
}

void PDC(const int u)
{
	vis[u] = 1;
	
	Calc(u);
	
	for(reg int i = head[u] ; i ; i = e[i].Next)
		if(!vis[e[i].to])
		{
			rt = 0;
			U = Size[e[i].to];
			Getgc(e[i].to,e[i].to);
			PDC(rt);
		}
}

int main()
{
	n = Read();m = Read();
	
	for(reg int i = 1; i < n ; ++i) add_edge(Read(),Read(),Read());
	
	for(reg int i = 1; i <= m ; ++i) (Query[i] = Read()) == 0 ? It_is_OK[i] = 1 : It_is_OK[i] = 0;
	
	g[0] = n;
	
	Getgc(1,1);
	
	PDC(rt);
	
	for(reg int i = 1; i <= m ; ++i)
		if(It_is_OK[i]) puts("AYE");
		else puts("NAY");
			
	return 0;
} 
2020/7/20 21:04
加载中...