全部TLE求救
查看原帖
全部TLE求救
276181
GarinGeek楼主2021/8/14 18:04

萌新初学淀粉,样例过了,第一个点下载测了一下没问题,但全部TLE,不知哪里写的不对,求各位巨犇救救孩子,orz。

#include<bits/stdc++.h>
using namespace std;
int k,top,root,cnt,n,m,now,ans[10000005],dis[10005],vis[10005],size[10005],mas[10005],head[10005],t1,t2,t3,val;
struct node{
	int v,chu,nxt;
}a[10005];
void merge(int g,int j,int l){
	a[++cnt].chu=j;
	a[cnt].nxt=head[g];
	a[cnt].v=l;
	head[g]=cnt;
}
void dfssize(int x,int fa){
	size[x]=1;
	mas[x]=0;
	for(int i=head[x];i;i=a[i].nxt){
	if(a[i].chu!=fa&&!vis[a[i].chu]){
		dfssize(a[i].chu,x);
		size[x]+=size[a[i].chu];
		mas[x]=max(mas[x],size[a[i].chu]);
	} 
	} 
}
void dfsroot(int zx,int x,int fa){
	if(size[zx]-size[x]>mas[x]) mas[x]=size[zx]-size[x];
	if(mas[x]<val){ 
		val=mas[x];
		root=x;
	}
	for(int i=head[x];i;i=a[i].nxt)
	if(!vis[a[i].chu]&&a[i].chu!=fa) dfsroot(zx,a[i].chu,x);
}
void dfsdis(int x,int fa,int d){
	dis[++top]=d;
	for(int i=head[x];i;i=a[i].nxt)
	if(a[i].chu!=fa&&!vis[a[i].chu])
	dfsdis(a[i].chu,x,d+a[i].v);
}
void calc(int x,int co){
	top=0;
	dfsdis(x,0,co);
	sort(dis+1,dis+1+top);
	for(register int i=1;i<=top;i++)
	for(register int j=i;j<=top;j++)
	ans[dis[i]+dis[j]]++;
}
void calc1(int x,int co){
	top=0;
	dfsdis(x,0,co);
	sort(dis+1,dis+1+top);
	for(int i=1;i<=top;i++)
	for(int j=i;j<=top;j++)
	ans[dis[i]+dis[j]]--;
}
bool dfs(int x){
	dfssize(x,0);
	val=2147483646;
	dfsroot(x,x,0);
	calc(root,0);
	vis[root]=1;
	for(register int i=head[root];i;i=a[i].nxt){
		if(!vis[a[i].chu]){
		calc1(a[i].chu,a[i].v);
		dfs(a[i].chu); 
		}
	}

} 
int main(){
    cin >> n >> m;
    for(register int i=1;i<n;i++){
    cin >> t1 >> t2 >> t3;
    merge(t1,t2,t3);
    merge(t2,t1,t3);
	}
	dfs(1);
	for(register int i=1;i<=m;i++){
	cin >> k;
	if(ans[k])cout << "AYE" << endl;
	else cout << "NAY" << endl;
	}
	return 0;
}

2021/8/14 18:04
加载中...