#pragma GCC optimize("O3,unroll-loops")
#include <cstdio>
#include <vector>
int md;
inline int mul(int a, int b) {
return (long long)a * b % md;
}
const int N = 200005;
const int D = 40;
const int LG = 19;
const int K = 500;
std::vector<int> g[N], list[N], t[N];
int q, n, in[N], dep[N], pr[N], pos[N], h[N], start[N], out[N], amt, st[LG][N * 2], clz[N * 2], bounds[N][D + 1][2];
void dfs(int v) {
static int dt = 0;
in[v] = dt++;
pos[v] = list[dep[v]].size();
list[dep[v]].push_back(v);
start[v] = amt;
st[0][amt++] = dep[v];
for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i] != pr[v]) {
if (i) st[0][amt++] = dep[v];
pr[g[v][i]] = v;
dep[g[v][i]] = dep[v] + 1;
dfs(g[v][i]);
}
out[v] = dt;
}
int l;
int dlca(int u, int v) {
u = start[u];
v = start[v];
if (u > v) std::swap(u, v);
++v;
l = clz[v - u];
return std::min(st[l][u], st[l][v - (1 << l)]);
}
int f(int u, int v) {
return dep[u] + dep[v] - 2 * dlca(u, v);
}
void update(std::vector<int> &t, int l, int r, int x) {
if (!x) {
for (l += t.size() >> 1, r += t.size() >> 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) t[l++] = 0;
if (r & 1) t[--r] = 0;
}
return;
}
for (l += t.size() >> 1, r += t.size() >> 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
t[l] = mul(t[l], x);
++l;
}
if (r & 1) {
--r;
t[r] = mul(t[r], x);
}
}
}
int get(std::vector<int> &t, int i) {
int res = 1;
for (i += t.size() >> 1; i > 0; i >>= 1) res = mul(res, t[i]);
return res;
}
int sub_left(int v, int dep) {
int l = 0, r = (int)list[dep].size();
while (l < r) {
int m = l + r >> 1;
if (in[list[dep][m]] >= in[v]) r = m;
else l = m + 1;
}
return r;
}
int sub_right(int v, int dep) {
int l = 0, r = (int)list[dep].size();
while (l < r) {
int m = l + r >> 1;
if (out[list[dep][m]] > out[v]) r = m;
else l = m + 1;
}
return r;
}
int main() {
scanf("%d%d", &n, &md);
clz[1] = 0;
for (int i = 2; i <= 2 * n; ++i) {
clz[i] = clz[i - 1];
while (1 << clz[i] + 1 <= i) ++clz[i];
}
for (int i = 1; i < n; ++i) {
int a, b;
scanf("%d%d", &a, &b);
g[a - 1].push_back(b - 1);
g[b - 1].push_back(a - 1);
}
dfs(0);
for (int j = 1; j < LG; ++j) for (int i = 0; i + (1 << j) <= 2 * n; ++i) st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
for (int i = 0; i < n; ++i) scanf("%d", h + i);
for (int i = 0; i < n; ++i) t[i].resize(list[i].size() << 1, 1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= D && dep[i] + j < n; ++j) {
bounds[i][j][0] = sub_left(i, dep[i] + j);
bounds[i][j][1] = sub_right(i, dep[i] + j);
}
}
scanf("%d", &q);
while (q--) {
int type, v;
scanf("%d%d", &type, &v);
--v;
if (type == 1) {
int dist, x;
scanf("%d%d", &dist, &x);
for (int i = std::min(n - 1, dep[v] + dist), j = v; i >= std::max(0, dep[v] - dist); --i) {
while (j && dep[v] + i - 2 * (dep[j] - 1) <= dist) j = pr[j];
int l = bounds[j][i - dep[j]][0], r = bounds[j][i - dep[j]][1];
update(t[i], l, r, x);
}
} else printf("%d\n", mul(h[v], get(t[dep[v]], pos[v])));
}
return 0;
}
Compilation message
sprinkler.cpp: In function 'int sub_left(int, int)':
sprinkler.cpp:76:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int m = l + r >> 1;
| ~~^~~
sprinkler.cpp: In function 'int sub_right(int, int)':
sprinkler.cpp:86:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
86 | int m = l + r >> 1;
| ~~^~~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:98:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
98 | while (1 << clz[i] + 1 <= i) ++clz[i];
| ~~~~~~~^~~
sprinkler.cpp:107:131: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
107 | for (int j = 1; j < LG; ++j) for (int i = 0; i + (1 << j) <= 2 * n; ++i) st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
| ~~^~~
sprinkler.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d%d", &n, &md);
| ~~~~~^~~~~~~~~~~~~~~~~
sprinkler.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:108:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | for (int i = 0; i < n; ++i) scanf("%d", h + i);
| ~~~~~^~~~~~~~~~~~~
sprinkler.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
116 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
sprinkler.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | scanf("%d%d", &type, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~
sprinkler.cpp:123:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | scanf("%d%d", &dist, &x);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
14420 KB |
Output is correct |
2 |
Correct |
9 ms |
14420 KB |
Output is correct |
3 |
Correct |
12 ms |
14420 KB |
Output is correct |
4 |
Correct |
12 ms |
14960 KB |
Output is correct |
5 |
Correct |
12 ms |
15000 KB |
Output is correct |
6 |
Correct |
11 ms |
14932 KB |
Output is correct |
7 |
Correct |
12 ms |
14996 KB |
Output is correct |
8 |
Correct |
14 ms |
14976 KB |
Output is correct |
9 |
Correct |
12 ms |
14420 KB |
Output is correct |
10 |
Correct |
9 ms |
14420 KB |
Output is correct |
11 |
Correct |
9 ms |
14420 KB |
Output is correct |
12 |
Correct |
10 ms |
14420 KB |
Output is correct |
13 |
Correct |
11 ms |
14420 KB |
Output is correct |
14 |
Correct |
10 ms |
14432 KB |
Output is correct |
15 |
Correct |
13 ms |
14420 KB |
Output is correct |
16 |
Correct |
14 ms |
14344 KB |
Output is correct |
17 |
Correct |
10 ms |
14420 KB |
Output is correct |
18 |
Correct |
12 ms |
14420 KB |
Output is correct |
19 |
Correct |
10 ms |
14420 KB |
Output is correct |
20 |
Correct |
12 ms |
14420 KB |
Output is correct |
21 |
Correct |
10 ms |
14420 KB |
Output is correct |
22 |
Correct |
9 ms |
14472 KB |
Output is correct |
23 |
Correct |
13 ms |
14464 KB |
Output is correct |
24 |
Correct |
13 ms |
14340 KB |
Output is correct |
25 |
Correct |
13 ms |
14452 KB |
Output is correct |
26 |
Correct |
10 ms |
14464 KB |
Output is correct |
27 |
Correct |
12 ms |
14476 KB |
Output is correct |
28 |
Correct |
12 ms |
14476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
14420 KB |
Output is correct |
2 |
Correct |
1998 ms |
125732 KB |
Output is correct |
3 |
Correct |
2124 ms |
122568 KB |
Output is correct |
4 |
Correct |
654 ms |
139272 KB |
Output is correct |
5 |
Correct |
2033 ms |
124372 KB |
Output is correct |
6 |
Correct |
1508 ms |
123956 KB |
Output is correct |
7 |
Correct |
1258 ms |
124104 KB |
Output is correct |
8 |
Correct |
661 ms |
124824 KB |
Output is correct |
9 |
Correct |
693 ms |
150120 KB |
Output is correct |
10 |
Correct |
966 ms |
144644 KB |
Output is correct |
11 |
Correct |
1998 ms |
125700 KB |
Output is correct |
12 |
Correct |
2217 ms |
122544 KB |
Output is correct |
13 |
Correct |
921 ms |
123784 KB |
Output is correct |
14 |
Correct |
804 ms |
123084 KB |
Output is correct |
15 |
Correct |
901 ms |
123300 KB |
Output is correct |
16 |
Correct |
805 ms |
123144 KB |
Output is correct |
17 |
Correct |
901 ms |
123572 KB |
Output is correct |
18 |
Correct |
10 ms |
14420 KB |
Output is correct |
19 |
Correct |
10 ms |
14420 KB |
Output is correct |
20 |
Correct |
10 ms |
14452 KB |
Output is correct |
21 |
Correct |
10 ms |
14472 KB |
Output is correct |
22 |
Correct |
10 ms |
14388 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
14420 KB |
Output is correct |
2 |
Correct |
1998 ms |
125732 KB |
Output is correct |
3 |
Correct |
2124 ms |
122568 KB |
Output is correct |
4 |
Correct |
654 ms |
139272 KB |
Output is correct |
5 |
Correct |
2033 ms |
124372 KB |
Output is correct |
6 |
Correct |
1508 ms |
123956 KB |
Output is correct |
7 |
Correct |
1258 ms |
124104 KB |
Output is correct |
8 |
Correct |
661 ms |
124824 KB |
Output is correct |
9 |
Correct |
693 ms |
150120 KB |
Output is correct |
10 |
Correct |
966 ms |
144644 KB |
Output is correct |
11 |
Correct |
1998 ms |
125700 KB |
Output is correct |
12 |
Correct |
2217 ms |
122544 KB |
Output is correct |
13 |
Correct |
921 ms |
123784 KB |
Output is correct |
14 |
Correct |
804 ms |
123084 KB |
Output is correct |
15 |
Correct |
901 ms |
123300 KB |
Output is correct |
16 |
Correct |
805 ms |
123144 KB |
Output is correct |
17 |
Correct |
901 ms |
123572 KB |
Output is correct |
18 |
Correct |
10 ms |
14420 KB |
Output is correct |
19 |
Correct |
10 ms |
14420 KB |
Output is correct |
20 |
Correct |
10 ms |
14452 KB |
Output is correct |
21 |
Correct |
10 ms |
14472 KB |
Output is correct |
22 |
Correct |
10 ms |
14388 KB |
Output is correct |
23 |
Correct |
9 ms |
14468 KB |
Output is correct |
24 |
Correct |
1981 ms |
125720 KB |
Output is correct |
25 |
Correct |
2381 ms |
122548 KB |
Output is correct |
26 |
Correct |
765 ms |
147340 KB |
Output is correct |
27 |
Correct |
2045 ms |
124152 KB |
Output is correct |
28 |
Correct |
1409 ms |
124060 KB |
Output is correct |
29 |
Correct |
1248 ms |
124148 KB |
Output is correct |
30 |
Correct |
806 ms |
124764 KB |
Output is correct |
31 |
Correct |
912 ms |
141784 KB |
Output is correct |
32 |
Correct |
978 ms |
144744 KB |
Output is correct |
33 |
Correct |
1912 ms |
125740 KB |
Output is correct |
34 |
Correct |
2227 ms |
122524 KB |
Output is correct |
35 |
Correct |
12 ms |
14412 KB |
Output is correct |
36 |
Correct |
10 ms |
14420 KB |
Output is correct |
37 |
Correct |
10 ms |
14420 KB |
Output is correct |
38 |
Correct |
10 ms |
14420 KB |
Output is correct |
39 |
Correct |
10 ms |
14420 KB |
Output is correct |
40 |
Correct |
11 ms |
14420 KB |
Output is correct |
41 |
Correct |
10 ms |
14420 KB |
Output is correct |
42 |
Correct |
9 ms |
14472 KB |
Output is correct |
43 |
Correct |
12 ms |
14376 KB |
Output is correct |
44 |
Correct |
11 ms |
14476 KB |
Output is correct |
45 |
Correct |
10 ms |
14336 KB |
Output is correct |
46 |
Correct |
10 ms |
14460 KB |
Output is correct |
47 |
Correct |
10 ms |
14440 KB |
Output is correct |
48 |
Correct |
13 ms |
14420 KB |
Output is correct |
49 |
Correct |
13 ms |
14420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
14420 KB |
Output is correct |
2 |
Correct |
1384 ms |
147044 KB |
Output is correct |
3 |
Correct |
3950 ms |
139636 KB |
Output is correct |
4 |
Correct |
1721 ms |
141428 KB |
Output is correct |
5 |
Correct |
3379 ms |
122528 KB |
Output is correct |
6 |
Correct |
1670 ms |
122384 KB |
Output is correct |
7 |
Correct |
1415 ms |
122620 KB |
Output is correct |
8 |
Correct |
738 ms |
123320 KB |
Output is correct |
9 |
Correct |
1406 ms |
139184 KB |
Output is correct |
10 |
Correct |
3545 ms |
143916 KB |
Output is correct |
11 |
Correct |
2830 ms |
122908 KB |
Output is correct |
12 |
Execution timed out |
4070 ms |
122232 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
14420 KB |
Output is correct |
2 |
Correct |
1300 ms |
140732 KB |
Output is correct |
3 |
Execution timed out |
4078 ms |
133852 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
14420 KB |
Output is correct |
2 |
Correct |
9 ms |
14420 KB |
Output is correct |
3 |
Correct |
12 ms |
14420 KB |
Output is correct |
4 |
Correct |
12 ms |
14960 KB |
Output is correct |
5 |
Correct |
12 ms |
15000 KB |
Output is correct |
6 |
Correct |
11 ms |
14932 KB |
Output is correct |
7 |
Correct |
12 ms |
14996 KB |
Output is correct |
8 |
Correct |
14 ms |
14976 KB |
Output is correct |
9 |
Correct |
12 ms |
14420 KB |
Output is correct |
10 |
Correct |
9 ms |
14420 KB |
Output is correct |
11 |
Correct |
9 ms |
14420 KB |
Output is correct |
12 |
Correct |
10 ms |
14420 KB |
Output is correct |
13 |
Correct |
11 ms |
14420 KB |
Output is correct |
14 |
Correct |
10 ms |
14432 KB |
Output is correct |
15 |
Correct |
13 ms |
14420 KB |
Output is correct |
16 |
Correct |
14 ms |
14344 KB |
Output is correct |
17 |
Correct |
10 ms |
14420 KB |
Output is correct |
18 |
Correct |
12 ms |
14420 KB |
Output is correct |
19 |
Correct |
10 ms |
14420 KB |
Output is correct |
20 |
Correct |
12 ms |
14420 KB |
Output is correct |
21 |
Correct |
10 ms |
14420 KB |
Output is correct |
22 |
Correct |
9 ms |
14472 KB |
Output is correct |
23 |
Correct |
13 ms |
14464 KB |
Output is correct |
24 |
Correct |
13 ms |
14340 KB |
Output is correct |
25 |
Correct |
13 ms |
14452 KB |
Output is correct |
26 |
Correct |
10 ms |
14464 KB |
Output is correct |
27 |
Correct |
12 ms |
14476 KB |
Output is correct |
28 |
Correct |
12 ms |
14476 KB |
Output is correct |
29 |
Correct |
11 ms |
14420 KB |
Output is correct |
30 |
Correct |
1998 ms |
125732 KB |
Output is correct |
31 |
Correct |
2124 ms |
122568 KB |
Output is correct |
32 |
Correct |
654 ms |
139272 KB |
Output is correct |
33 |
Correct |
2033 ms |
124372 KB |
Output is correct |
34 |
Correct |
1508 ms |
123956 KB |
Output is correct |
35 |
Correct |
1258 ms |
124104 KB |
Output is correct |
36 |
Correct |
661 ms |
124824 KB |
Output is correct |
37 |
Correct |
693 ms |
150120 KB |
Output is correct |
38 |
Correct |
966 ms |
144644 KB |
Output is correct |
39 |
Correct |
1998 ms |
125700 KB |
Output is correct |
40 |
Correct |
2217 ms |
122544 KB |
Output is correct |
41 |
Correct |
921 ms |
123784 KB |
Output is correct |
42 |
Correct |
804 ms |
123084 KB |
Output is correct |
43 |
Correct |
901 ms |
123300 KB |
Output is correct |
44 |
Correct |
805 ms |
123144 KB |
Output is correct |
45 |
Correct |
901 ms |
123572 KB |
Output is correct |
46 |
Correct |
10 ms |
14420 KB |
Output is correct |
47 |
Correct |
10 ms |
14420 KB |
Output is correct |
48 |
Correct |
10 ms |
14452 KB |
Output is correct |
49 |
Correct |
10 ms |
14472 KB |
Output is correct |
50 |
Correct |
10 ms |
14388 KB |
Output is correct |
51 |
Correct |
9 ms |
14468 KB |
Output is correct |
52 |
Correct |
1981 ms |
125720 KB |
Output is correct |
53 |
Correct |
2381 ms |
122548 KB |
Output is correct |
54 |
Correct |
765 ms |
147340 KB |
Output is correct |
55 |
Correct |
2045 ms |
124152 KB |
Output is correct |
56 |
Correct |
1409 ms |
124060 KB |
Output is correct |
57 |
Correct |
1248 ms |
124148 KB |
Output is correct |
58 |
Correct |
806 ms |
124764 KB |
Output is correct |
59 |
Correct |
912 ms |
141784 KB |
Output is correct |
60 |
Correct |
978 ms |
144744 KB |
Output is correct |
61 |
Correct |
1912 ms |
125740 KB |
Output is correct |
62 |
Correct |
2227 ms |
122524 KB |
Output is correct |
63 |
Correct |
12 ms |
14412 KB |
Output is correct |
64 |
Correct |
10 ms |
14420 KB |
Output is correct |
65 |
Correct |
10 ms |
14420 KB |
Output is correct |
66 |
Correct |
10 ms |
14420 KB |
Output is correct |
67 |
Correct |
10 ms |
14420 KB |
Output is correct |
68 |
Correct |
11 ms |
14420 KB |
Output is correct |
69 |
Correct |
10 ms |
14420 KB |
Output is correct |
70 |
Correct |
9 ms |
14472 KB |
Output is correct |
71 |
Correct |
12 ms |
14376 KB |
Output is correct |
72 |
Correct |
11 ms |
14476 KB |
Output is correct |
73 |
Correct |
10 ms |
14336 KB |
Output is correct |
74 |
Correct |
10 ms |
14460 KB |
Output is correct |
75 |
Correct |
10 ms |
14440 KB |
Output is correct |
76 |
Correct |
13 ms |
14420 KB |
Output is correct |
77 |
Correct |
13 ms |
14420 KB |
Output is correct |
78 |
Correct |
10 ms |
14420 KB |
Output is correct |
79 |
Correct |
1384 ms |
147044 KB |
Output is correct |
80 |
Correct |
3950 ms |
139636 KB |
Output is correct |
81 |
Correct |
1721 ms |
141428 KB |
Output is correct |
82 |
Correct |
3379 ms |
122528 KB |
Output is correct |
83 |
Correct |
1670 ms |
122384 KB |
Output is correct |
84 |
Correct |
1415 ms |
122620 KB |
Output is correct |
85 |
Correct |
738 ms |
123320 KB |
Output is correct |
86 |
Correct |
1406 ms |
139184 KB |
Output is correct |
87 |
Correct |
3545 ms |
143916 KB |
Output is correct |
88 |
Correct |
2830 ms |
122908 KB |
Output is correct |
89 |
Execution timed out |
4070 ms |
122232 KB |
Time limit exceeded |
90 |
Halted |
0 ms |
0 KB |
- |