제출 #888980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888980		amirhoseinfar1385	Sprinkler (JOI22_sprinkler)	C++17	41 / 100	4054 ms	71184 KiB

sprinkler

#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
vector<long long>adj[maxn];
long long q,high[maxn],n,mod,timea=0,part[maxn];
pair<long long,long long>stf[maxn];
struct segment{
	vector<long long>seg;
	long long sz=0;
	void create(){
		while(__builtin_popcount(sz)!=1){
			sz++;
		}
		seg.resize(sz*2,1);
	}
	void add(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i]*=w;
			seg[i]%=mod;
			return ;
		}
		long long m=(l+r)>>1;
		add((i<<1),l,m,tl,tr,w);
		add((i<<1)^1,m+1,r,tl,tr,w);
		return ;
	}
	long long pors(long long i){
		if(i==0){
			return 1;
		}
		long long ret=pors((i>>1))*seg[i]%mod;
		return ret;
	}
}seg[maxn];
vector<pair<long long,long long>>alll[maxn];

void pre(long long u=1,long long par=1){
	part[u]=par;
	timea++;
	stf[u].first=timea;
	alll[high[u]].push_back(make_pair(stf[u].first,u));
	for(auto x:adj[u]){
		if(x!=par){
			high[x]=high[u]+1;
			pre(x,u);
		}
	}
	stf[u].second=timea;
}

void upd(long long u,long long dis,long long w){
	long long z=0;
	long long lev=high[u]+dis;
	while(lev>=0&&high[u]<=lev){
		if(lev<maxn){
			long long l=lower_bound(alll[lev].begin(),alll[lev].end(),make_pair(stf[u].first,-1ll))-alll[lev].begin();
			long long r=lower_bound(alll[lev].begin(),alll[lev].end(),make_pair(stf[u].second+1,-1ll))-alll[lev].begin();
			//cout<<u<<" "<<dis<<" "<<w<<" "<<l<<" "<<r<<" "<<lev<<endl; 
			r--;
			seg[lev].add(1,0,seg[lev].sz-1,l,r,w);
		}
		if(z==1){
			u=part[u];
			lev--;
			z=0;
		}
		else{
			lev--;
			z=1;
		}
	}
}

void solve(long long u){
	long long ind=lower_bound(alll[high[u]].begin(),alll[high[u]].end(),make_pair(stf[u].first,u))-alll[high[u]].begin();
	//cout<<u<<" wtf "<<ind<<endl;
	cout<<seg[high[u]].pors(ind+seg[high[u]].sz)<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>mod;
	for(long long i=0;i<n-1;i++){
		long long u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	pre(1);
	for(long long i=0;i<maxn;i++){
		seg[i].sz=alll[i].size();
		seg[i].create();
	}
	for(long long i=1;i<=n;i++){
		long long d;
		cin>>d;
		upd(i,0,d);
	}
	cin>>q;
	for(long long i=0;i<q;i++){
		long long qq;
		cin>>qq;
		if(qq==1){
			long long u,d,w;
			cin>>u>>d>>w;
			upd(u,d,w); 
		}
		else{
			long long u;
			cin>>u;
			solve(u);
		}
	}
}

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17