QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#413815#6737. NeighbourhoodThankto_zy6ML 0ms0kbC++146.6kb2024-05-18 09:14:402024-05-18 09:14:41

Judging History

你现在查看的是最新测评结果

  • [2024-05-18 09:14:41]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-05-18 09:14:40]
  • 提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ii;
int he[200005],to[400005],ne[400005],id[400005],cnt;
ii w[200005];
void link(int u,int v,int w){
	cnt++;
	to[cnt]=v;
	ne[cnt]=he[u];
	id[cnt]=w;
	he[u]=cnt;
}
int B;
bool bdr[200005];
int bel[200005],bee[200005],stk[200005],_top[200005],top;
int cl[200005],clutop;
int up[200005],down[200005];
struct nodd{
	int id;
	ii v;
};
bool operator<(nodd x,nodd y){
	return x.v<y.v;
}
vector<nodd>dis[200005][2];int clu;
int ef[200005],fa[200005],wait[200005],low[200005];
ii dud[200005];int tag[200005];bool vist[200005];
vector<nodd>edge[200005][405];
void puttag(int x,int pr,int k,int tg){
	tag[x]=tg;vist[x]=true;
	for(int i=he[x];i;i=ne[i]){
		if(to[i]!=pr&&bel[to[i]]==k){
			puttag(to[i],x,k,tg);
		}
	}
}
void getdud(int i){
	int x=down[i];dud[i]=0;
	if(!x)return;
	while(x!=up[i]){
		dud[i]+=w[ef[x]];
		x=fa[x];
	}
}
int get(int x,int i){
	return (x==up[i])?0:1;
}
struct node{
	int v,i;
};
vector<node>eg[200005];int bdn[200005],bdt;
void add_clu(int u,int v){
	clu++;
	if(!bdr[u])bdn[++bdt]=u;
	if(!bdr[v])bdn[++bdt]=v;
	bdr[u]=1;up[clu]=u;
	if(!v)v=cl[clutop];
	eg[u].push_back({v,clu});
	down[clu]=v;bdr[v]=1;
	eg[v].push_back({u,clu});
	clutop=0;
}
void dfs(int x){
	wait[x]=1;int tot=0;_top[x]=top;
	for(int i=he[x];i;i=ne[i]){
		if(to[i]==fa[x])continue;
		ef[to[i]]=id[i];fa[to[i]]=x;stk[++top]=to[i];
		dfs(to[i]);
		wait[x]+=wait[to[i]];
		if(low[to[i]])low[x]=low[to[i]],tot++;
	}
	if(tot>1||wait[x]>=B||!fa[x]){
		wait[x]=0;
		low[x]=x;
		for(int i=he[x],cur=0,j=_top[x]+1,wt=0;;i=ne[i]){
			if(to[i]==fa[x]&&fa[x])continue;
			int v=to[i];
			if(wt+wait[v]>B||!v||(cur&&low[v])){
				for(;(j<_top[v]||!v)&&j<=top;j++){
					cl[++clutop]=stk[j];
					if(!bel[stk[j]])bel[stk[j]]=clu+1;
					if(stk[j]!=x){
						if(!bee[ef[stk[j]]]){
							bee[ef[stk[j]]]=clu+1;
							edge[clu+1][stk[j]].push_back({ef[stk[j]],fa[stk[j]]});
							edge[clu+1][fa[stk[j]]].push_back({ef[stk[j]],stk[j]});
						}
					}
				}
				add_clu(x,cur);
				wt=cur=0;
			}
			wt+=wait[v];
            if(low[v])cur=low[v];
			if(!i)break;
		}
	}
}
void sear(int x,int pr,int k,int bz,ii ds){
	if(!bdr[x])dis[k][bz].push_back({x,ds});
//	for(int i=he[x];i;i=ne[i]){
//		if(to[i]!=pr&&(bel[to[i]]==k||to[i]==up[k]||to[i]==down[k])){
//			sear(to[i],x,k,bz,ds+w[id[i]]);
//		}
//	}
	for(nodd v:edge[k][x]){
		if(v.v!=pr){
			sear(v.v,x,k,bz,ds+w[v.id]);
		}
	}
}
void pre(int x,int i){
	if(!x)return;
	int bz=get(x,i);
	vector<nodd>().swap(dis[i][bz]);
	sear(x,0,i,bz,0);
	sort(dis[i][bz].begin(),dis[i][bz].end());
}
int flg[200005];
void sear2(int x,int pr,int k,int tg,int sw){
	flg[x]=sw;
//	for(int i=he[x];i;i=ne[i]){
//		if(to[i]!=pr&&(bel[to[i]]==k||to[i]==up[k]||to[i]==down[k])){
//			if(id[i]==tg){
//				sear2(to[i],x,k,tg,1);
//			}
//			else{
//				sear2(to[i],x,k,tg,sw);
//			}
//		}
//	}
	for(nodd v:edge[k][x]){
		if(v.v!=pr){
			if(v.id==tg){
				sear2(v.v,x,k,tg,1);
			}
			else{
				sear2(v.v,x,k,tg,sw);
			}
		}
	}
}
nodd ttmp1[200005],ttmp2[200005];int top1,top2;
void pre2(int x,int i,int tg,ii delta){
	if(!x)return;top1=top2=0;
	int bz=get(x,i);
	sear2(x,0,i,tg,0);
	for(nodd v:dis[i][bz]){
		if(flg[v.id])ttmp2[++top2]={v.id,v.v+delta};
		else ttmp1[++top1]=v;
	}
	vector<nodd>().swap(dis[i][bz]);
	int j=1,k=1;
	while(j<=top1&&k<=top2){
		if(ttmp1[j].v<ttmp2[k].v){
			dis[i][bz].push_back(ttmp1[j]);
			j++;
		}
		else{
			dis[i][bz].push_back(ttmp2[k]);
			k++;
		}
	}
	while(j<=top1){
		dis[i][bz].push_back(ttmp1[j]);
		j++;
	}
	while(k<=top2){
		dis[i][bz].push_back(ttmp2[k]);
		k++;
	}
}
int qry_clu(int x,int i,ii k){
	if(!x)return 0;
	int bz=get(x,i);
	if(dis[i][bz].empty())return 0;
	if((dis[i][bz].back()).v<=k){
		return dis[i][bz].size();
	}
	int l=1,r=dis[i][bz].size(),mid;
	while(l<r){
		mid=(l+r)>>1;
		if(dis[i][bz][mid-1].v<=k)l=mid+1;
		else r=mid;
	}
//	cerr<<"!"<<x<<" "<<i<<" "<<k<<" "<<l-1<<endl;
	return l-1;
}
int res;
ii d1,d2;
void qry1(int x,int y,int pr,ii ds,ii k){
	if(x==up[y])d1=ds;
	if(x==down[y])d2=ds;
//	if(bdr[x])return;
	if(ds<=k&&!bdr[x])res++;
//	for(int i=he[x];i;i=ne[i]){
//		if(to[i]!=pr&&(bel[to[i]]==y||to[i]==up[y]||to[i]==down[y])){
//			qry1(to[i],y,x,ds+w[id[i]],k);
//		}
//	}
	for(nodd v:edge[y][x]){
		if(v.v!=pr){
			qry1(v.v,y,x,ds+w[v.id],k);
		}
	}
}
int qry2(int x,int pr,ii k){
	int ret=1;
	if(k<0)return 0;
	for(node v:eg[x]){
		if(v.v!=pr){
			ret+=qry_clu(x,v.i,k);
			if(k>=dud[v.i]&&v.v){
				ret+=qry2(v.v,x,k-dud[v.i]);
			}
		}
	}
	return ret;
}
inline ii read(){
	char ch=getchar();
	ii ret=0;
	while(ch<'0'||ch>'9')ch=getchar();
	while('0'<=ch&&ch<='9'){
		ret=ret*10+ch-'0';
		ch=getchar();
	}
	return ret;
}
int main(){
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	int n=read(),q=read();B=max(700,int(sqrt(n)));
	for(int i=1;i<n;i++){
		int u=read(),v=read();w[i]=read();
		link(u,v,i);
		link(v,u,i);
	}
	dfs(1);
	for(int i=1;i<=clu;i++){
		pre(up[i],i);
		if(down[i])pre(down[i],i);
		int x=down[i];dud[i]=0;
		if(!x)continue;
		int o=0;
		while(x!=up[i]){
			dud[i]+=w[ef[x]];
			if(!bdr[x]){
				for(int j=he[x];j;j=ne[j]){
					if(bel[to[j]]==i&&to[j]!=o&&to[j]!=fa[x]){
						puttag(to[j],x,i,x);
					}
				}
				if(!bdr[x])tag[x]=x,vist[x]=true;
			}
			o=x;
			x=fa[x];
		}
	}
	for(int i=1;i<=bdt;i++){
		int x=bdn[i];tag[x]=x;
		for(int j=he[x];j;j=ne[j]){
			int y=to[j];
			if(!tag[y]){
				if(!bdr[to[j]])puttag(to[j],x,bel[to[j]],x);
			}
		}
	}
	int tot=0;
	while(q--){
		int opt=read();
		if(opt==1){
			int i=read();ii c=read(),d;d=c-w[i];
			w[i]=c;
			int k=bee[i];
			pre2(up[k],k,i,d);
			if(down[k])pre2(down[k],k,i,d);
			getdud(k);
		}
		else{
			int x=read();ii d=read();
			res=0;
			if(!bdr[x]){
				if(tag[x]!=up[bel[x]]&&tag[x]!=down[bel[x]]){
					qry1(x,bel[x],0,0,d);
					res+=qry2(up[bel[x]],down[bel[x]],d-d1);
					res+=qry2(down[bel[x]],up[bel[x]],d-d2);
				}
				else{
					if(tag[x]==up[bel[x]]){
						qry1(x,bel[x],0,0,d);
						res+=qry2(up[bel[x]],0,d-d1);
						res-=qry_clu(up[bel[x]],bel[x],d-d1);
					}
					if(tag[x]==down[bel[x]]){
						qry1(x,bel[x],0,0,d);
						res+=qry2(down[bel[x]],0,d-d2);
						res-=qry_clu(down[bel[x]],bel[x],d-d2);
					}
				} 
			}
			else{
				res=qry2(x,-1,d);
			}
			printf("%d\n",res);
		}
		tot++;
		if(tot==1000)cerr<<clock()*1.0/CLOCKS_PER_SEC<<endl;
	}
	return 0;
}

详细

Test #1:

score: 0
Memory Limit Exceeded

input:

3 7
1 2 3
2 3 1
2 2 1
2 1 3
2 3 4
1 1 1
2 2 1
2 1 0
2 3 1

output:

2
2
3
3
1
2

result: