oj.uz

Submission #721263

# Submission time Handle Problem Language Result Execution time Memory
721263 2023-04-10T15:04:51 Z Abrar_Al_Samit Sprinkler (JOI22_sprinkler) C++17
100 / 100
 2404 ms 95568 KB 
#include<bits/stdc++.h>
using namespace std;

const int nax = 2e5 + 3;
const int cax = 42;

vector<int>g[nax];
int n;
long long L;
long long H[nax];
long long growth[nax][cax];
int par[nax];


void dfs(int v, int p = 1) {
	par[v] = p;
	for(int u : g[v]) if(u!=p) {
		dfs(u, v);
	}
}
void update(int v, int cd, int mt) {
	if(cd<0) return;
	growth[v][cd] = (growth[v][cd] * mt) % L;

	if(v!=1) update(par[v], cd-1, mt);
}	
long long query(int v, int cd) {
	if(cd==cax) return 1LL;

	long long ret = 1LL;
	for(int j=cd; j<cax; ++j) {
		if(j-1>=cd+1 && v!=1) continue;
		ret = (ret * growth[v][j]) % L;
	}	
	if(v!=1) ret = (ret * query(par[v], cd+1)) % L;
	return ret;
}
void PlayGround() {
	cin>>n>>L;
	for(int i=0; i<n-1; ++i) {
		int u, v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}	
	for(int i=1; i<=n; ++i) {
		cin>>H[i];
	}
	for(int i=1; i<=n; ++i) {
		for(int j=0; j<cax; ++j) {
			growth[i][j] = 1;
		}
	}
	dfs(1);

	int q;
	cin>>q;
	while(q--) {
		int type;
		cin>>type;
		if(type==1) {
			int x, d, w;
			cin>>x>>d>>w;

			update(x, d, w);
		} else {
			int x;
			cin>>x;
			long long ans = query(x, 0) * H[x];
			ans %= L;
			cout<<ans<<'\n';
		}
	}

	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

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 3 ms 5024 KB Output is correct
4 Correct 5 ms 5420 KB Output is correct
5 Correct 5 ms 5448 KB Output is correct
6 Correct 4 ms 5420 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 5032 KB Output is correct
12 Correct 3 ms 5036 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 4 ms 4984 KB Output is correct
15 Correct 5 ms 4948 KB Output is correct
16 Correct 4 ms 5040 KB Output is correct
17 Correct 4 ms 5076 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5024 KB Output is correct
20 Correct 3 ms 5032 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 4 ms 5032 KB Output is correct
23 Correct 4 ms 4948 KB Output is correct
24 Correct 3 ms 4948 KB Output is correct
25 Correct 3 ms 5032 KB Output is correct
26 Correct 3 ms 4948 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 3 ms 4948 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 1767 ms 84952 KB Output is correct
3 Correct 521 ms 81780 KB Output is correct
4 Correct 1495 ms 86064 KB Output is correct
5 Correct 1151 ms 83356 KB Output is correct
6 Correct 647 ms 83256 KB Output is correct
7 Correct 598 ms 83512 KB Output is correct
8 Correct 322 ms 83928 KB Output is correct
9 Correct 2287 ms 89024 KB Output is correct
10 Correct 568 ms 85676 KB Output is correct
11 Correct 2013 ms 84860 KB Output is correct
12 Correct 503 ms 81664 KB Output is correct
13 Correct 250 ms 82316 KB Output is correct
14 Correct 278 ms 82268 KB Output is correct
15 Correct 260 ms 82280 KB Output is correct
16 Correct 298 ms 82244 KB Output is correct
17 Correct 271 ms 82944 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 4 ms 4948 KB Output is correct
20 Correct 3 ms 5036 KB Output is correct
21 Correct 5 ms 4948 KB Output is correct
22 Correct 4 ms 4948 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 1767 ms 84952 KB Output is correct
3 Correct 521 ms 81780 KB Output is correct
4 Correct 1495 ms 86064 KB Output is correct
5 Correct 1151 ms 83356 KB Output is correct
6 Correct 647 ms 83256 KB Output is correct
7 Correct 598 ms 83512 KB Output is correct
8 Correct 322 ms 83928 KB Output is correct
9 Correct 2287 ms 89024 KB Output is correct
10 Correct 568 ms 85676 KB Output is correct
11 Correct 2013 ms 84860 KB Output is correct
12 Correct 503 ms 81664 KB Output is correct
13 Correct 250 ms 82316 KB Output is correct
14 Correct 278 ms 82268 KB Output is correct
15 Correct 260 ms 82280 KB Output is correct
16 Correct 298 ms 82244 KB Output is correct
17 Correct 271 ms 82944 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 4 ms 4948 KB Output is correct
20 Correct 3 ms 5036 KB Output is correct
21 Correct 5 ms 4948 KB Output is correct
22 Correct 4 ms 4948 KB Output is correct
23 Correct 4 ms 4948 KB Output is correct
24 Correct 1824 ms 84860 KB Output is correct
25 Correct 544 ms 81688 KB Output is correct
26 Correct 1433 ms 87356 KB Output is correct
27 Correct 1061 ms 83240 KB Output is correct
28 Correct 652 ms 83436 KB Output is correct
29 Correct 567 ms 83376 KB Output is correct
30 Correct 349 ms 83972 KB Output is correct
31 Correct 2300 ms 87764 KB Output is correct
32 Correct 567 ms 85676 KB Output is correct
33 Correct 1809 ms 84840 KB Output is correct
34 Correct 571 ms 81696 KB Output is correct
35 Correct 3 ms 4948 KB Output is correct
36 Correct 3 ms 4956 KB Output is correct
37 Correct 4 ms 4948 KB Output is correct
38 Correct 5 ms 5036 KB Output is correct
39 Correct 4 ms 4948 KB Output is correct
40 Correct 3 ms 5028 KB Output is correct
41 Correct 3 ms 4948 KB Output is correct
42 Correct 4 ms 5056 KB Output is correct
43 Correct 3 ms 5076 KB Output is correct
44 Correct 4 ms 4948 KB Output is correct
45 Correct 4 ms 4948 KB Output is correct
46 Correct 4 ms 4948 KB Output is correct
47 Correct 3 ms 5036 KB Output is correct
48 Correct 3 ms 4948 KB Output is correct
49 Correct 3 ms 5032 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5024 KB Output is correct
2 Correct 2287 ms 86708 KB Output is correct
3 Correct 812 ms 84696 KB Output is correct
4 Correct 1513 ms 85280 KB Output is correct
5 Correct 1323 ms 81756 KB Output is correct
6 Correct 712 ms 81860 KB Output is correct
7 Correct 535 ms 82136 KB Output is correct
8 Correct 337 ms 82540 KB Output is correct
9 Correct 2332 ms 85524 KB Output is correct
10 Correct 894 ms 85520 KB Output is correct
11 Correct 1841 ms 82324 KB Output is correct
12 Correct 713 ms 81492 KB Output is correct
13 Correct 432 ms 82448 KB Output is correct
14 Correct 428 ms 82844 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 5032 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4932 KB Output is correct
19 Correct 4 ms 5028 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5024 KB Output is correct
2 Correct 2404 ms 87840 KB Output is correct
3 Correct 838 ms 84060 KB Output is correct
4 Correct 1561 ms 86048 KB Output is correct
5 Correct 1188 ms 83476 KB Output is correct
6 Correct 672 ms 83552 KB Output is correct
7 Correct 610 ms 83472 KB Output is correct
8 Correct 344 ms 83996 KB Output is correct
9 Correct 2311 ms 88960 KB Output is correct
10 Correct 764 ms 85844 KB Output is correct
11 Correct 1761 ms 85068 KB Output is correct
12 Correct 656 ms 81840 KB Output is correct
13 Correct 408 ms 82640 KB Output is correct
14 Correct 423 ms 82992 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5028 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 4 ms 5032 KB Output is correct
19 Correct 3 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 3 ms 5024 KB Output is correct
4 Correct 5 ms 5420 KB Output is correct
5 Correct 5 ms 5448 KB Output is correct
6 Correct 4 ms 5420 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 5032 KB Output is correct
12 Correct 3 ms 5036 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 4 ms 4984 KB Output is correct
15 Correct 5 ms 4948 KB Output is correct
16 Correct 4 ms 5040 KB Output is correct
17 Correct 4 ms 5076 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5024 KB Output is correct
20 Correct 3 ms 5032 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 4 ms 5032 KB Output is correct
23 Correct 4 ms 4948 KB Output is correct
24 Correct 3 ms 4948 KB Output is correct
25 Correct 3 ms 5032 KB Output is correct
26 Correct 3 ms 4948 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 3 ms 4948 KB Output is correct
29 Correct 3 ms 4948 KB Output is correct
30 Correct 1767 ms 84952 KB Output is correct
31 Correct 521 ms 81780 KB Output is correct
32 Correct 1495 ms 86064 KB Output is correct
33 Correct 1151 ms 83356 KB Output is correct
34 Correct 647 ms 83256 KB Output is correct
35 Correct 598 ms 83512 KB Output is correct
36 Correct 322 ms 83928 KB Output is correct
37 Correct 2287 ms 89024 KB Output is correct
38 Correct 568 ms 85676 KB Output is correct
39 Correct 2013 ms 84860 KB Output is correct
40 Correct 503 ms 81664 KB Output is correct
41 Correct 250 ms 82316 KB Output is correct
42 Correct 278 ms 82268 KB Output is correct
43 Correct 260 ms 82280 KB Output is correct
44 Correct 298 ms 82244 KB Output is correct
45 Correct 271 ms 82944 KB Output is correct
46 Correct 3 ms 4948 KB Output is correct
47 Correct 4 ms 4948 KB Output is correct
48 Correct 3 ms 5036 KB Output is correct
49 Correct 5 ms 4948 KB Output is correct
50 Correct 4 ms 4948 KB Output is correct
51 Correct 4 ms 4948 KB Output is correct
52 Correct 1824 ms 84860 KB Output is correct
53 Correct 544 ms 81688 KB Output is correct
54 Correct 1433 ms 87356 KB Output is correct
55 Correct 1061 ms 83240 KB Output is correct
56 Correct 652 ms 83436 KB Output is correct
57 Correct 567 ms 83376 KB Output is correct
58 Correct 349 ms 83972 KB Output is correct
59 Correct 2300 ms 87764 KB Output is correct
60 Correct 567 ms 85676 KB Output is correct
61 Correct 1809 ms 84840 KB Output is correct
62 Correct 571 ms 81696 KB Output is correct
63 Correct 3 ms 4948 KB Output is correct
64 Correct 3 ms 4956 KB Output is correct
65 Correct 4 ms 4948 KB Output is correct
66 Correct 5 ms 5036 KB Output is correct
67 Correct 4 ms 4948 KB Output is correct
68 Correct 3 ms 5028 KB Output is correct
69 Correct 3 ms 4948 KB Output is correct
70 Correct 4 ms 5056 KB Output is correct
71 Correct 3 ms 5076 KB Output is correct
72 Correct 4 ms 4948 KB Output is correct
73 Correct 4 ms 4948 KB Output is correct
74 Correct 4 ms 4948 KB Output is correct
75 Correct 3 ms 5036 KB Output is correct
76 Correct 3 ms 4948 KB Output is correct
77 Correct 3 ms 5032 KB Output is correct
78 Correct 3 ms 5024 KB Output is correct
79 Correct 2287 ms 86708 KB Output is correct
80 Correct 812 ms 84696 KB Output is correct
81 Correct 1513 ms 85280 KB Output is correct
82 Correct 1323 ms 81756 KB Output is correct
83 Correct 712 ms 81860 KB Output is correct
84 Correct 535 ms 82136 KB Output is correct
85 Correct 337 ms 82540 KB Output is correct
86 Correct 2332 ms 85524 KB Output is correct
87 Correct 894 ms 85520 KB Output is correct
88 Correct 1841 ms 82324 KB Output is correct
89 Correct 713 ms 81492 KB Output is correct
90 Correct 432 ms 82448 KB Output is correct
91 Correct 428 ms 82844 KB Output is correct
92 Correct 3 ms 4948 KB Output is correct
93 Correct 4 ms 5032 KB Output is correct
94 Correct 3 ms 4948 KB Output is correct
95 Correct 3 ms 4932 KB Output is correct
96 Correct 4 ms 5028 KB Output is correct
97 Correct 3 ms 5024 KB Output is correct
98 Correct 2404 ms 87840 KB Output is correct
99 Correct 838 ms 84060 KB Output is correct
100 Correct 1561 ms 86048 KB Output is correct
101 Correct 1188 ms 83476 KB Output is correct
102 Correct 672 ms 83552 KB Output is correct
103 Correct 610 ms 83472 KB Output is correct
104 Correct 344 ms 83996 KB Output is correct
105 Correct 2311 ms 88960 KB Output is correct
106 Correct 764 ms 85844 KB Output is correct
107 Correct 1761 ms 85068 KB Output is correct
108 Correct 656 ms 81840 KB Output is correct
109 Correct 408 ms 82640 KB Output is correct
110 Correct 423 ms 82992 KB Output is correct
111 Correct 3 ms 4948 KB Output is correct
112 Correct 3 ms 5028 KB Output is correct
113 Correct 3 ms 4948 KB Output is correct
114 Correct 4 ms 5032 KB Output is correct
115 Correct 3 ms 4948 KB Output is correct
116 Correct 1779 ms 89328 KB Output is correct
117 Correct 666 ms 91764 KB Output is correct
118 Correct 1470 ms 95568 KB Output is correct
119 Correct 1146 ms 91452 KB Output is correct
120 Correct 665 ms 91056 KB Output is correct
121 Correct 645 ms 91900 KB Output is correct
122 Correct 355 ms 92308 KB Output is correct
123 Correct 2240 ms 94616 KB Output is correct
124 Correct 802 ms 94112 KB Output is correct
125 Correct 1602 ms 90344 KB Output is correct
126 Correct 726 ms 91648 KB Output is correct
127 Correct 642 ms 92204 KB Output is correct
128 Correct 455 ms 92936 KB Output is correct
129 Correct 474 ms 93544 KB Output is correct