TLE 求助
查看原帖
TLE 求助
754311
zhangjiting楼主2024/5/6 16:22

不知道是常数大还是做法错了还是输入挂了,难绷

#include<bits/stdc++.h>
#define endl '\n'
#define debug(x) cout<<#x<<':'<<x<<endl
using namespace std;
const int N=1e5+5;
int n,m,cnt;
int top[N],son[N],dep[N],siz[N],fa[N],dfn[N],a[N],num[N],tot;
int to[N<<1],nxt[N<<1],head[N<<1];
#define ls p<<1
#define rs p<<1|1
struct node{
	int l,r;
	set<int> s;
}tree[N<<2];
void build(int p,int l,int r){
	tree[p].l=l,tree[p].r=r;
	for(int i=l;i<=r;i++) tree[p].s.insert(a[i]);
	if(l==r) return;
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
int ask(int p,int l,int r,int k){
	if(l<=tree[p].l&&tree[p].r<=r){
		return tree[p].s.count(k);
	}
	int mid=(tree[p].l+tree[p].r)>>1,res=0;
	if(l<=mid) res+=ask(ls,l,r,k);
	if(r>mid) res+=ask(rs,l,r,k);
	return res;
}
void add(int x,int y){
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
void dfs1(int x,int f){
	siz[x]=1;dep[x]=dep[f]+1;fa[x]=f;
	int mx=INT_MIN;
  	for(int i=head[x];i;i=nxt[i]){
  		int y=to[i];
  		if(y==f) continue;
  		dfs1(y,x);
  		siz[x]+=siz[y];
  		if(siz[y]>mx)mx=siz[y],son[x]=y;
	}
}
void dfs2(int x,int hd){
	top[x]=hd;
	dfn[x]=++cnt;
	a[cnt]=num[x];
	if(son[x]) dfs2(son[x],hd);
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y!=son[x]&&y!=fa[x]) dfs2(y,y);
	}
}
int query(int x,int y,int k){
	while(top[x]^top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		if(ask(1,dfn[top[x]],dfn[x],k)>0) return 1;
		x=fa[top[x]];
	}
	if(dfn[x]>dfn[y]) swap(x,y);
	return ask(1,dfn[x],dfn[y],k);
}
signed main(){
	while(scanf("%d%d",&n,&m)!=EOF){

	memset(top,0,sizeof(top));
	memset(son,0,sizeof(son));
	memset(dep,0,sizeof(dep));
	memset(siz,0,sizeof(siz));
	memset(fa,0,sizeof(fa));
	memset(dfn,0,sizeof(dfn));
	memset(a,0,sizeof(a));
	memset(num,0,sizeof(num));
	memset(to,0,sizeof(to));
	memset(head,0,sizeof(head));
	memset(nxt,0,sizeof(nxt));
	tot=cnt=0;
	for(int i=1;i<=(n<<2);i++){
		tree[i].l=tree[i].r=0;
		tree[i].s.clear();
	}
	

	for(int i=1;i<=n;i++) cin>>num[i];
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		add(u,v),add(v,u);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	for(int i=1,x,y,k;i<=m;i++){
		cin>>x>>y>>k;
		cout<<(query(x,y,k)?"Find\n":"NotFind\n");
	}

	}
    return 0;
}
2024/5/6 16:22
加载中...