oj.uz

Submission #580646

# Submission time Handle Problem Language Result Execution time Memory
580646 2022-06-21T14:57:08 Z otonozadze Sprinkler (JOI22_sprinkler) C++14
0 / 100
 1242 ms 89416 KB 
#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;
    		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];
					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.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 1242 ms 89416 KB Output is correct
3 Incorrect 497 ms 86324 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 1242 ms 89416 KB Output is correct
3 Incorrect 497 ms 86324 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -