oj.uz

Submission #580644

# Submission time Handle Problem Language Result Execution time Memory
580644 2022-06-21T14:53:47 Z otonozadze Sprinkler (JOI22_sprinkler) C++14
9 / 100
 1210 ms 93960 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;
    	p[1]=-1;
    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];
	}
	dfs(1,1);
	

	

	
	for (long long i=1; i<=n; i++) {
    	for (long long 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.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 992 ms 89432 KB Output is correct
3 Correct 396 ms 86196 KB Output is correct
4 Correct 721 ms 90612 KB Output is correct
5 Correct 700 ms 87884 KB Output is correct
6 Correct 591 ms 87864 KB Output is correct
7 Correct 599 ms 88232 KB Output is correct
8 Correct 488 ms 88464 KB Output is correct
9 Correct 1210 ms 93960 KB Output is correct
10 Correct 430 ms 90484 KB Output is correct
11 Correct 1010 ms 89604 KB Output is correct
12 Correct 446 ms 86228 KB Output is correct
13 Correct 290 ms 86652 KB Output is correct
14 Correct 286 ms 86756 KB Output is correct
15 Correct 294 ms 86564 KB Output is correct
16 Correct 292 ms 86496 KB Output is correct
17 Correct 305 ms 87116 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 4 ms 4948 KB Output is correct
20 Correct 4 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 992 ms 89432 KB Output is correct
3 Correct 396 ms 86196 KB Output is correct
4 Correct 721 ms 90612 KB Output is correct
5 Correct 700 ms 87884 KB Output is correct
6 Correct 591 ms 87864 KB Output is correct
7 Correct 599 ms 88232 KB Output is correct
8 Correct 488 ms 88464 KB Output is correct
9 Correct 1210 ms 93960 KB Output is correct
10 Correct 430 ms 90484 KB Output is correct
11 Correct 1010 ms 89604 KB Output is correct
12 Correct 446 ms 86228 KB Output is correct
13 Correct 290 ms 86652 KB Output is correct
14 Correct 286 ms 86756 KB Output is correct
15 Correct 294 ms 86564 KB Output is correct
16 Correct 292 ms 86496 KB Output is correct
17 Correct 305 ms 87116 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 4 ms 4948 KB Output is correct
20 Correct 4 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 1016 ms 89420 KB Output is correct
25 Correct 444 ms 86468 KB Output is correct
26 Correct 744 ms 92256 KB Output is correct
27 Correct 689 ms 87860 KB Output is correct
28 Correct 576 ms 87976 KB Output is correct
29 Correct 543 ms 88008 KB Output is correct
30 Correct 485 ms 88376 KB Output is correct
31 Correct 1022 ms 92384 KB Output is correct
32 Correct 423 ms 90644 KB Output is correct
33 Correct 966 ms 89452 KB Output is correct
34 Correct 407 ms 86272 KB Output is correct
35 Incorrect 3 ms 4948 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -