TLE #8 求助
查看原帖
TLE #8 求助
549499
Disjoint_cat楼主2022/10/8 14:00

RT

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=10005,K=10000005,M=105;
int n,m,U,V,W,q[M],siz[N],root,ma[N],LEN,t,cnt,tot;
bool can[M],Vis[N];
int head[N],to[N<<1],dis[N<<1],nxt[N<<1],cnt2;//lsqxx
struct rec
{
	int len,tr;
	bool operator<(const rec B)const
	{
		return len<B.len;
	}
}v[N];
#ifndef ONLINE_JUDGE
double st,et,st1,et1,sum;
#endif
void add(int From,int To,int Dis)
{
	to[++cnt2]=To,dis[cnt2]=Dis,nxt[cnt2]=head[From],head[From]=cnt2;
}
void froot(int now,int fa)
{
	siz[now]=1,ma[now]=0;
	for(int i=head[now];i;i=nxt[i])
		if((t=to[i])!=fa&&!Vis[t])
		{
			froot(t,now);
			siz[now]+=siz[t],ma[now]=max(ma[now],siz[t]);
		}
	ma[now]=max(ma[now],LEN-siz[now]);
	if(!root||ma[now]<ma[root])root=now;
}
void dfs(int now,int fa,int len,int Tr)
{
	v[++cnt]=rec{len,Tr};
	for(int i=head[now];i;i=nxt[i])
		if((t=to[i])!=fa&&!Vis[t])
			dfs(t,now,len+dis[i],Tr);
}
void sol(int Root)
{
	v[cnt=1]=rec{0,0};
	for(int i=head[Root];i;i=nxt[i])
		if(!Vis[t=to[i]])
			dfs(t,Root,dis[i],t);
	//cout<<cnt<<endl;
	tot+=cnt;
	//st1=clock();
	sort(v+1,v+cnt+1);
	int l,r;
	for(int i=1;i<=m;i++)
	{
		if(can[i])continue;
		l=1,r=cnt;
		while(l<r)
		{
			if(v[l].len+v[r].len<q[i])l++;
			else if(v[l].len+v[r].len>q[i])r--;
			else
			{
				if(v[l].tr!=v[r].tr)
				{
					can[i]=1;
					break;
				}
				else if(v[l].len==v[l+1].len)l++;
				else r--;
			}
		}
	}
	//et1=clock();
	//sum+=et1-st1;
}
void dfz(int Root)
{
	Vis[Root]=1;
	sol(Root);
	for(int i=head[Root];i;i=nxt[i])
		if(!Vis[t=to[i]])
		{
			//sol(t);
			LEN=siz[t],root=0;
			froot(t,0);
			//cout<<root<<endl;
			dfz(root);
		}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("P3806_8.in","r",stdin);
freopen("my.txt","w",stdout);
st=clock();
#endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		cin>>U>>V>>W;
		//to[U].push_back(V),to[V].push_back(U),dis[U].\
		//push_back(W),dis[V].push_back(W);
		add(U,V,W);add(V,U,W);
	}
	for(int i=1;i<=m;i++)cin>>q[i];
	LEN=n;
	froot(1,0);
	dfz(root);
#ifndef ONLINE_JUDGE
et=clock();
cout<<"time:"<<et-st<<"ms"<<endl;
cout<<sum<<endl<<tot;
fclose(stdout);
#endif
	for(int i=1;i<=m;i++)cout<<(can[i]?"AYE":"NAY")<<endl;
	return 0;
}
2022/10/8 14:00
加载中...