#include <bits/stdc++.h>
using namespace std;
#define int long long
int N, L;
struct st
{
vector<int>r;
vector<int>lazy;
int treeN;
void init(int cnt)
{
for (treeN = 1; treeN < cnt; treeN *= 2);
r.resize(2 * treeN + 3, 1);
lazy.resize(2 * treeN + 3, 1);
}
void ul(int n)
{
if (lazy[n] == 1)
return;
if (n < treeN)
{
lazy[n * 2] *= lazy[n];
lazy[n * 2] %= L;
lazy[n * 2+1] *= lazy[n];
lazy[n * 2+1] %= L;
}
else
{
r[n] *= lazy[n];
r[n] %= L;
}
lazy[n] = 1;
}
void upd(int qs, int qe,int n, int s, int e, int i = 1)
{
if (s > qe || qs > e)
return;
if (qs <= s && e <= qe)
{
lazy[i] *= n;
lazy[i] %= L;
ul(i);
return;
}
upd(qs, qe, n, s, (s + e) / 2, i * 2);
upd(qs, qe, n, (s + e) / 2 + 1, e, i * 2 + 1);
}
int ge(int qs, int qe, int n,int i = 1)
{
ul(i);
if (qs == qe)
{
return r[i];
}
int m = (qs + qe) / 2;
if (n > m)
{
return ge(m+1,qe, n, i * 2 + 1);
}
else
{
return ge(qs, m, n, i * 2);
}
}
}arr[200100];
int d[201000];
int pos[200100];
int par[200100];
int st[201000];
int en[200100];
int c;
vector<int>li[201000];
vector<pair<int,int>>dl[200100];
vector<int>dl2[200100];
void dfs(int n,int p=0)
{
st[n] = ++c;
dl[d[n]].push_back({ st[n],n });
dl2[d[n]].push_back(st[n]);
int i;
for (i = 0; i < li[n].size(); i++)
{
if (li[n][i] == p)
continue;
par[li[n][i]] = n;
d[li[n][i]] = d[n] + 1;
dfs(li[n][i],n);
}
en[n] = c;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> L;
int i;
for (i = 1; i < N; i++)
{
int a, b;
cin >> a >> b;
li[a].push_back(b);
li[b].push_back(a);
}
dfs(1);
for (i = 0; i <= N; i++)
{
arr[i].init(dl[i].size());
int j;
for (j = 0; j < dl[i].size(); j++)
{
pos[dl[i][j].second] = j;
}
}
for (i = 1; i <= N; i++)
{
int a;
cin >> a;
arr[d[i]].r[pos[i] + arr[d[i]].treeN] =a;
}
int Q;
cin >> Q;
while (Q--)
{
int a;
cin >> a;
if (a == 1)
{
int b, c, w;
cin >> b >> c >> w;
int j;
int dp = d[b];
int cp = b;
for (j = dp + c; j >= dp - c; j--)
{
if (j + dp - d[cp] * 2 + 2 <= c && cp != 1)
{
cp = par[cp];
}
if (j < 0)
break;
int lp = lower_bound(dl2[j].begin(), dl2[j].end(), st[cp]) - dl2[j].begin();
int rp = lower_bound(dl2[j].begin(), dl2[j].end(), en[cp]+1) - dl2[j].begin()-1;
if (lp <= rp)
{
arr[j].upd(lp, rp, w, 0, arr[j].treeN - 1);
}
}
}
else
{
int b;
cin >> b;
cout << arr[d[b]].ge(0, arr[d[b]].treeN - 1, pos[b]) << '\n';
}
}
}
Compilation message
sprinkler.cpp: In function 'void dfs(long long int, long long int)':
sprinkler.cpp:81:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (i = 0; i < li[n].size(); i++)
| ~~^~~~~~~~~~~~~~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:109:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for (j = 0; j < dl[i].size(); j++)
| ~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
25412 KB |
Output is correct |
2 |
Correct |
14 ms |
25408 KB |
Output is correct |
3 |
Correct |
16 ms |
25436 KB |
Output is correct |
4 |
Correct |
20 ms |
25628 KB |
Output is correct |
5 |
Correct |
21 ms |
25668 KB |
Output is correct |
6 |
Correct |
20 ms |
25684 KB |
Output is correct |
7 |
Correct |
17 ms |
25688 KB |
Output is correct |
8 |
Correct |
21 ms |
25664 KB |
Output is correct |
9 |
Correct |
18 ms |
25424 KB |
Output is correct |
10 |
Correct |
19 ms |
25448 KB |
Output is correct |
11 |
Correct |
18 ms |
25428 KB |
Output is correct |
12 |
Correct |
17 ms |
25428 KB |
Output is correct |
13 |
Correct |
19 ms |
25440 KB |
Output is correct |
14 |
Correct |
19 ms |
25380 KB |
Output is correct |
15 |
Correct |
16 ms |
25428 KB |
Output is correct |
16 |
Correct |
16 ms |
25364 KB |
Output is correct |
17 |
Correct |
15 ms |
25428 KB |
Output is correct |
18 |
Correct |
17 ms |
25444 KB |
Output is correct |
19 |
Correct |
14 ms |
25424 KB |
Output is correct |
20 |
Correct |
16 ms |
25428 KB |
Output is correct |
21 |
Correct |
19 ms |
25440 KB |
Output is correct |
22 |
Correct |
19 ms |
25392 KB |
Output is correct |
23 |
Correct |
19 ms |
25344 KB |
Output is correct |
24 |
Correct |
18 ms |
25332 KB |
Output is correct |
25 |
Correct |
19 ms |
25428 KB |
Output is correct |
26 |
Correct |
17 ms |
25372 KB |
Output is correct |
27 |
Correct |
18 ms |
25448 KB |
Output is correct |
28 |
Correct |
15 ms |
25408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
25428 KB |
Output is correct |
2 |
Correct |
594 ms |
78856 KB |
Output is correct |
3 |
Correct |
913 ms |
75724 KB |
Output is correct |
4 |
Correct |
614 ms |
83728 KB |
Output is correct |
5 |
Correct |
642 ms |
77440 KB |
Output is correct |
6 |
Correct |
673 ms |
75960 KB |
Output is correct |
7 |
Correct |
700 ms |
75536 KB |
Output is correct |
8 |
Correct |
461 ms |
74808 KB |
Output is correct |
9 |
Correct |
572 ms |
92672 KB |
Output is correct |
10 |
Correct |
608 ms |
88252 KB |
Output is correct |
11 |
Correct |
441 ms |
78464 KB |
Output is correct |
12 |
Correct |
699 ms |
75776 KB |
Output is correct |
13 |
Correct |
439 ms |
74448 KB |
Output is correct |
14 |
Correct |
491 ms |
75432 KB |
Output is correct |
15 |
Correct |
540 ms |
74908 KB |
Output is correct |
16 |
Correct |
544 ms |
74652 KB |
Output is correct |
17 |
Correct |
617 ms |
74184 KB |
Output is correct |
18 |
Correct |
16 ms |
25428 KB |
Output is correct |
19 |
Correct |
15 ms |
25428 KB |
Output is correct |
20 |
Correct |
15 ms |
25428 KB |
Output is correct |
21 |
Correct |
18 ms |
25428 KB |
Output is correct |
22 |
Correct |
15 ms |
25428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
25428 KB |
Output is correct |
2 |
Correct |
594 ms |
78856 KB |
Output is correct |
3 |
Correct |
913 ms |
75724 KB |
Output is correct |
4 |
Correct |
614 ms |
83728 KB |
Output is correct |
5 |
Correct |
642 ms |
77440 KB |
Output is correct |
6 |
Correct |
673 ms |
75960 KB |
Output is correct |
7 |
Correct |
700 ms |
75536 KB |
Output is correct |
8 |
Correct |
461 ms |
74808 KB |
Output is correct |
9 |
Correct |
572 ms |
92672 KB |
Output is correct |
10 |
Correct |
608 ms |
88252 KB |
Output is correct |
11 |
Correct |
441 ms |
78464 KB |
Output is correct |
12 |
Correct |
699 ms |
75776 KB |
Output is correct |
13 |
Correct |
439 ms |
74448 KB |
Output is correct |
14 |
Correct |
491 ms |
75432 KB |
Output is correct |
15 |
Correct |
540 ms |
74908 KB |
Output is correct |
16 |
Correct |
544 ms |
74652 KB |
Output is correct |
17 |
Correct |
617 ms |
74184 KB |
Output is correct |
18 |
Correct |
16 ms |
25428 KB |
Output is correct |
19 |
Correct |
15 ms |
25428 KB |
Output is correct |
20 |
Correct |
15 ms |
25428 KB |
Output is correct |
21 |
Correct |
18 ms |
25428 KB |
Output is correct |
22 |
Correct |
15 ms |
25428 KB |
Output is correct |
23 |
Correct |
14 ms |
25428 KB |
Output is correct |
24 |
Correct |
452 ms |
78384 KB |
Output is correct |
25 |
Correct |
890 ms |
75796 KB |
Output is correct |
26 |
Correct |
557 ms |
89916 KB |
Output is correct |
27 |
Correct |
616 ms |
77028 KB |
Output is correct |
28 |
Correct |
637 ms |
76128 KB |
Output is correct |
29 |
Correct |
646 ms |
76912 KB |
Output is correct |
30 |
Correct |
495 ms |
74632 KB |
Output is correct |
31 |
Correct |
492 ms |
88012 KB |
Output is correct |
32 |
Correct |
760 ms |
87596 KB |
Output is correct |
33 |
Correct |
472 ms |
78944 KB |
Output is correct |
34 |
Correct |
907 ms |
75368 KB |
Output is correct |
35 |
Correct |
14 ms |
25428 KB |
Output is correct |
36 |
Correct |
15 ms |
25432 KB |
Output is correct |
37 |
Correct |
14 ms |
25424 KB |
Output is correct |
38 |
Correct |
15 ms |
25428 KB |
Output is correct |
39 |
Correct |
15 ms |
25352 KB |
Output is correct |
40 |
Correct |
15 ms |
25436 KB |
Output is correct |
41 |
Correct |
15 ms |
25440 KB |
Output is correct |
42 |
Correct |
17 ms |
25428 KB |
Output is correct |
43 |
Correct |
17 ms |
25372 KB |
Output is correct |
44 |
Correct |
16 ms |
25408 KB |
Output is correct |
45 |
Correct |
14 ms |
25428 KB |
Output is correct |
46 |
Correct |
15 ms |
25388 KB |
Output is correct |
47 |
Correct |
13 ms |
25428 KB |
Output is correct |
48 |
Correct |
13 ms |
25428 KB |
Output is correct |
49 |
Correct |
12 ms |
25428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
25428 KB |
Output is correct |
2 |
Correct |
1024 ms |
89748 KB |
Output is correct |
3 |
Correct |
3349 ms |
85432 KB |
Output is correct |
4 |
Correct |
1247 ms |
84860 KB |
Output is correct |
5 |
Correct |
2913 ms |
75260 KB |
Output is correct |
6 |
Correct |
2179 ms |
74256 KB |
Output is correct |
7 |
Correct |
1267 ms |
75608 KB |
Output is correct |
8 |
Correct |
417 ms |
73172 KB |
Output is correct |
9 |
Correct |
819 ms |
83428 KB |
Output is correct |
10 |
Correct |
3007 ms |
87828 KB |
Output is correct |
11 |
Correct |
1403 ms |
76456 KB |
Output is correct |
12 |
Execution timed out |
4037 ms |
75020 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
25408 KB |
Output is correct |
2 |
Correct |
837 ms |
87328 KB |
Output is correct |
3 |
Correct |
3541 ms |
82376 KB |
Output is correct |
4 |
Correct |
1249 ms |
82736 KB |
Output is correct |
5 |
Correct |
2838 ms |
77252 KB |
Output is correct |
6 |
Correct |
1983 ms |
76620 KB |
Output is correct |
7 |
Correct |
1356 ms |
74696 KB |
Output is correct |
8 |
Correct |
421 ms |
74600 KB |
Output is correct |
9 |
Correct |
799 ms |
91412 KB |
Output is correct |
10 |
Correct |
2916 ms |
88164 KB |
Output is correct |
11 |
Correct |
1385 ms |
78392 KB |
Output is correct |
12 |
Execution timed out |
4073 ms |
75468 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
25412 KB |
Output is correct |
2 |
Correct |
14 ms |
25408 KB |
Output is correct |
3 |
Correct |
16 ms |
25436 KB |
Output is correct |
4 |
Correct |
20 ms |
25628 KB |
Output is correct |
5 |
Correct |
21 ms |
25668 KB |
Output is correct |
6 |
Correct |
20 ms |
25684 KB |
Output is correct |
7 |
Correct |
17 ms |
25688 KB |
Output is correct |
8 |
Correct |
21 ms |
25664 KB |
Output is correct |
9 |
Correct |
18 ms |
25424 KB |
Output is correct |
10 |
Correct |
19 ms |
25448 KB |
Output is correct |
11 |
Correct |
18 ms |
25428 KB |
Output is correct |
12 |
Correct |
17 ms |
25428 KB |
Output is correct |
13 |
Correct |
19 ms |
25440 KB |
Output is correct |
14 |
Correct |
19 ms |
25380 KB |
Output is correct |
15 |
Correct |
16 ms |
25428 KB |
Output is correct |
16 |
Correct |
16 ms |
25364 KB |
Output is correct |
17 |
Correct |
15 ms |
25428 KB |
Output is correct |
18 |
Correct |
17 ms |
25444 KB |
Output is correct |
19 |
Correct |
14 ms |
25424 KB |
Output is correct |
20 |
Correct |
16 ms |
25428 KB |
Output is correct |
21 |
Correct |
19 ms |
25440 KB |
Output is correct |
22 |
Correct |
19 ms |
25392 KB |
Output is correct |
23 |
Correct |
19 ms |
25344 KB |
Output is correct |
24 |
Correct |
18 ms |
25332 KB |
Output is correct |
25 |
Correct |
19 ms |
25428 KB |
Output is correct |
26 |
Correct |
17 ms |
25372 KB |
Output is correct |
27 |
Correct |
18 ms |
25448 KB |
Output is correct |
28 |
Correct |
15 ms |
25408 KB |
Output is correct |
29 |
Correct |
15 ms |
25428 KB |
Output is correct |
30 |
Correct |
594 ms |
78856 KB |
Output is correct |
31 |
Correct |
913 ms |
75724 KB |
Output is correct |
32 |
Correct |
614 ms |
83728 KB |
Output is correct |
33 |
Correct |
642 ms |
77440 KB |
Output is correct |
34 |
Correct |
673 ms |
75960 KB |
Output is correct |
35 |
Correct |
700 ms |
75536 KB |
Output is correct |
36 |
Correct |
461 ms |
74808 KB |
Output is correct |
37 |
Correct |
572 ms |
92672 KB |
Output is correct |
38 |
Correct |
608 ms |
88252 KB |
Output is correct |
39 |
Correct |
441 ms |
78464 KB |
Output is correct |
40 |
Correct |
699 ms |
75776 KB |
Output is correct |
41 |
Correct |
439 ms |
74448 KB |
Output is correct |
42 |
Correct |
491 ms |
75432 KB |
Output is correct |
43 |
Correct |
540 ms |
74908 KB |
Output is correct |
44 |
Correct |
544 ms |
74652 KB |
Output is correct |
45 |
Correct |
617 ms |
74184 KB |
Output is correct |
46 |
Correct |
16 ms |
25428 KB |
Output is correct |
47 |
Correct |
15 ms |
25428 KB |
Output is correct |
48 |
Correct |
15 ms |
25428 KB |
Output is correct |
49 |
Correct |
18 ms |
25428 KB |
Output is correct |
50 |
Correct |
15 ms |
25428 KB |
Output is correct |
51 |
Correct |
14 ms |
25428 KB |
Output is correct |
52 |
Correct |
452 ms |
78384 KB |
Output is correct |
53 |
Correct |
890 ms |
75796 KB |
Output is correct |
54 |
Correct |
557 ms |
89916 KB |
Output is correct |
55 |
Correct |
616 ms |
77028 KB |
Output is correct |
56 |
Correct |
637 ms |
76128 KB |
Output is correct |
57 |
Correct |
646 ms |
76912 KB |
Output is correct |
58 |
Correct |
495 ms |
74632 KB |
Output is correct |
59 |
Correct |
492 ms |
88012 KB |
Output is correct |
60 |
Correct |
760 ms |
87596 KB |
Output is correct |
61 |
Correct |
472 ms |
78944 KB |
Output is correct |
62 |
Correct |
907 ms |
75368 KB |
Output is correct |
63 |
Correct |
14 ms |
25428 KB |
Output is correct |
64 |
Correct |
15 ms |
25432 KB |
Output is correct |
65 |
Correct |
14 ms |
25424 KB |
Output is correct |
66 |
Correct |
15 ms |
25428 KB |
Output is correct |
67 |
Correct |
15 ms |
25352 KB |
Output is correct |
68 |
Correct |
15 ms |
25436 KB |
Output is correct |
69 |
Correct |
15 ms |
25440 KB |
Output is correct |
70 |
Correct |
17 ms |
25428 KB |
Output is correct |
71 |
Correct |
17 ms |
25372 KB |
Output is correct |
72 |
Correct |
16 ms |
25408 KB |
Output is correct |
73 |
Correct |
14 ms |
25428 KB |
Output is correct |
74 |
Correct |
15 ms |
25388 KB |
Output is correct |
75 |
Correct |
13 ms |
25428 KB |
Output is correct |
76 |
Correct |
13 ms |
25428 KB |
Output is correct |
77 |
Correct |
12 ms |
25428 KB |
Output is correct |
78 |
Correct |
16 ms |
25428 KB |
Output is correct |
79 |
Correct |
1024 ms |
89748 KB |
Output is correct |
80 |
Correct |
3349 ms |
85432 KB |
Output is correct |
81 |
Correct |
1247 ms |
84860 KB |
Output is correct |
82 |
Correct |
2913 ms |
75260 KB |
Output is correct |
83 |
Correct |
2179 ms |
74256 KB |
Output is correct |
84 |
Correct |
1267 ms |
75608 KB |
Output is correct |
85 |
Correct |
417 ms |
73172 KB |
Output is correct |
86 |
Correct |
819 ms |
83428 KB |
Output is correct |
87 |
Correct |
3007 ms |
87828 KB |
Output is correct |
88 |
Correct |
1403 ms |
76456 KB |
Output is correct |
89 |
Execution timed out |
4037 ms |
75020 KB |
Time limit exceeded |
90 |
Halted |
0 ms |
0 KB |
- |