Submission #889073

#	Time	Username	Problem	Language	Result	Execution time	Memory
889073		amirhoseinfar1385	Sprinkler (JOI22_sprinkler)	C++17	0 / 100	585 ms	117128 KiB

sprinkler

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
vector<int>adj[maxn];
int q,high[maxn],n,mod,timea=0,part[maxn];
pair<int,int>stf[maxn],av[maxn][42];
struct segment{
	vector<long long>seg;
	int sz=0;
	void create(){
		while(__builtin_popcount(sz)!=1){
			sz++;
		}
		seg.resize(sz*2,1);
	}
	void add(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i]*=w;
			seg[i]%=mod;
			return ;
		}
		int m=(l+r)>>1;
		add((i<<1),l,m,tl,tr,w);
		add((i<<1)^1,m+1,r,tl,tr,w);
		return ;
	}
	int pors(int i){
		if(i==0){
			return 1;
		}
		int ret=seg[i]*pors((i>>1))%mod;
		return ret;
	}
}seg[maxn];
vector<pair<int,int>>alll[maxn];
 
void pre(int u=1,int 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(int u,int dis,int w){
	int z=0;
	int lev=high[u]+dis;
	while(lev>=0&&high[u]<=lev){
		if(lev<maxn){
			int l=av[u][lev-high[u]].first;
			int r=av[u][lev-high[u]].second;
			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(int u){
	int ind=lower_bound(alll[high[u]].begin(),alll[high[u]].end(),make_pair(stf[u].first,u))-alll[high[u]].begin();
	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(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	pre(1);
	for(int i=1;i<=n;i++){
		for(int j=high[i];j<=min(high[i]+40,maxn-1);j++){
			int l=lower_bound(alll[j+high[i]].begin(),alll[j+high[i]].end(),make_pair(stf[i].first,-1))-alll[j+high[i]].begin();
			int r=lower_bound(alll[j+high[i]].begin(),alll[j+high[i]].end(),make_pair(stf[i].second+1,-1))-alll[j+high[i]].begin()-1;
			av[i][j]=make_pair(l,r);
		}
	}
	for(int i=0;i<maxn;i++){
		seg[i].sz=alll[i].size();
		seg[i].create();
	}
	for(int i=1;i<=n;i++){
		int d;
		cin>>d;
		upd(i,0,d);
	}
	cin>>q;
	for(int i=0;i<q;i++){
		int qq;
		cin>>qq;
		if(qq==1){
			int u,d,w;
			cin>>u>>d>>w;
			if(d>40){
				assert(0);
			}
			upd(u,d,w); 
		}
		else{
			int u;
			cin>>u;
			solve(u);
		}
	}
}

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