oj.uz

Submission #689332

# Submission time Handle Problem Language Result Execution time Memory
689332 2023-01-28T08:10:48 Z happypotato Sprinkler (JOI22_sprinkler) C++17
100 / 100
 1320 ms 61176 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5;
const int mxD = 40;
int contrib[mxN + 1][mxD + 1];
vector<int> adj[mxN + 1];
int height[mxN + 1];
int n, L;
void Init() {
	for (int i = 1; i <= mxN; i++) {
		for (int j = 0; j <= mxD; j++) {
			contrib[i][j] = 1;
		}
	}
}
void Input() {
	cin >> n >> L;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		cin >> height[i];
	}
}
int par[mxN + 1];
void FindParent(int u = 1, int pp = 0) {
	par[u] = pp;
	for (int &v : adj[u]) {
		if (v != pp) {
			FindParent(v, u);
		}
	}
}
void Update(int x, int d, int w) {
	while (x != 1 && d >= 0) {
		contrib[x][d] = (1LL * contrib[x][d] * w) % L;
		if (d > 0) {
			contrib[x][d - 1] = (1LL * contrib[x][d - 1] * w) % L;
		}
		x = par[x];
		d--;
	}
	for (int i = d; i >= 0; i--) {
		contrib[x][i] = (1LL * contrib[x][i] * w) % L;
	}
}
int Query(int x) {
	int res = height[x];
	for (int i = 0; i <= mxD; i++) {
		if (x == 0) break;
		res = (1LL * res * contrib[x][i]) % L;
		x = par[x];
	}
	return res;
}
int main() {
	Init();
	Input();
	FindParent();
	int q;
	cin >> q;
	while (q--) {
		int cmd;
		cin >> cmd;
		if (cmd == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			Update(x, d, w);
		} else if (cmd == 2) {
			int x;
			cin >> x;
			cout << Query(x) << endl;
		}
	}
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37068 KB Output is correct
2 Correct 19 ms 37000 KB Output is correct
3 Correct 19 ms 37088 KB Output is correct
4 Correct 21 ms 37084 KB Output is correct
5 Correct 21 ms 37132 KB Output is correct
6 Correct 25 ms 37132 KB Output is correct
7 Correct 22 ms 37064 KB Output is correct
8 Correct 20 ms 37064 KB Output is correct
9 Correct 21 ms 37012 KB Output is correct
10 Correct 20 ms 37076 KB Output is correct
11 Correct 20 ms 37016 KB Output is correct
12 Correct 24 ms 36988 KB Output is correct
13 Correct 26 ms 36996 KB Output is correct
14 Correct 21 ms 37044 KB Output is correct
15 Correct 22 ms 37076 KB Output is correct
16 Correct 21 ms 37004 KB Output is correct
17 Correct 20 ms 36964 KB Output is correct
18 Correct 21 ms 37044 KB Output is correct
19 Correct 21 ms 37076 KB Output is correct
20 Correct 20 ms 37056 KB Output is correct
21 Correct 20 ms 37076 KB Output is correct
22 Correct 20 ms 37052 KB Output is correct
23 Correct 21 ms 37040 KB Output is correct
24 Correct 20 ms 37076 KB Output is correct
25 Correct 20 ms 37036 KB Output is correct
26 Correct 19 ms 37068 KB Output is correct
27 Correct 20 ms 37076 KB Output is correct
28 Correct 20 ms 37104 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 36980 KB Output is correct
2 Correct 1194 ms 48644 KB Output is correct
3 Correct 734 ms 57244 KB Output is correct
4 Correct 1067 ms 59688 KB Output is correct
5 Correct 997 ms 57048 KB Output is correct
6 Correct 833 ms 56656 KB Output is correct
7 Correct 862 ms 57316 KB Output is correct
8 Correct 780 ms 57852 KB Output is correct
9 Correct 1228 ms 60840 KB Output is correct
10 Correct 776 ms 61072 KB Output is correct
11 Correct 1207 ms 56772 KB Output is correct
12 Correct 776 ms 57272 KB Output is correct
13 Correct 650 ms 57508 KB Output is correct
14 Correct 653 ms 58092 KB Output is correct
15 Correct 615 ms 57528 KB Output is correct
16 Correct 640 ms 57824 KB Output is correct
17 Correct 691 ms 58412 KB Output is correct
18 Correct 21 ms 37076 KB Output is correct
19 Correct 22 ms 37076 KB Output is correct
20 Correct 21 ms 37076 KB Output is correct
21 Correct 22 ms 37108 KB Output is correct
22 Correct 21 ms 37000 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 36980 KB Output is correct
2 Correct 1194 ms 48644 KB Output is correct
3 Correct 734 ms 57244 KB Output is correct
4 Correct 1067 ms 59688 KB Output is correct
5 Correct 997 ms 57048 KB Output is correct
6 Correct 833 ms 56656 KB Output is correct
7 Correct 862 ms 57316 KB Output is correct
8 Correct 780 ms 57852 KB Output is correct
9 Correct 1228 ms 60840 KB Output is correct
10 Correct 776 ms 61072 KB Output is correct
11 Correct 1207 ms 56772 KB Output is correct
12 Correct 776 ms 57272 KB Output is correct
13 Correct 650 ms 57508 KB Output is correct
14 Correct 653 ms 58092 KB Output is correct
15 Correct 615 ms 57528 KB Output is correct
16 Correct 640 ms 57824 KB Output is correct
17 Correct 691 ms 58412 KB Output is correct
18 Correct 21 ms 37076 KB Output is correct
19 Correct 22 ms 37076 KB Output is correct
20 Correct 21 ms 37076 KB Output is correct
21 Correct 22 ms 37108 KB Output is correct
22 Correct 21 ms 37000 KB Output is correct
23 Correct 24 ms 37084 KB Output is correct
24 Correct 1256 ms 56688 KB Output is correct
25 Correct 734 ms 57300 KB Output is correct
26 Correct 1072 ms 61068 KB Output is correct
27 Correct 947 ms 56948 KB Output is correct
28 Correct 878 ms 57060 KB Output is correct
29 Correct 835 ms 56760 KB Output is correct
30 Correct 824 ms 57856 KB Output is correct
31 Correct 1247 ms 59692 KB Output is correct
32 Correct 772 ms 61176 KB Output is correct
33 Correct 1254 ms 56680 KB Output is correct
34 Correct 729 ms 57172 KB Output is correct
35 Correct 22 ms 37028 KB Output is correct
36 Correct 22 ms 37068 KB Output is correct
37 Correct 25 ms 37056 KB Output is correct
38 Correct 20 ms 37064 KB Output is correct
39 Correct 20 ms 37052 KB Output is correct
40 Correct 22 ms 37128 KB Output is correct
41 Correct 20 ms 37064 KB Output is correct
42 Correct 21 ms 37076 KB Output is correct
43 Correct 20 ms 37076 KB Output is correct
44 Correct 20 ms 37056 KB Output is correct
45 Correct 22 ms 37072 KB Output is correct
46 Correct 22 ms 37072 KB Output is correct
47 Correct 21 ms 37076 KB Output is correct
48 Correct 21 ms 37076 KB Output is correct
49 Correct 24 ms 37076 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37076 KB Output is correct
2 Correct 1243 ms 50088 KB Output is correct
3 Correct 1008 ms 57764 KB Output is correct
4 Correct 1078 ms 57300 KB Output is correct
5 Correct 986 ms 54068 KB Output is correct
6 Correct 837 ms 54196 KB Output is correct
7 Correct 821 ms 54456 KB Output is correct
8 Correct 752 ms 54840 KB Output is correct
9 Correct 1266 ms 56772 KB Output is correct
10 Correct 1046 ms 58252 KB Output is correct
11 Correct 1233 ms 53676 KB Output is correct
12 Correct 946 ms 54596 KB Output is correct
13 Correct 717 ms 55424 KB Output is correct
14 Correct 746 ms 55968 KB Output is correct
15 Correct 20 ms 37104 KB Output is correct
16 Correct 21 ms 37080 KB Output is correct
17 Correct 19 ms 37048 KB Output is correct
18 Correct 20 ms 37004 KB Output is correct
19 Correct 21 ms 37108 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37076 KB Output is correct
2 Correct 1265 ms 51436 KB Output is correct
3 Correct 1113 ms 57196 KB Output is correct
4 Correct 1022 ms 58084 KB Output is correct
5 Correct 1077 ms 55564 KB Output is correct
6 Correct 837 ms 55680 KB Output is correct
7 Correct 841 ms 55516 KB Output is correct
8 Correct 745 ms 55880 KB Output is correct
9 Correct 1282 ms 60396 KB Output is correct
10 Correct 1090 ms 58820 KB Output is correct
11 Correct 1175 ms 56376 KB Output is correct
12 Correct 889 ms 54968 KB Output is correct
13 Correct 704 ms 55600 KB Output is correct
14 Correct 740 ms 56128 KB Output is correct
15 Correct 19 ms 37076 KB Output is correct
16 Correct 20 ms 37052 KB Output is correct
17 Correct 19 ms 37076 KB Output is correct
18 Correct 20 ms 37076 KB Output is correct
19 Correct 18 ms 37100 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37068 KB Output is correct
2 Correct 19 ms 37000 KB Output is correct
3 Correct 19 ms 37088 KB Output is correct
4 Correct 21 ms 37084 KB Output is correct
5 Correct 21 ms 37132 KB Output is correct
6 Correct 25 ms 37132 KB Output is correct
7 Correct 22 ms 37064 KB Output is correct
8 Correct 20 ms 37064 KB Output is correct
9 Correct 21 ms 37012 KB Output is correct
10 Correct 20 ms 37076 KB Output is correct
11 Correct 20 ms 37016 KB Output is correct
12 Correct 24 ms 36988 KB Output is correct
13 Correct 26 ms 36996 KB Output is correct
14 Correct 21 ms 37044 KB Output is correct
15 Correct 22 ms 37076 KB Output is correct
16 Correct 21 ms 37004 KB Output is correct
17 Correct 20 ms 36964 KB Output is correct
18 Correct 21 ms 37044 KB Output is correct
19 Correct 21 ms 37076 KB Output is correct
20 Correct 20 ms 37056 KB Output is correct
21 Correct 20 ms 37076 KB Output is correct
22 Correct 20 ms 37052 KB Output is correct
23 Correct 21 ms 37040 KB Output is correct
24 Correct 20 ms 37076 KB Output is correct
25 Correct 20 ms 37036 KB Output is correct
26 Correct 19 ms 37068 KB Output is correct
27 Correct 20 ms 37076 KB Output is correct
28 Correct 20 ms 37104 KB Output is correct
29 Correct 20 ms 36980 KB Output is correct
30 Correct 1194 ms 48644 KB Output is correct
31 Correct 734 ms 57244 KB Output is correct
32 Correct 1067 ms 59688 KB Output is correct
33 Correct 997 ms 57048 KB Output is correct
34 Correct 833 ms 56656 KB Output is correct
35 Correct 862 ms 57316 KB Output is correct
36 Correct 780 ms 57852 KB Output is correct
37 Correct 1228 ms 60840 KB Output is correct
38 Correct 776 ms 61072 KB Output is correct
39 Correct 1207 ms 56772 KB Output is correct
40 Correct 776 ms 57272 KB Output is correct
41 Correct 650 ms 57508 KB Output is correct
42 Correct 653 ms 58092 KB Output is correct
43 Correct 615 ms 57528 KB Output is correct
44 Correct 640 ms 57824 KB Output is correct
45 Correct 691 ms 58412 KB Output is correct
46 Correct 21 ms 37076 KB Output is correct
47 Correct 22 ms 37076 KB Output is correct
48 Correct 21 ms 37076 KB Output is correct
49 Correct 22 ms 37108 KB Output is correct
50 Correct 21 ms 37000 KB Output is correct
51 Correct 24 ms 37084 KB Output is correct
52 Correct 1256 ms 56688 KB Output is correct
53 Correct 734 ms 57300 KB Output is correct
54 Correct 1072 ms 61068 KB Output is correct
55 Correct 947 ms 56948 KB Output is correct
56 Correct 878 ms 57060 KB Output is correct
57 Correct 835 ms 56760 KB Output is correct
58 Correct 824 ms 57856 KB Output is correct
59 Correct 1247 ms 59692 KB Output is correct
60 Correct 772 ms 61176 KB Output is correct
61 Correct 1254 ms 56680 KB Output is correct
62 Correct 729 ms 57172 KB Output is correct
63 Correct 22 ms 37028 KB Output is correct
64 Correct 22 ms 37068 KB Output is correct
65 Correct 25 ms 37056 KB Output is correct
66 Correct 20 ms 37064 KB Output is correct
67 Correct 20 ms 37052 KB Output is correct
68 Correct 22 ms 37128 KB Output is correct
69 Correct 20 ms 37064 KB Output is correct
70 Correct 21 ms 37076 KB Output is correct
71 Correct 20 ms 37076 KB Output is correct
72 Correct 20 ms 37056 KB Output is correct
73 Correct 22 ms 37072 KB Output is correct
74 Correct 22 ms 37072 KB Output is correct
75 Correct 21 ms 37076 KB Output is correct
76 Correct 21 ms 37076 KB Output is correct
77 Correct 24 ms 37076 KB Output is correct
78 Correct 22 ms 37076 KB Output is correct
79 Correct 1243 ms 50088 KB Output is correct
80 Correct 1008 ms 57764 KB Output is correct
81 Correct 1078 ms 57300 KB Output is correct
82 Correct 986 ms 54068 KB Output is correct
83 Correct 837 ms 54196 KB Output is correct
84 Correct 821 ms 54456 KB Output is correct
85 Correct 752 ms 54840 KB Output is correct
86 Correct 1266 ms 56772 KB Output is correct
87 Correct 1046 ms 58252 KB Output is correct
88 Correct 1233 ms 53676 KB Output is correct
89 Correct 946 ms 54596 KB Output is correct
90 Correct 717 ms 55424 KB Output is correct
91 Correct 746 ms 55968 KB Output is correct
92 Correct 20 ms 37104 KB Output is correct
93 Correct 21 ms 37080 KB Output is correct
94 Correct 19 ms 37048 KB Output is correct
95 Correct 20 ms 37004 KB Output is correct
96 Correct 21 ms 37108 KB Output is correct
97 Correct 20 ms 37076 KB Output is correct
98 Correct 1265 ms 51436 KB Output is correct
99 Correct 1113 ms 57196 KB Output is correct
100 Correct 1022 ms 58084 KB Output is correct
101 Correct 1077 ms 55564 KB Output is correct
102 Correct 837 ms 55680 KB Output is correct
103 Correct 841 ms 55516 KB Output is correct
104 Correct 745 ms 55880 KB Output is correct
105 Correct 1282 ms 60396 KB Output is correct
106 Correct 1090 ms 58820 KB Output is correct
107 Correct 1175 ms 56376 KB Output is correct
108 Correct 889 ms 54968 KB Output is correct
109 Correct 704 ms 55600 KB Output is correct
110 Correct 740 ms 56128 KB Output is correct
111 Correct 19 ms 37076 KB Output is correct
112 Correct 20 ms 37052 KB Output is correct
113 Correct 19 ms 37076 KB Output is correct
114 Correct 20 ms 37076 KB Output is correct
115 Correct 18 ms 37100 KB Output is correct
116 Correct 1188 ms 54780 KB Output is correct
117 Correct 1090 ms 57360 KB Output is correct
118 Correct 1097 ms 61036 KB Output is correct
119 Correct 1020 ms 57192 KB Output is correct
120 Correct 881 ms 56696 KB Output is correct
121 Correct 922 ms 57488 KB Output is correct
122 Correct 902 ms 57804 KB Output is correct
123 Correct 1320 ms 60168 KB Output is correct
124 Correct 1046 ms 59580 KB Output is correct
125 Correct 1221 ms 55908 KB Output is correct
126 Correct 983 ms 57316 KB Output is correct
127 Correct 1072 ms 57772 KB Output is correct
128 Correct 874 ms 58348 KB Output is correct
129 Correct 900 ms 58896 KB Output is correct