oj.uz

Submission #876843

# Submission time Handle Problem Language Result Execution time Memory
876843 2023-11-22T12:28:11 Z simona1230 Sprinkler (JOI22_sprinkler) C++17
100 / 100
 1281 ms 107232 KB 
#include <bits/stdc++.h>
using namespace std;
long long n,l;
vector<long long> v[200001];
long long h[200001];
void read()
{
    cin>>n>>l;
    for(long long i=1;i<n;i++)
    {
        long long a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(long long i=1;i<=n;i++)
        cin>>h[i];
}
long long curr[200001][45];
long long q,t,x,d,w;
long long used[200001];
long long p[200001];
void dfs(long long i)
{
    used[i]=1;
    for(long long j=0;j<v[i].size();j++)
    {
        long long nb=v[i][j];
        if(!used[nb])
        {
            p[nb]=i;
            dfs(nb);
        }
    }
}
void upd(long long i,long long lvl)
{
    curr[i][lvl]*=w;
    curr[i][lvl]%=l;
    if(lvl>0)
    {
        curr[i][lvl-1]*=w;
        curr[i][lvl-1]%=l;
    }
    if(i==1)
    {
        for(int j=0;j<lvl-1;j++)
        {
            curr[i][j]*=w;
            curr[i][j]%=l;
        }
    }
    if(i!=1&&lvl!=0)
        upd(p[i],lvl-1);
}
long long get(long long i,long long lvl)
{
    long long here=curr[i][lvl];
    if(i!=1&&lvl!=40)
        here*=get(p[i],lvl+1);
    return here%l;
}
void solve()
{
    for(long long i=1;i<=n;i++)
        for(long long j=0;j<=40;j++)
            curr[i][j]=1;
    dfs(1);
    cin>>q;
    for(long long i=1;i<=q;i++)
    {
        cin>>t>>x;
        if(t==1)
        {
            cin>>d>>w;
            upd(x,d);
        }
        else
        {
            cout<<(get(x,0)*h[x])%l<<endl;
        }
    }
}
int main()
{
    read();
    solve();
    return 0;
}

Compilation message

sprinkler.cpp: In function 'void dfs(long long int)':
sprinkler.cpp:26:24: 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]
   26 |     for(long long j=0;j<v[i].size();j++)
      |                       ~^~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Correct 2 ms 12372 KB Output is correct
3 Correct 2 ms 12376 KB Output is correct
4 Correct 5 ms 12380 KB Output is correct
5 Correct 6 ms 12380 KB Output is correct
6 Correct 5 ms 12464 KB Output is correct
7 Correct 4 ms 12376 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 4 ms 12380 KB Output is correct
10 Correct 3 ms 12380 KB Output is correct
11 Correct 3 ms 12256 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 3 ms 12380 KB Output is correct
15 Correct 3 ms 12380 KB Output is correct
16 Correct 4 ms 12380 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 4 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 3 ms 12380 KB Output is correct
21 Correct 3 ms 12380 KB Output is correct
22 Correct 3 ms 12380 KB Output is correct
23 Correct 3 ms 12376 KB Output is correct
24 Correct 3 ms 12380 KB Output is correct
25 Correct 3 ms 12380 KB Output is correct
26 Correct 4 ms 12380 KB Output is correct
27 Correct 3 ms 12376 KB Output is correct
28 Correct 4 ms 12380 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 1068 ms 91200 KB Output is correct
3 Correct 657 ms 88208 KB Output is correct
4 Correct 899 ms 94880 KB Output is correct
5 Correct 846 ms 89432 KB Output is correct
6 Correct 720 ms 89308 KB Output is correct
7 Correct 728 ms 90024 KB Output is correct
8 Correct 680 ms 89948 KB Output is correct
9 Correct 1193 ms 99308 KB Output is correct
10 Correct 661 ms 95464 KB Output is correct
11 Correct 1094 ms 91120 KB Output is correct
12 Correct 645 ms 99660 KB Output is correct
13 Correct 500 ms 99800 KB Output is correct
14 Correct 517 ms 100368 KB Output is correct
15 Correct 534 ms 99644 KB Output is correct
16 Correct 526 ms 100136 KB Output is correct
17 Correct 573 ms 100592 KB Output is correct
18 Correct 3 ms 12380 KB Output is correct
19 Correct 4 ms 12400 KB Output is correct
20 Correct 4 ms 12380 KB Output is correct
21 Correct 4 ms 12380 KB Output is correct
22 Correct 3 ms 12276 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 1068 ms 91200 KB Output is correct
3 Correct 657 ms 88208 KB Output is correct
4 Correct 899 ms 94880 KB Output is correct
5 Correct 846 ms 89432 KB Output is correct
6 Correct 720 ms 89308 KB Output is correct
7 Correct 728 ms 90024 KB Output is correct
8 Correct 680 ms 89948 KB Output is correct
9 Correct 1193 ms 99308 KB Output is correct
10 Correct 661 ms 95464 KB Output is correct
11 Correct 1094 ms 91120 KB Output is correct
12 Correct 645 ms 99660 KB Output is correct
13 Correct 500 ms 99800 KB Output is correct
14 Correct 517 ms 100368 KB Output is correct
15 Correct 534 ms 99644 KB Output is correct
16 Correct 526 ms 100136 KB Output is correct
17 Correct 573 ms 100592 KB Output is correct
18 Correct 3 ms 12380 KB Output is correct
19 Correct 4 ms 12400 KB Output is correct
20 Correct 4 ms 12380 KB Output is correct
21 Correct 4 ms 12380 KB Output is correct
22 Correct 3 ms 12276 KB Output is correct
23 Correct 3 ms 12380 KB Output is correct
24 Correct 1089 ms 99220 KB Output is correct
25 Correct 744 ms 99840 KB Output is correct
26 Correct 946 ms 107104 KB Output is correct
27 Correct 864 ms 99564 KB Output is correct
28 Correct 751 ms 99568 KB Output is correct
29 Correct 726 ms 99572 KB Output is correct
30 Correct 721 ms 100216 KB Output is correct
31 Correct 1171 ms 104620 KB Output is correct
32 Correct 661 ms 107232 KB Output is correct
33 Correct 1102 ms 99288 KB Output is correct
34 Correct 654 ms 99728 KB Output is correct
35 Correct 3 ms 12376 KB Output is correct
36 Correct 3 ms 12380 KB Output is correct
37 Correct 3 ms 12384 KB Output is correct
38 Correct 3 ms 12380 KB Output is correct
39 Correct 4 ms 12276 KB Output is correct
40 Correct 3 ms 12380 KB Output is correct
41 Correct 3 ms 12380 KB Output is correct
42 Correct 3 ms 12380 KB Output is correct
43 Correct 3 ms 12376 KB Output is correct
44 Correct 3 ms 12380 KB Output is correct
45 Correct 3 ms 12380 KB Output is correct
46 Correct 3 ms 12384 KB Output is correct
47 Correct 6 ms 12376 KB Output is correct
48 Correct 3 ms 12380 KB Output is correct
49 Correct 5 ms 12380 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Correct 1167 ms 96312 KB Output is correct
3 Correct 892 ms 93520 KB Output is correct
4 Correct 960 ms 94168 KB Output is correct
5 Correct 856 ms 87892 KB Output is correct
6 Correct 810 ms 88416 KB Output is correct
7 Correct 723 ms 88624 KB Output is correct
8 Correct 642 ms 88612 KB Output is correct
9 Correct 1176 ms 94176 KB Output is correct
10 Correct 926 ms 95276 KB Output is correct
11 Correct 1082 ms 88316 KB Output is correct
12 Correct 746 ms 87528 KB Output is correct
13 Correct 606 ms 88560 KB Output is correct
14 Correct 610 ms 89832 KB Output is correct
15 Correct 3 ms 12380 KB Output is correct
16 Correct 3 ms 12380 KB Output is correct
17 Correct 3 ms 12380 KB Output is correct
18 Correct 3 ms 12380 KB Output is correct
19 Correct 3 ms 12380 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Correct 1256 ms 95952 KB Output is correct
3 Correct 940 ms 97080 KB Output is correct
4 Correct 1000 ms 102372 KB Output is correct
5 Correct 939 ms 98096 KB Output is correct
6 Correct 792 ms 98312 KB Output is correct
7 Correct 699 ms 97988 KB Output is correct
8 Correct 658 ms 98236 KB Output is correct
9 Correct 1281 ms 106324 KB Output is correct
10 Correct 911 ms 105008 KB Output is correct
11 Correct 1165 ms 99100 KB Output is correct
12 Correct 794 ms 97456 KB Output is correct
13 Correct 600 ms 98076 KB Output is correct
14 Correct 607 ms 98932 KB Output is correct
15 Correct 3 ms 12632 KB Output is correct
16 Correct 4 ms 12380 KB Output is correct
17 Correct 3 ms 12380 KB Output is correct
18 Correct 3 ms 12380 KB Output is correct
19 Correct 3 ms 12380 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Correct 2 ms 12372 KB Output is correct
3 Correct 2 ms 12376 KB Output is correct
4 Correct 5 ms 12380 KB Output is correct
5 Correct 6 ms 12380 KB Output is correct
6 Correct 5 ms 12464 KB Output is correct
7 Correct 4 ms 12376 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 4 ms 12380 KB Output is correct
10 Correct 3 ms 12380 KB Output is correct
11 Correct 3 ms 12256 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 3 ms 12380 KB Output is correct
15 Correct 3 ms 12380 KB Output is correct
16 Correct 4 ms 12380 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 4 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 3 ms 12380 KB Output is correct
21 Correct 3 ms 12380 KB Output is correct
22 Correct 3 ms 12380 KB Output is correct
23 Correct 3 ms 12376 KB Output is correct
24 Correct 3 ms 12380 KB Output is correct
25 Correct 3 ms 12380 KB Output is correct
26 Correct 4 ms 12380 KB Output is correct
27 Correct 3 ms 12376 KB Output is correct
28 Correct 4 ms 12380 KB Output is correct
29 Correct 3 ms 12380 KB Output is correct
30 Correct 1068 ms 91200 KB Output is correct
31 Correct 657 ms 88208 KB Output is correct
32 Correct 899 ms 94880 KB Output is correct
33 Correct 846 ms 89432 KB Output is correct
34 Correct 720 ms 89308 KB Output is correct
35 Correct 728 ms 90024 KB Output is correct
36 Correct 680 ms 89948 KB Output is correct
37 Correct 1193 ms 99308 KB Output is correct
38 Correct 661 ms 95464 KB Output is correct
39 Correct 1094 ms 91120 KB Output is correct
40 Correct 645 ms 99660 KB Output is correct
41 Correct 500 ms 99800 KB Output is correct
42 Correct 517 ms 100368 KB Output is correct
43 Correct 534 ms 99644 KB Output is correct
44 Correct 526 ms 100136 KB Output is correct
45 Correct 573 ms 100592 KB Output is correct
46 Correct 3 ms 12380 KB Output is correct
47 Correct 4 ms 12400 KB Output is correct
48 Correct 4 ms 12380 KB Output is correct
49 Correct 4 ms 12380 KB Output is correct
50 Correct 3 ms 12276 KB Output is correct
51 Correct 3 ms 12380 KB Output is correct
52 Correct 1089 ms 99220 KB Output is correct
53 Correct 744 ms 99840 KB Output is correct
54 Correct 946 ms 107104 KB Output is correct
55 Correct 864 ms 99564 KB Output is correct
56 Correct 751 ms 99568 KB Output is correct
57 Correct 726 ms 99572 KB Output is correct
58 Correct 721 ms 100216 KB Output is correct
59 Correct 1171 ms 104620 KB Output is correct
60 Correct 661 ms 107232 KB Output is correct
61 Correct 1102 ms 99288 KB Output is correct
62 Correct 654 ms 99728 KB Output is correct
63 Correct 3 ms 12376 KB Output is correct
64 Correct 3 ms 12380 KB Output is correct
65 Correct 3 ms 12384 KB Output is correct
66 Correct 3 ms 12380 KB Output is correct
67 Correct 4 ms 12276 KB Output is correct
68 Correct 3 ms 12380 KB Output is correct
69 Correct 3 ms 12380 KB Output is correct
70 Correct 3 ms 12380 KB Output is correct
71 Correct 3 ms 12376 KB Output is correct
72 Correct 3 ms 12380 KB Output is correct
73 Correct 3 ms 12380 KB Output is correct
74 Correct 3 ms 12384 KB Output is correct
75 Correct 6 ms 12376 KB Output is correct
76 Correct 3 ms 12380 KB Output is correct
77 Correct 5 ms 12380 KB Output is correct
78 Correct 2 ms 12380 KB Output is correct
79 Correct 1167 ms 96312 KB Output is correct
80 Correct 892 ms 93520 KB Output is correct
81 Correct 960 ms 94168 KB Output is correct
82 Correct 856 ms 87892 KB Output is correct
83 Correct 810 ms 88416 KB Output is correct
84 Correct 723 ms 88624 KB Output is correct
85 Correct 642 ms 88612 KB Output is correct
86 Correct 1176 ms 94176 KB Output is correct
87 Correct 926 ms 95276 KB Output is correct
88 Correct 1082 ms 88316 KB Output is correct
89 Correct 746 ms 87528 KB Output is correct
90 Correct 606 ms 88560 KB Output is correct
91 Correct 610 ms 89832 KB Output is correct
92 Correct 3 ms 12380 KB Output is correct
93 Correct 3 ms 12380 KB Output is correct
94 Correct 3 ms 12380 KB Output is correct
95 Correct 3 ms 12380 KB Output is correct
96 Correct 3 ms 12380 KB Output is correct
97 Correct 2 ms 12380 KB Output is correct
98 Correct 1256 ms 95952 KB Output is correct
99 Correct 940 ms 97080 KB Output is correct
100 Correct 1000 ms 102372 KB Output is correct
101 Correct 939 ms 98096 KB Output is correct
102 Correct 792 ms 98312 KB Output is correct
103 Correct 699 ms 97988 KB Output is correct
104 Correct 658 ms 98236 KB Output is correct
105 Correct 1281 ms 106324 KB Output is correct
106 Correct 911 ms 105008 KB Output is correct
107 Correct 1165 ms 99100 KB Output is correct
108 Correct 794 ms 97456 KB Output is correct
109 Correct 600 ms 98076 KB Output is correct
110 Correct 607 ms 98932 KB Output is correct
111 Correct 3 ms 12632 KB Output is correct
112 Correct 4 ms 12380 KB Output is correct
113 Correct 3 ms 12380 KB Output is correct
114 Correct 3 ms 12380 KB Output is correct
115 Correct 3 ms 12380 KB Output is correct
116 Correct 1113 ms 97576 KB Output is correct
117 Correct 857 ms 99956 KB Output is correct
118 Correct 1044 ms 107128 KB Output is correct
119 Correct 1000 ms 99620 KB Output is correct
120 Correct 807 ms 99156 KB Output is correct
121 Correct 817 ms 100064 KB Output is correct
122 Correct 689 ms 100172 KB Output is correct
123 Correct 1195 ms 105332 KB Output is correct
124 Correct 994 ms 104032 KB Output is correct
125 Correct 1173 ms 98384 KB Output is correct
126 Correct 892 ms 99692 KB Output is correct
127 Correct 968 ms 100376 KB Output is correct
128 Correct 773 ms 100944 KB Output is correct
129 Correct 801 ms 101880 KB Output is correct