Submission #580217

#	Time	Username	Problem	Language	Result	Execution time	Memory
580217		uncripted	Sprinkler (JOI22_sprinkler)	C++11	100 / 100	1507 ms	95820 KiB

sprinkler

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

long long p[201000],a[200001];

long long d[201000][41];
vector<long long> adj[200001];
void dfs(long long x, long long par) {
	for (auto k :adj[x]){
		if (k == par) continue;
		p[k] = x;
		dfs(k , x);
	}	
}
int main(){
 
    
    long long n, md;
 cin>>n>>md;
    
    for (int i=1; i<n; i++) {
    	long long x,y; 
		cin>>x>>y;
    	adj[x].pb(y);
    	adj[y].pb(x);
	}
	
	dfs(1 , 1);
	
	p[1]=n+1;
	for(int i=n+2; i<=n+40; i++){
		p[i-1] = i;
	}
	
	for (int i=1; i<=n; i++) {
    	cin>>a[i];
	}
	
	for (int i=1; i<=n+40; i++) {
    	for (int j=0; j<=40; j++) {
    		d[i][j] = 1;
		}
	}
	
	long long q; 
	cin>>q;
	
	for (int i = 1; i <= q; i++) {
		
		long long temp; cin>>temp;
		
		if (temp == 2) {
			
			long long x , pas = 1; 
			cin>>x;
			pas = a[x];
			long long j = 0;	
			while (j <= 40) {
				pas *= d[x][j];
				pas %= md;
				x=p[x];
				j++;
			}
			cout<<pas<<endl;
			
		}else {	
			long long x, r, w; 
			cin>>x>>r>>w;
			long long j = r;
			
				
			while (j > 0) {
				
				d[x][j]*=w;
				d[x][j]%=md;
				
				d[x][j - 1]*=w;
				d[x][j - 1]%=md;
				
				//cput<<"  "<<pas<<" br"<<endl;	
				x=p[x];
				j--;
			}
			d[x][j] *= w;
			d[x][j] %= md;
			
		}
		
	}
    
}

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