TLE on #7#9 求条
查看原帖
TLE on #7#9 求条
685183
LightSpot楼主2024/12/31 12:18
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 10 , INF = 0x3f3f3f3f;
inline int read()
{
    int x = 0 , f = 1;
    char c = getchar();
    while(c < '0' || c > '9')
	{
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
	{
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x * f;
}
struct node
{
	int to;
	int val;
};
struct pt
{
	int pos;
	int id;
	int dis;
};
int n , m;
int q[MAXN];
int sz[MAXN] , wt[MAXN] , ct;
bool vis[MAXN] , ans[MAXN];
pt tr_dis[MAXN];
int lp;
vector <node> a[MAXN];
void get_ct(int now , int fa , int sum)
{
	sz[now] = 1;
	wt[now] = 0;
	for(node i : a[now])
	{
		int to = i.to;
		if(to == fa || vis[to]) continue;
		get_ct(to , now , sum);
		sz[now] += sz[to];
		wt[now] = max(wt[now] , sz[to]);
	}
	wt[now] = max(wt[now] , sum - sz[now]);
	if(!ct || wt[now] < wt[ct]) ct = now;
	return;
}
void get_dis(int now , int fa , int dis , int from)
{
	tr_dis[++lp].pos = now , tr_dis[lp].dis = dis , tr_dis[lp].id = from;
	for(node i : a[now])
	{
		int to = i.to , val = i.val;
		if(to == fa || vis[to]) continue;
		get_dis(to , now , dis + val , from);
	}
	return;
}
bool cmp(pt x , pt y)
{
	return x.dis < y.dis;
}
void calc(int now)
{
	lp = 0;
	tr_dis[++lp].pos = now , tr_dis[lp].dis = 0 , tr_dis[lp].id = now;
	for(node i : a[now])
	{
		int to = i.to , val = i.val;
		if(vis[to]) continue;
		get_dis(to , now , val , to);
	}
	sort(tr_dis + 1 , tr_dis + 1 + lp , cmp);
	for(int i = 1 ; i <= m ; i++)
	{
		int l = 1 , r = lp;
		if(ans[i]) continue;
		while(l < r)
		{
			if(tr_dis[l].dis + tr_dis[r].dis > q[i]) r--;
			else if(tr_dis[l].dis + tr_dis[r].dis < q[i]) l++;
			else if(tr_dis[l].id == tr_dis[r].id)
			{
				if(tr_dis[l].id == tr_dis[r - 1].id) r--;
				else l++;
			}
			else
			{
				ans[i] = 1;
				break;
			}
		}
	}
	return;
}
void solve(int now)
{
	vis[now] = 1;
	calc(now);
	for(node i : a[now])
	{
		int to = i.to;
		if(vis[to]) continue;
		ct = 0;
		get_ct(to , 0 , sz[to]);
		solve(to);
	}
	return; 
}
int main()
{
	cin >> n >> m;
	for(int i = 1 ; i < n ; i++)
	{
		int u = read() , v = read() , w = read();
		node tmp;
		tmp.val = w;
		tmp.to = v;
		a[u].push_back(tmp);
		tmp.to = u;
		a[v].push_back(tmp);
	}
	for(int i = 1 ; i <= m ; i++)
	{
		q[i] = read();
		if(!q[i]) ans[i] = 1;
	}
	ct = 0;
	wt[ct] = INF;
	get_ct(1 , 0 , n);
	solve(ct);
	for(int i = 1 ; i <= m ; i++)
	{
		if(ans[i]) printf("AYE\n");
		else printf("NAY\n");
	}
	return 0;
}

2024/12/31 12:18
加载中...