oj.uz

Submission #551937

# Submission time Handle Problem Language Result Execution time Memory
551937 2022-04-21T23:01:48 Z QwertyPi Sprinkler (JOI22_sprinkler) C++14
100 / 100
 1363 ms 99444 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define int long long
using namespace std;

const int N = 2e5 + 5, D = 41;
int n, L;
int h[N], p[N], d[N];
vector<int> G[N];
int dp[N][D];

void dfs(int x, int par = -1){
	for(auto i : G[x]){
		if(i != par){
			d[i] = d[x] + 1;
			dfs(i, x);
			p[i] = x;
		}
	}
}

int lay[D];
void upd(int x, int d, int w){
	int idx = 0;
	while(x != 0 && idx <= d){
		lay[idx++] = x;
		x = p[x];
	}
	int mx = 0;
	for(int i = idx - 1; i >= 0; i--){
		int l = mx, r = d - i;
		for(int j = l; j <= r; j++){
			dp[lay[i]][j] = dp[lay[i]][j] * w % L;
		}
		mx = r;
	}
}

int qry(int x){
	int ret = h[x];
	for(int i = 0; i < D && x > 0; i++){
		ret = ret * dp[x][i] % L;
		x = p[x];
	}
	return ret;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	for(int i = 0; i < N; i++) for(int j = 0; j < D; j++) dp[i][j] = 1;
	cin >> n >> L;
	for(int i = 0; i < n - 1; i++){
		int u, v;
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1);
	for(int i = 1; i <= n; i++) cin >> h[i];
	int q;
	cin >> q;
	for(int i = 0; i < q; i++){
		int t; cin >> t;
		if(t == 1){
			int x, d, w;
			cin >> x >> d >> w; 
			upd(x, d, w);
		}else{
			int x;
			cin >> x;
			cout << qry(x) << endl;
		}
	}
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 69196 KB Output is correct
2 Correct 30 ms 69196 KB Output is correct
3 Correct 40 ms 69136 KB Output is correct
4 Correct 37 ms 69272 KB Output is correct
5 Correct 40 ms 69228 KB Output is correct
6 Correct 31 ms 69204 KB Output is correct
7 Correct 31 ms 69320 KB Output is correct
8 Correct 32 ms 69260 KB Output is correct
9 Correct 33 ms 69144 KB Output is correct
10 Correct 30 ms 69128 KB Output is correct
11 Correct 32 ms 69152 KB Output is correct
12 Correct 36 ms 69200 KB Output is correct
13 Correct 32 ms 69148 KB Output is correct
14 Correct 34 ms 69220 KB Output is correct
15 Correct 29 ms 69208 KB Output is correct
16 Correct 30 ms 69180 KB Output is correct
17 Correct 32 ms 69124 KB Output is correct
18 Correct 30 ms 69156 KB Output is correct
19 Correct 32 ms 69212 KB Output is correct
20 Correct 38 ms 69144 KB Output is correct
21 Correct 41 ms 69132 KB Output is correct
22 Correct 34 ms 69188 KB Output is correct
23 Correct 30 ms 69128 KB Output is correct
24 Correct 30 ms 69108 KB Output is correct
25 Correct 30 ms 69172 KB Output is correct
26 Correct 32 ms 69148 KB Output is correct
27 Correct 30 ms 69204 KB Output is correct
28 Correct 30 ms 69136 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 69204 KB Output is correct
2 Correct 1141 ms 85220 KB Output is correct
3 Correct 506 ms 86808 KB Output is correct
4 Correct 876 ms 94536 KB Output is correct
5 Correct 802 ms 88384 KB Output is correct
6 Correct 652 ms 86868 KB Output is correct
7 Correct 623 ms 87712 KB Output is correct
8 Correct 544 ms 88084 KB Output is correct
9 Correct 1155 ms 99444 KB Output is correct
10 Correct 513 ms 96772 KB Output is correct
11 Correct 1150 ms 88140 KB Output is correct
12 Correct 414 ms 85260 KB Output is correct
13 Correct 338 ms 87280 KB Output is correct
14 Correct 316 ms 87184 KB Output is correct
15 Correct 334 ms 83236 KB Output is correct
16 Correct 344 ms 84648 KB Output is correct
17 Correct 320 ms 84944 KB Output is correct
18 Correct 35 ms 69184 KB Output is correct
19 Correct 32 ms 69156 KB Output is correct
20 Correct 35 ms 69180 KB Output is correct
21 Correct 32 ms 69204 KB Output is correct
22 Correct 33 ms 69116 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 69204 KB Output is correct
2 Correct 1141 ms 85220 KB Output is correct
3 Correct 506 ms 86808 KB Output is correct
4 Correct 876 ms 94536 KB Output is correct
5 Correct 802 ms 88384 KB Output is correct
6 Correct 652 ms 86868 KB Output is correct
7 Correct 623 ms 87712 KB Output is correct
8 Correct 544 ms 88084 KB Output is correct
9 Correct 1155 ms 99444 KB Output is correct
10 Correct 513 ms 96772 KB Output is correct
11 Correct 1150 ms 88140 KB Output is correct
12 Correct 414 ms 85260 KB Output is correct
13 Correct 338 ms 87280 KB Output is correct
14 Correct 316 ms 87184 KB Output is correct
15 Correct 334 ms 83236 KB Output is correct
16 Correct 344 ms 84648 KB Output is correct
17 Correct 320 ms 84944 KB Output is correct
18 Correct 35 ms 69184 KB Output is correct
19 Correct 32 ms 69156 KB Output is correct
20 Correct 35 ms 69180 KB Output is correct
21 Correct 32 ms 69204 KB Output is correct
22 Correct 33 ms 69116 KB Output is correct
23 Correct 38 ms 69208 KB Output is correct
24 Correct 1174 ms 89952 KB Output is correct
25 Correct 514 ms 86724 KB Output is correct
26 Correct 850 ms 98968 KB Output is correct
27 Correct 814 ms 88452 KB Output is correct
28 Correct 591 ms 88408 KB Output is correct
29 Correct 640 ms 88492 KB Output is correct
30 Correct 530 ms 88720 KB Output is correct
31 Correct 1248 ms 97088 KB Output is correct
32 Correct 506 ms 96880 KB Output is correct
33 Correct 1102 ms 89804 KB Output is correct
34 Correct 498 ms 86776 KB Output is correct
35 Correct 31 ms 69216 KB Output is correct
36 Correct 36 ms 69144 KB Output is correct
37 Correct 32 ms 69212 KB Output is correct
38 Correct 33 ms 69200 KB Output is correct
39 Correct 32 ms 69148 KB Output is correct
40 Correct 33 ms 69104 KB Output is correct
41 Correct 34 ms 69192 KB Output is correct
42 Correct 31 ms 69212 KB Output is correct
43 Correct 32 ms 69152 KB Output is correct
44 Correct 30 ms 69120 KB Output is correct
45 Correct 40 ms 69184 KB Output is correct
46 Correct 31 ms 69152 KB Output is correct
47 Correct 32 ms 69164 KB Output is correct
48 Correct 34 ms 69196 KB Output is correct
49 Correct 31 ms 69188 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 69184 KB Output is correct
2 Correct 1262 ms 94888 KB Output is correct
3 Correct 1104 ms 96412 KB Output is correct
4 Correct 987 ms 95224 KB Output is correct
5 Correct 919 ms 87576 KB Output is correct
6 Correct 717 ms 84236 KB Output is correct
7 Correct 658 ms 84328 KB Output is correct
8 Correct 518 ms 84480 KB Output is correct
9 Correct 1203 ms 92096 KB Output is correct
10 Correct 1154 ms 93572 KB Output is correct
11 Correct 1284 ms 84480 KB Output is correct
12 Correct 1120 ms 86756 KB Output is correct
13 Correct 648 ms 84556 KB Output is correct
14 Correct 663 ms 85736 KB Output is correct
15 Correct 35 ms 69204 KB Output is correct
16 Correct 32 ms 69200 KB Output is correct
17 Correct 33 ms 69200 KB Output is correct
18 Correct 40 ms 69116 KB Output is correct
19 Correct 31 ms 69152 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 69204 KB Output is correct
2 Correct 1299 ms 93504 KB Output is correct
3 Correct 1186 ms 93140 KB Output is correct
4 Correct 1068 ms 94480 KB Output is correct
5 Correct 972 ms 88792 KB Output is correct
6 Correct 743 ms 85824 KB Output is correct
7 Correct 729 ms 85752 KB Output is correct
8 Correct 533 ms 85928 KB Output is correct
9 Correct 1343 ms 97332 KB Output is correct
10 Correct 1188 ms 94296 KB Output is correct
11 Correct 1279 ms 87108 KB Output is correct
12 Correct 1024 ms 87136 KB Output is correct
13 Correct 639 ms 85220 KB Output is correct
14 Correct 707 ms 85876 KB Output is correct
15 Correct 32 ms 69192 KB Output is correct
16 Correct 32 ms 69184 KB Output is correct
17 Correct 33 ms 69168 KB Output is correct
18 Correct 33 ms 69204 KB Output is correct
19 Correct 32 ms 69188 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 69196 KB Output is correct
2 Correct 30 ms 69196 KB Output is correct
3 Correct 40 ms 69136 KB Output is correct
4 Correct 37 ms 69272 KB Output is correct
5 Correct 40 ms 69228 KB Output is correct
6 Correct 31 ms 69204 KB Output is correct
7 Correct 31 ms 69320 KB Output is correct
8 Correct 32 ms 69260 KB Output is correct
9 Correct 33 ms 69144 KB Output is correct
10 Correct 30 ms 69128 KB Output is correct
11 Correct 32 ms 69152 KB Output is correct
12 Correct 36 ms 69200 KB Output is correct
13 Correct 32 ms 69148 KB Output is correct
14 Correct 34 ms 69220 KB Output is correct
15 Correct 29 ms 69208 KB Output is correct
16 Correct 30 ms 69180 KB Output is correct
17 Correct 32 ms 69124 KB Output is correct
18 Correct 30 ms 69156 KB Output is correct
19 Correct 32 ms 69212 KB Output is correct
20 Correct 38 ms 69144 KB Output is correct
21 Correct 41 ms 69132 KB Output is correct
22 Correct 34 ms 69188 KB Output is correct
23 Correct 30 ms 69128 KB Output is correct
24 Correct 30 ms 69108 KB Output is correct
25 Correct 30 ms 69172 KB Output is correct
26 Correct 32 ms 69148 KB Output is correct
27 Correct 30 ms 69204 KB Output is correct
28 Correct 30 ms 69136 KB Output is correct
29 Correct 37 ms 69204 KB Output is correct
30 Correct 1141 ms 85220 KB Output is correct
31 Correct 506 ms 86808 KB Output is correct
32 Correct 876 ms 94536 KB Output is correct
33 Correct 802 ms 88384 KB Output is correct
34 Correct 652 ms 86868 KB Output is correct
35 Correct 623 ms 87712 KB Output is correct
36 Correct 544 ms 88084 KB Output is correct
37 Correct 1155 ms 99444 KB Output is correct
38 Correct 513 ms 96772 KB Output is correct
39 Correct 1150 ms 88140 KB Output is correct
40 Correct 414 ms 85260 KB Output is correct
41 Correct 338 ms 87280 KB Output is correct
42 Correct 316 ms 87184 KB Output is correct
43 Correct 334 ms 83236 KB Output is correct
44 Correct 344 ms 84648 KB Output is correct
45 Correct 320 ms 84944 KB Output is correct
46 Correct 35 ms 69184 KB Output is correct
47 Correct 32 ms 69156 KB Output is correct
48 Correct 35 ms 69180 KB Output is correct
49 Correct 32 ms 69204 KB Output is correct
50 Correct 33 ms 69116 KB Output is correct
51 Correct 38 ms 69208 KB Output is correct
52 Correct 1174 ms 89952 KB Output is correct
53 Correct 514 ms 86724 KB Output is correct
54 Correct 850 ms 98968 KB Output is correct
55 Correct 814 ms 88452 KB Output is correct
56 Correct 591 ms 88408 KB Output is correct
57 Correct 640 ms 88492 KB Output is correct
58 Correct 530 ms 88720 KB Output is correct
59 Correct 1248 ms 97088 KB Output is correct
60 Correct 506 ms 96880 KB Output is correct
61 Correct 1102 ms 89804 KB Output is correct
62 Correct 498 ms 86776 KB Output is correct
63 Correct 31 ms 69216 KB Output is correct
64 Correct 36 ms 69144 KB Output is correct
65 Correct 32 ms 69212 KB Output is correct
66 Correct 33 ms 69200 KB Output is correct
67 Correct 32 ms 69148 KB Output is correct
68 Correct 33 ms 69104 KB Output is correct
69 Correct 34 ms 69192 KB Output is correct
70 Correct 31 ms 69212 KB Output is correct
71 Correct 32 ms 69152 KB Output is correct
72 Correct 30 ms 69120 KB Output is correct
73 Correct 40 ms 69184 KB Output is correct
74 Correct 31 ms 69152 KB Output is correct
75 Correct 32 ms 69164 KB Output is correct
76 Correct 34 ms 69196 KB Output is correct
77 Correct 31 ms 69188 KB Output is correct
78 Correct 30 ms 69184 KB Output is correct
79 Correct 1262 ms 94888 KB Output is correct
80 Correct 1104 ms 96412 KB Output is correct
81 Correct 987 ms 95224 KB Output is correct
82 Correct 919 ms 87576 KB Output is correct
83 Correct 717 ms 84236 KB Output is correct
84 Correct 658 ms 84328 KB Output is correct
85 Correct 518 ms 84480 KB Output is correct
86 Correct 1203 ms 92096 KB Output is correct
87 Correct 1154 ms 93572 KB Output is correct
88 Correct 1284 ms 84480 KB Output is correct
89 Correct 1120 ms 86756 KB Output is correct
90 Correct 648 ms 84556 KB Output is correct
91 Correct 663 ms 85736 KB Output is correct
92 Correct 35 ms 69204 KB Output is correct
93 Correct 32 ms 69200 KB Output is correct
94 Correct 33 ms 69200 KB Output is correct
95 Correct 40 ms 69116 KB Output is correct
96 Correct 31 ms 69152 KB Output is correct
97 Correct 31 ms 69204 KB Output is correct
98 Correct 1299 ms 93504 KB Output is correct
99 Correct 1186 ms 93140 KB Output is correct
100 Correct 1068 ms 94480 KB Output is correct
101 Correct 972 ms 88792 KB Output is correct
102 Correct 743 ms 85824 KB Output is correct
103 Correct 729 ms 85752 KB Output is correct
104 Correct 533 ms 85928 KB Output is correct
105 Correct 1343 ms 97332 KB Output is correct
106 Correct 1188 ms 94296 KB Output is correct
107 Correct 1279 ms 87108 KB Output is correct
108 Correct 1024 ms 87136 KB Output is correct
109 Correct 639 ms 85220 KB Output is correct
110 Correct 707 ms 85876 KB Output is correct
111 Correct 32 ms 69192 KB Output is correct
112 Correct 32 ms 69184 KB Output is correct
113 Correct 33 ms 69168 KB Output is correct
114 Correct 33 ms 69204 KB Output is correct
115 Correct 32 ms 69188 KB Output is correct
116 Correct 1258 ms 85152 KB Output is correct
117 Correct 1097 ms 86224 KB Output is correct
118 Correct 1131 ms 96144 KB Output is correct
119 Correct 998 ms 86352 KB Output is correct
120 Correct 731 ms 85752 KB Output is correct
121 Correct 773 ms 86880 KB Output is correct
122 Correct 599 ms 86676 KB Output is correct
123 Correct 1363 ms 95620 KB Output is correct
124 Correct 1260 ms 92640 KB Output is correct
125 Correct 1228 ms 86608 KB Output is correct
126 Correct 1108 ms 86444 KB Output is correct
127 Correct 1241 ms 86536 KB Output is correct
128 Correct 824 ms 84688 KB Output is correct
129 Correct 796 ms 83188 KB Output is correct