Submission #966762

#	Time	Username	Problem	Language	Result	Execution time	Memory
966762		PM1	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	3913 ms	129028 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
const int mxn=2e5+5;
int n,M,q,st[mxn],fn[mxn],cnt,dis[mxn],par[mxn],w;
pair<int,int> fnd[mxn][42];
vector<int>v[mxn],d[mxn];
struct segment{
	vector<long long>val;
	int sz=0;
	void build(){
		while(__builtin_popcount(sz)!=1){
			sz++;
		}
		val.resize(sz*2,1);
	}
	void add(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			val[i]*=w;
			val[i]%=M;
			return ;
		}
		int m=(l+r)>>1;
		add((i<<1),l,m,tl,tr);
		add((i<<1)^1,m+1,r,tl,tr);
		return ;
	}
	int get(int i){
		if(i==0){
			return 1;
		}
		int ret=val[i]*get((i>>1))%M;
		return ret;
	}
}seg[mxn];
void dfs(int z){
	st[z]=++cnt;
	d[dis[z]].push_back(st[z]);
	for(auto i:v[z]){
		if(i!=par[z]){
			par[i]=z;
			dis[i]=dis[z]+1;
			dfs(i);
		}
	}
	fn[z]=cnt;
}
void up(int x,int dd){
	int z=0;
	dd+=dis[x];
	while(dd>=dis[x]){
		if(dd<mxn){
			int l=fnd[x][dd-dis[x]].first;
			int r=fnd[x][dd-dis[x]].second;
			seg[dd].add(1,0,seg[dd].sz-1,l,r);
		}
		if(z)
			x=par[x];
		z^=1;
		dd--;
	}
}
void get(int z,int x){
	int l=fnd[x][0].first;
	cout<<seg[z].get(l+seg[z].sz)<<'\n';
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>M;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	par[1]=1;
	dfs(1);
	for(int i=0;i<=n;i++){
		seg[i].sz=d[i].size();
		seg[i].build();
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=40 && dis[i]+j<mxn;j++){
			int dd=dis[i]+j;
			fnd[i][j].first=lower_bound(d[dd].begin(),d[dd].end(),st[i])-d[dd].begin();
			fnd[i][j].second=upper_bound(d[dd].begin(),d[dd].end(),fn[i])-d[dd].begin()-1;
		}
	}
	for(int i=1;i<=n;i++){
		int l=fnd[i][0].first;
		cin>>w;
		seg[dis[i]].add(1,0,seg[dis[i]].sz-1,l,l);
	}
	cin>>q;
	while(q--){
		int ty,x,dd;
		cin>>ty;
		if(ty==1){
			cin>>x>>dd>>w;
			up(x,dd);
		}

		else{
			cin>>x;
			get(dis[x],x);
		}
		
	}
	return 0;
}

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