Submission #1274455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274455		coderpemula	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	633 ms	88712 KiB

sprinkler

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;
vector<int>v[200001];
int par[200001],dp[200001][42];

// 0 = left, 1 = right
void dfs(int node){
	for(auto x:v[node]){
		if(x == par[node]) continue;
		par[x] = node;
		dfs(x);
	}
}
signed main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int i,j,t,x,d,qt,n,mod;
	cin>>n>>mod;
	int anu[n+1];
	for(i=1;i<=n;i++){
		for(j=0;j<=41;j++) dp[i][j] = 1;
	}
	for(i=1;i<n;i++){
		cin>>j>>t;
		v[j].pb(t);
		v[t].pb(j);
	}
	for(i=1;i<=n;i++) cin>>anu[i];
	par[1] = 0;
	dfs(1);
	cin>>qt;
	while(qt--){
		cin>>t;
		if(t == 1){
			cin>>x>>d>>j;
			while(true){
				dp[x][d] = dp[x][d]*j%mod;
				if(x == 1 or d == 0) break;
				d--;
				x = par[x];
			}
		}
		else{
			cin>>x;
			int dst = 0,ans=anu[x];
			while(true){
				if(dst > 40) break;
				if(x == 1){
					for(i=dst;i<=40;i++) ans = ans*dp[x][i]%mod;
					break;
				}
				ans = ans*dp[x][dst]%mod*dp[x][dst+1]%mod;
				dst++;
				x = par[x];
			}
			cout<<ans<<"\n";
		}
	}
	
	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