Submission #580643

#	Time	Username	Problem	Language	Result	Execution time	Memory
580643		otonozadze	Sprinkler (JOI22_sprinkler)	C++14	9 / 100	1490 ms	102288 KiB

sprinkler

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int siz=225000;
long long a[siz],p[siz];
long long up[siz][45];
vector<long long> adj[200001];
void dfs(long long x, long long par) {
	for (auto xd:adj[x]){
		if (xd==par){
			 continue;
		}	
		dfs(xd , x);
		p[xd]=x;
	
	}	
}
int main(){
 
    
    long long n, md;
 cin>>n>>md;
    	p[1]=-1;
    for (int i=1; i<n; i++) {
    	long long x,y; 
		cin>>x>>y;
	adj[x].pb(y);
    	adj[y].pb(x);
	}
	for (int i=1; i<=n; i++) {
    	cin>>a[i];
	}
	dfs(1,1);
	

	

	
	for (int i=1; i<=n+40; i++) {
    	for (int j=0; j<=40; j++) {
    		up[i][j] = 1;
}
	}
	
	long long q; 
	cin>>q;
	
while(q--){

		
		long long temp; 
		cin>>temp;
		
		if (temp==1) {
			
		long long x, dis, w; 
			cin>>x>>dis>>w;
		
			
				
			while (dis>=0) {	
	//		cout<<"x"<<x<<" up"<<up[x][dis]<<endl;
				up[x][dis]=(w*up[x][dis])%md;
				if(dis>0){
					up[x][dis-1]=(w*up[x][dis-1])%md;
				}
					x=p[x];
					if(x==-1){
						break;
					}
				//	cout<<dis<<endl;
				dis--;
			}
		}else {	
		//cout<<"  "<<pas<<" br"<<" meore"<<endl;
			long long x;
			long long pas=1; 
			cin>>x;
			pas=a[x];
			long long j=0;	
			while (j<=40) {
				pas=(pas*(up[x][j])%md)%md;
				
				j++;
				x=p[x];
				if(x==-1){
					break;
				}
				
			}
			cout<<pas<<endl;
			
		}
		
	}
    
}

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