Submission #1123631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123631		nikolashami	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	1673 ms	91720 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
const int N=2e5+44;
int f[N][44],par[N],h[N],n,q,mod;
vector<int>g[N];

void dfs(int u,int p){
	par[u]=p;
	for(int v:g[u])
		if(v^p)dfs(v,u);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>mod;
    for(int i=1,u,v;i<n;++i){
    	cin>>u>>v;
    	g[u].push_back(v);
    	g[v].push_back(u);
    }

    for(int i=1;i<=n;++i)
    	cin>>h[i];

    dfs(1,0);

    for(int i=1;i<=n+40;++i){
    	for(int j=0;j<=40;++j)
    		f[i][j]=1;
    }

    par[1]=n+1;
    for(int i=n+1;i<=n+42;++i)
    	par[i]=i+1;

    cin>>q;
    while(q--){
    	int tp;
    	cin>>tp;
    	if(tp==2){
    		int u,hummer;
    		cin>>u;
    		hummer=h[u];
    		for(int i=0;i<=40&&u;++i){
    			hummer*=(f[u][i]);
    			hummer%=mod;
    			u=par[u];
    		}
    		cout<<hummer<<'\n';
    	}else{
    		int u,d,w;
    		cin>>u>>d>>w;
    		while(d>=0&&u){
    			f[u][d]*=w;
    			if(d)f[u][d-1]*=w;
    			f[u][d]%=mod;
    			if(d)f[u][d-1]%=mod;
    			--d;
    			u=par[u];
    		}
    	}
    }
}

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