oj.uz

Submission #574874

# Submission time Handle Problem Language Result Execution time Memory
574874 2022-06-09T12:42:24 Z MateGiorbelidze Sprinkler (JOI22_sprinkler) C++14
100 / 100
 987 ms 95760 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define sc second
#define pb push_back
#define in insert

ll p[201000] , h[200001] , d[201000][41];
vector<ll> g[200001];

void dfs(ll v, ll par) {
	for (auto k :g[v]){
		if (k == par) continue;
		p[k] = v;
		dfs(k , v);
	}
	
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n, mod; cin>>n>>mod;
    
    for (int i = 1; i < n; i++) {
    	ll u , v; cin>>u>>v;
    	g[u].pb(v);
    	g[v].pb(u);
	}
	
	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>>h[i];
	}
	
	for (int i = 1; i <= n + 40; i++) {
    	for (int j = 0; j <= 40; j++) {
    		d[i][j] = 1;
		}
	}
	
	ll q; cin>>q;
	
	for (int o = 1; o <= q; o++) {
		
		ll tp; cin>>tp;
		
		if (tp == 2) {
			
			ll v , ans = 1; cin>>v;
			
			ans = h[v];
			
			ll j = 0;
			
			while (j <= 40) {
				
				ans *= d[v][j];
				ans %= mod;
				
				v = p[v];
				j++;
			}
			
			cout<<ans<<"\n";
			
		}
		else {
			
			ll v, r, mul; cin>>v>>r>>mul;
			
			
			ll j = r;
			
			while (j > 0) {
				
				d[v][j] *= mul;
				d[v][j] %= mod;
				
				d[v][j - 1] *= mul;
				d[v][j - 1] %= mod;
				
				v = p[v];
				j--;
			}
			d[v][j] *= mul;
			d[v][j] %= mod;
			
		}
		
	}
    
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 4 ms 5460 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 5 ms 5424 KB Output is correct
8 Correct 4 ms 5404 KB Output is correct
9 Correct 3 ms 5036 KB Output is correct
10 Correct 3 ms 5036 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 4 ms 5032 KB Output is correct
15 Correct 3 ms 5036 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5028 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 5032 KB Output is correct
22 Correct 4 ms 4948 KB Output is correct
23 Correct 3 ms 5036 KB Output is correct
24 Correct 3 ms 5024 KB Output is correct
25 Correct 3 ms 5076 KB Output is correct
26 Correct 3 ms 5024 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 3 ms 5028 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 552 ms 83260 KB Output is correct
3 Correct 357 ms 91868 KB Output is correct
4 Correct 521 ms 93936 KB Output is correct
5 Correct 509 ms 91620 KB Output is correct
6 Correct 434 ms 90664 KB Output is correct
7 Correct 358 ms 92000 KB Output is correct
8 Correct 346 ms 92304 KB Output is correct
9 Correct 675 ms 95524 KB Output is correct
10 Correct 447 ms 95624 KB Output is correct
11 Correct 585 ms 90828 KB Output is correct
12 Correct 403 ms 91920 KB Output is correct
13 Correct 262 ms 91960 KB Output is correct
14 Correct 266 ms 92392 KB Output is correct
15 Correct 257 ms 90564 KB Output is correct
16 Correct 258 ms 92168 KB Output is correct
17 Correct 291 ms 91928 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 4 ms 5036 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 552 ms 83260 KB Output is correct
3 Correct 357 ms 91868 KB Output is correct
4 Correct 521 ms 93936 KB Output is correct
5 Correct 509 ms 91620 KB Output is correct
6 Correct 434 ms 90664 KB Output is correct
7 Correct 358 ms 92000 KB Output is correct
8 Correct 346 ms 92304 KB Output is correct
9 Correct 675 ms 95524 KB Output is correct
10 Correct 447 ms 95624 KB Output is correct
11 Correct 585 ms 90828 KB Output is correct
12 Correct 403 ms 91920 KB Output is correct
13 Correct 262 ms 91960 KB Output is correct
14 Correct 266 ms 92392 KB Output is correct
15 Correct 257 ms 90564 KB Output is correct
16 Correct 258 ms 92168 KB Output is correct
17 Correct 291 ms 91928 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 4 ms 5036 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 653 ms 91428 KB Output is correct
25 Correct 486 ms 91936 KB Output is correct
26 Correct 572 ms 95760 KB Output is correct
27 Correct 535 ms 91652 KB Output is correct
28 Correct 417 ms 91732 KB Output is correct
29 Correct 418 ms 91508 KB Output is correct
30 Correct 396 ms 92284 KB Output is correct
31 Correct 656 ms 94160 KB Output is correct
32 Correct 451 ms 95708 KB Output is correct
33 Correct 647 ms 91420 KB Output is correct
34 Correct 499 ms 91824 KB Output is correct
35 Correct 3 ms 4948 KB Output is correct
36 Correct 4 ms 5076 KB Output is correct
37 Correct 3 ms 5076 KB Output is correct
38 Correct 4 ms 5076 KB Output is correct
39 Correct 3 ms 5008 KB Output is correct
40 Correct 3 ms 5032 KB Output is correct
41 Correct 4 ms 4948 KB Output is correct
42 Correct 3 ms 4948 KB Output is correct
43 Correct 4 ms 5032 KB Output is correct
44 Correct 3 ms 4948 KB Output is correct
45 Correct 4 ms 4948 KB Output is correct
46 Correct 3 ms 4948 KB Output is correct
47 Correct 4 ms 5076 KB Output is correct
48 Correct 3 ms 4948 KB Output is correct
49 Correct 4 ms 5028 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5016 KB Output is correct
2 Correct 701 ms 85504 KB Output is correct
3 Correct 817 ms 92264 KB Output is correct
4 Correct 596 ms 91892 KB Output is correct
5 Correct 563 ms 88780 KB Output is correct
6 Correct 424 ms 88816 KB Output is correct
7 Correct 403 ms 89032 KB Output is correct
8 Correct 308 ms 89344 KB Output is correct
9 Correct 685 ms 91216 KB Output is correct
10 Correct 796 ms 92840 KB Output is correct
11 Correct 658 ms 88296 KB Output is correct
12 Correct 741 ms 89232 KB Output is correct
13 Correct 430 ms 90204 KB Output is correct
14 Correct 449 ms 90988 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 5 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 829 ms 86680 KB Output is correct
3 Correct 987 ms 91300 KB Output is correct
4 Correct 686 ms 92352 KB Output is correct
5 Correct 629 ms 90260 KB Output is correct
6 Correct 488 ms 90596 KB Output is correct
7 Correct 426 ms 90228 KB Output is correct
8 Correct 344 ms 90296 KB Output is correct
9 Correct 735 ms 94932 KB Output is correct
10 Correct 770 ms 93632 KB Output is correct
11 Correct 644 ms 91212 KB Output is correct
12 Correct 607 ms 89428 KB Output is correct
13 Correct 398 ms 90216 KB Output is correct
14 Correct 441 ms 91120 KB Output is correct
15 Correct 4 ms 5032 KB Output is correct
16 Correct 3 ms 5028 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 4 ms 4948 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 4 ms 5460 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 5 ms 5424 KB Output is correct
8 Correct 4 ms 5404 KB Output is correct
9 Correct 3 ms 5036 KB Output is correct
10 Correct 3 ms 5036 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 4 ms 5032 KB Output is correct
15 Correct 3 ms 5036 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5028 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 5032 KB Output is correct
22 Correct 4 ms 4948 KB Output is correct
23 Correct 3 ms 5036 KB Output is correct
24 Correct 3 ms 5024 KB Output is correct
25 Correct 3 ms 5076 KB Output is correct
26 Correct 3 ms 5024 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 3 ms 5028 KB Output is correct
29 Correct 3 ms 4948 KB Output is correct
30 Correct 552 ms 83260 KB Output is correct
31 Correct 357 ms 91868 KB Output is correct
32 Correct 521 ms 93936 KB Output is correct
33 Correct 509 ms 91620 KB Output is correct
34 Correct 434 ms 90664 KB Output is correct
35 Correct 358 ms 92000 KB Output is correct
36 Correct 346 ms 92304 KB Output is correct
37 Correct 675 ms 95524 KB Output is correct
38 Correct 447 ms 95624 KB Output is correct
39 Correct 585 ms 90828 KB Output is correct
40 Correct 403 ms 91920 KB Output is correct
41 Correct 262 ms 91960 KB Output is correct
42 Correct 266 ms 92392 KB Output is correct
43 Correct 257 ms 90564 KB Output is correct
44 Correct 258 ms 92168 KB Output is correct
45 Correct 291 ms 91928 KB Output is correct
46 Correct 3 ms 5076 KB Output is correct
47 Correct 4 ms 5036 KB Output is correct
48 Correct 3 ms 4948 KB Output is correct
49 Correct 3 ms 5076 KB Output is correct
50 Correct 3 ms 5076 KB Output is correct
51 Correct 3 ms 4948 KB Output is correct
52 Correct 653 ms 91428 KB Output is correct
53 Correct 486 ms 91936 KB Output is correct
54 Correct 572 ms 95760 KB Output is correct
55 Correct 535 ms 91652 KB Output is correct
56 Correct 417 ms 91732 KB Output is correct
57 Correct 418 ms 91508 KB Output is correct
58 Correct 396 ms 92284 KB Output is correct
59 Correct 656 ms 94160 KB Output is correct
60 Correct 451 ms 95708 KB Output is correct
61 Correct 647 ms 91420 KB Output is correct
62 Correct 499 ms 91824 KB Output is correct
63 Correct 3 ms 4948 KB Output is correct
64 Correct 4 ms 5076 KB Output is correct
65 Correct 3 ms 5076 KB Output is correct
66 Correct 4 ms 5076 KB Output is correct
67 Correct 3 ms 5008 KB Output is correct
68 Correct 3 ms 5032 KB Output is correct
69 Correct 4 ms 4948 KB Output is correct
70 Correct 3 ms 4948 KB Output is correct
71 Correct 4 ms 5032 KB Output is correct
72 Correct 3 ms 4948 KB Output is correct
73 Correct 4 ms 4948 KB Output is correct
74 Correct 3 ms 4948 KB Output is correct
75 Correct 4 ms 5076 KB Output is correct
76 Correct 3 ms 4948 KB Output is correct
77 Correct 4 ms 5028 KB Output is correct
78 Correct 3 ms 5016 KB Output is correct
79 Correct 701 ms 85504 KB Output is correct
80 Correct 817 ms 92264 KB Output is correct
81 Correct 596 ms 91892 KB Output is correct
82 Correct 563 ms 88780 KB Output is correct
83 Correct 424 ms 88816 KB Output is correct
84 Correct 403 ms 89032 KB Output is correct
85 Correct 308 ms 89344 KB Output is correct
86 Correct 685 ms 91216 KB Output is correct
87 Correct 796 ms 92840 KB Output is correct
88 Correct 658 ms 88296 KB Output is correct
89 Correct 741 ms 89232 KB Output is correct
90 Correct 430 ms 90204 KB Output is correct
91 Correct 449 ms 90988 KB Output is correct
92 Correct 3 ms 4948 KB Output is correct
93 Correct 5 ms 4948 KB Output is correct
94 Correct 3 ms 4948 KB Output is correct
95 Correct 4 ms 4948 KB Output is correct
96 Correct 3 ms 4948 KB Output is correct
97 Correct 4 ms 4948 KB Output is correct
98 Correct 829 ms 86680 KB Output is correct
99 Correct 987 ms 91300 KB Output is correct
100 Correct 686 ms 92352 KB Output is correct
101 Correct 629 ms 90260 KB Output is correct
102 Correct 488 ms 90596 KB Output is correct
103 Correct 426 ms 90228 KB Output is correct
104 Correct 344 ms 90296 KB Output is correct
105 Correct 735 ms 94932 KB Output is correct
106 Correct 770 ms 93632 KB Output is correct
107 Correct 644 ms 91212 KB Output is correct
108 Correct 607 ms 89428 KB Output is correct
109 Correct 398 ms 90216 KB Output is correct
110 Correct 441 ms 91120 KB Output is correct
111 Correct 4 ms 5032 KB Output is correct
112 Correct 3 ms 5028 KB Output is correct
113 Correct 3 ms 5076 KB Output is correct
114 Correct 3 ms 5076 KB Output is correct
115 Correct 4 ms 4948 KB Output is correct
116 Correct 678 ms 89492 KB Output is correct
117 Correct 755 ms 92008 KB Output is correct
118 Correct 697 ms 95712 KB Output is correct
119 Correct 701 ms 91728 KB Output is correct
120 Correct 501 ms 91396 KB Output is correct
121 Correct 470 ms 92180 KB Output is correct
122 Correct 427 ms 92204 KB Output is correct
123 Correct 799 ms 94592 KB Output is correct
124 Correct 770 ms 93924 KB Output is correct
125 Correct 614 ms 90668 KB Output is correct
126 Correct 663 ms 91960 KB Output is correct
127 Correct 700 ms 92444 KB Output is correct
128 Correct 546 ms 93076 KB Output is correct
129 Correct 560 ms 93920 KB Output is correct