Submission #1208348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208348		emptypringlescan	Sprinkler (JOI22_sprinkler)	C++17	3 / 100	926 ms	138336 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
int n;
long long mod;
vector<long long> fenw[400005][3];
void update(int o, int u, int x, long long v){
	x=(int)fenw[o][u].size()-x-1;
	x=max(x,1);
	for(;x<(int)fenw[o][u].size(); x+=x&-x){
		fenw[o][u][x]=fenw[o][u][x]*v%mod;
	}
}
long long query(int o, int u, int x){
	x=(int)fenw[o][u].size()-x-1;
	x=min(x,(int)fenw[o][u].size()-1);
	long long ret=1;
	for(;x; x-=x&-x){
		ret=ret*fenw[o][u][x]%mod;
	}
	return ret;
}
vector<int> og[200005];
vector<pair<int,int> > adj[400005];
long long arr[200005];
int cnt;
void bin(int x, int p){
	int d=x;
	int num=0;
	for(int i:og[x]){
		if(i==p) continue;
		num++;
		if(num==1){
			adj[x].push_back({i,1});
			adj[i].push_back({x,1});
			bin(i,x);
		}
		else{
			adj[cnt].push_back({d,0});
			adj[d].push_back({cnt,0});
			adj[cnt].push_back({i,1});
			adj[i].push_back({cnt,1});
			d=cnt;
			cnt++;
			bin(i,x);
		}
	}
}
int sz[400005],dt[20][400005],lvl[400005],hei[400005],del[400005];
pair<int,int> par[400005];
int dfssize(int x, int p){
	sz[x]=1;
	for(pair<int,int> i:adj[x]){
		if(i.first==p||del[i.first]) continue;
		sz[x]+=dfssize(i.first,x);
	}
	return sz[x];
}
int findcent(int x, int p, int tsz){
	for(auto i:adj[x]){
		if(i.first==p||del[i.first]) continue;
		if(sz[i.first]*2>tsz) return findcent(i.first,x,tsz);
	}
	return x;
}
int dfscent(int x, int p, int l, int d){
	dt[l][x]=d;
	int ret=1;
	for(auto i:adj[x]){
		if(i.first==p||del[i.first]) continue;
		ret=max(dfscent(i.first,x,l,d+i.second)+i.second,ret);
	}
	return ret;
}
int decomp(int x, int l){
	x=findcent(x,-1,dfssize(x,-1));
	del[x]=1;
	lvl[x]=l;
	hei[x]=1;
	int ind=-1;
	for(auto i:adj[x]){
		ind++;
		if(del[i.first]) continue;
		int h=dfscent(i.first,x,l,i.second)+i.second;
		for(int i=0; i<h+5; i++) fenw[x][ind].push_back(1);
		hei[x]=max(hei[x],h);
	}
	ind=-1;
	for(auto i:adj[x]){
		ind++;
		if(del[i.first]) continue;
		int kid=decomp(i.first,l+1);
		par[kid]={x,ind};
	}
	return x;
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> mod;
	for(int i=0; i<n-1; i++){
		int a,b;
		cin >> a >> b;
		og[a].push_back(b);
		og[b].push_back(a);
	}
	for(int i=1; i<=n; i++) cin >> arr[i];
	cnt=n+1;
	bin(1,-1);
	assert(cnt<400005);
	n=cnt-1;
	for(int i=1; i<=n; i++) assert(1<=(int)adj[i].size()&&(int)adj[i].size()<=3);
	int rt=decomp(1,0);
	par[rt]={-1,-1};
	int q;
	cin >> q;
	while(q--){
		int cmd;
		cin >> cmd;
		if(cmd==1){
			int x,d;
			long long k;
			cin >> x >> d >> k;
			int l=lvl[x],cur=x;
			int prev=-1;
			while(l!=-1){
				if(dt[l][x]<=d){
					arr[cur]=arr[cur]*k%mod;
					for(int i=0; i<(int)adj[cur].size(); i++){
						if(i==prev) continue;
						//cout << cur << ' ' << i << ' ' << d-dt[l][x] << '\n';
						update(cur,i,d-dt[l][x],k);
					}
					//cout << "UPD " << cur << ' ' << d-dt[l][x] << ' ' << k << '\n';
				}
				l--;
				prev=par[cur].second;
				cur=par[cur].first;
			}
		}
		else{
			int x;
			cin >> x;
			long long ans=arr[x];
			int l=lvl[x],cur=x,prev=-1;
			while(l!=0){
				l--;
				prev=par[cur].second;
				cur=par[cur].first;
				ans=ans*query(cur,prev,dt[l][x])%mod;
				//cout << "MULT " << cur << ' ' << dt[l][x] << ' ' << query(cur,prev,dt[l][x]) << '\n';
			}
			cout << ans << '\n';
		}
	}
}

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