Submission #580669

#	Time	Username	Problem	Language	Result	Execution time	Memory
580669		otonozadze	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	1252 ms	102516 KiB

sprinkler

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const long long 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(){
 	ios::sync_with_stdio(false);
    
    long long n, md;
 cin>>n>>md;
    
    for (long long i=1; i<n; i++) {
    	long long x,y; 
		cin>>x>>y;
	adj[x].pb(y);
    	adj[y].pb(x);
	}
	for (long long i=1; i<=n; i++) {
    	cin>>a[i];
	}

	

	

		p[1]=n+1;
	for (long long i=1; i<=n+45; i++) {
    	for (long long j=0; j<=40; j++) {
    		up[i][j] = 1;
    		if(i>=n+1){
    			p[i]=i+1;
			}
    		
}
	}

		dfs(1,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];
			
				//	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];
			
				
			}
			cout<<pas<<endl;
			
		}
		
	}
    
}

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