oj.uz

Submission #892583

# Submission time Handle Problem Language Result Execution time Memory
892583 2023-12-25T14:26:51 Z vjudge1 Sprinkler (JOI22_sprinkler) C++17
100 / 100
 1110 ms 101468 KB 
#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=2e5+5;
vector <int> g[N];
int p[N];
int dp[N][50];
void dfs(int v,int par){
    p[v]=par;
    for(auto to : g[v]){
        if(to!=par)dfs(to,v);
    }
}
signed main(){
    int n,l;
    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);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=40;j++){
            dp[i][j]=1;
        }
    }
    dfs(1,0);
    vector <int> h(n+1);
    for(int i=1;i<=n;i++){
        cin>>h[i];
        dp[i][0]=h[i];
    }
    
    int q;cin>>q;
    while(q--){
        int type,v,d,x;
        cin>>type;
        if(type==1){
            cin>>v>>d>>x;
            while(v>=1 && d>=0){
                dp[v][d]=(dp[v][d])*x%l;
                d--;
                if(d<0)break;
                dp[v][d]=(dp[v][d])*x%l;
                if(p[v]!=0)v=p[v];
                else{
                    d--;
                    if(d<0)break;
                }
            }
        }
        else{
            cin>>v;
            int ans=1;
            for(int i=0;i<=40;i++){
                if(v>=1)ans=ans*dp[v][i]%l;
                v=p[v];
            }
            cout<<ans<<"\n";
        }
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 4 ms 9052 KB Output is correct
5 Correct 4 ms 9096 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 5 ms 8904 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 3 ms 6748 KB Output is correct
13 Correct 2 ms 6744 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 3 ms 6748 KB Output is correct
17 Correct 2 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 2 ms 7000 KB Output is correct
20 Correct 2 ms 6748 KB Output is correct
21 Correct 2 ms 6748 KB Output is correct
22 Correct 2 ms 6748 KB Output is correct
23 Correct 2 ms 6748 KB Output is correct
24 Correct 2 ms 6748 KB Output is correct
25 Correct 2 ms 6744 KB Output is correct
26 Correct 2 ms 6748 KB Output is correct
27 Correct 2 ms 6744 KB Output is correct
28 Correct 2 ms 6748 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 947 ms 97440 KB Output is correct
3 Correct 582 ms 94292 KB Output is correct
4 Correct 812 ms 98644 KB Output is correct
5 Correct 748 ms 95824 KB Output is correct
6 Correct 690 ms 95572 KB Output is correct
7 Correct 711 ms 96080 KB Output is correct
8 Correct 662 ms 96292 KB Output is correct
9 Correct 1030 ms 101468 KB Output is correct
10 Correct 598 ms 97836 KB Output is correct
11 Correct 956 ms 97252 KB Output is correct
12 Correct 654 ms 94300 KB Output is correct
13 Correct 497 ms 94692 KB Output is correct
14 Correct 502 ms 94392 KB Output is correct
15 Correct 494 ms 94524 KB Output is correct
16 Correct 517 ms 94832 KB Output is correct
17 Correct 505 ms 95056 KB Output is correct
18 Correct 2 ms 6744 KB Output is correct
19 Correct 3 ms 6748 KB Output is correct
20 Correct 3 ms 6748 KB Output is correct
21 Correct 2 ms 6748 KB Output is correct
22 Correct 2 ms 6744 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 947 ms 97440 KB Output is correct
3 Correct 582 ms 94292 KB Output is correct
4 Correct 812 ms 98644 KB Output is correct
5 Correct 748 ms 95824 KB Output is correct
6 Correct 690 ms 95572 KB Output is correct
7 Correct 711 ms 96080 KB Output is correct
8 Correct 662 ms 96292 KB Output is correct
9 Correct 1030 ms 101468 KB Output is correct
10 Correct 598 ms 97836 KB Output is correct
11 Correct 956 ms 97252 KB Output is correct
12 Correct 654 ms 94300 KB Output is correct
13 Correct 497 ms 94692 KB Output is correct
14 Correct 502 ms 94392 KB Output is correct
15 Correct 494 ms 94524 KB Output is correct
16 Correct 517 ms 94832 KB Output is correct
17 Correct 505 ms 95056 KB Output is correct
18 Correct 2 ms 6744 KB Output is correct
19 Correct 3 ms 6748 KB Output is correct
20 Correct 3 ms 6748 KB Output is correct
21 Correct 2 ms 6748 KB Output is correct
22 Correct 2 ms 6744 KB Output is correct
23 Correct 1 ms 6748 KB Output is correct
24 Correct 970 ms 97392 KB Output is correct
25 Correct 630 ms 94212 KB Output is correct
26 Correct 878 ms 99892 KB Output is correct
27 Correct 855 ms 95580 KB Output is correct
28 Correct 784 ms 95736 KB Output is correct
29 Correct 789 ms 96040 KB Output is correct
30 Correct 679 ms 96188 KB Output is correct
31 Correct 1101 ms 99880 KB Output is correct
32 Correct 673 ms 97980 KB Output is correct
33 Correct 1002 ms 97360 KB Output is correct
34 Correct 642 ms 94292 KB Output is correct
35 Correct 3 ms 6748 KB Output is correct
36 Correct 2 ms 6748 KB Output is correct
37 Correct 3 ms 6748 KB Output is correct
38 Correct 2 ms 6748 KB Output is correct
39 Correct 3 ms 6748 KB Output is correct
40 Correct 2 ms 6748 KB Output is correct
41 Correct 2 ms 6744 KB Output is correct
42 Correct 2 ms 6748 KB Output is correct
43 Correct 2 ms 6748 KB Output is correct
44 Correct 2 ms 6748 KB Output is correct
45 Correct 2 ms 6748 KB Output is correct
46 Correct 2 ms 6748 KB Output is correct
47 Correct 3 ms 6744 KB Output is correct
48 Correct 2 ms 6748 KB Output is correct
49 Correct 2 ms 6748 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6772 KB Output is correct
2 Correct 1110 ms 99132 KB Output is correct
3 Correct 857 ms 96640 KB Output is correct
4 Correct 854 ms 97372 KB Output is correct
5 Correct 800 ms 94544 KB Output is correct
6 Correct 714 ms 94440 KB Output is correct
7 Correct 705 ms 94804 KB Output is correct
8 Correct 639 ms 94692 KB Output is correct
9 Correct 1029 ms 97536 KB Output is correct
10 Correct 888 ms 97520 KB Output is correct
11 Correct 965 ms 94808 KB Output is correct
12 Correct 693 ms 94156 KB Output is correct
13 Correct 571 ms 94840 KB Output is correct
14 Correct 580 ms 95600 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 2 ms 6748 KB Output is correct
17 Correct 2 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 2 ms 6748 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1053 ms 99528 KB Output is correct
3 Correct 869 ms 95756 KB Output is correct
4 Correct 852 ms 97844 KB Output is correct
5 Correct 777 ms 95976 KB Output is correct
6 Correct 722 ms 96004 KB Output is correct
7 Correct 690 ms 95824 KB Output is correct
8 Correct 634 ms 96104 KB Output is correct
9 Correct 1078 ms 100756 KB Output is correct
10 Correct 899 ms 97836 KB Output is correct
11 Correct 961 ms 97228 KB Output is correct
12 Correct 688 ms 94380 KB Output is correct
13 Correct 586 ms 94816 KB Output is correct
14 Correct 590 ms 95720 KB Output is correct
15 Correct 2 ms 7000 KB Output is correct
16 Correct 2 ms 6744 KB Output is correct
17 Correct 2 ms 6956 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 2 ms 6748 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 4 ms 9052 KB Output is correct
5 Correct 4 ms 9096 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 5 ms 8904 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 3 ms 6748 KB Output is correct
13 Correct 2 ms 6744 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 3 ms 6748 KB Output is correct
17 Correct 2 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 2 ms 7000 KB Output is correct
20 Correct 2 ms 6748 KB Output is correct
21 Correct 2 ms 6748 KB Output is correct
22 Correct 2 ms 6748 KB Output is correct
23 Correct 2 ms 6748 KB Output is correct
24 Correct 2 ms 6748 KB Output is correct
25 Correct 2 ms 6744 KB Output is correct
26 Correct 2 ms 6748 KB Output is correct
27 Correct 2 ms 6744 KB Output is correct
28 Correct 2 ms 6748 KB Output is correct
29 Correct 1 ms 6748 KB Output is correct
30 Correct 947 ms 97440 KB Output is correct
31 Correct 582 ms 94292 KB Output is correct
32 Correct 812 ms 98644 KB Output is correct
33 Correct 748 ms 95824 KB Output is correct
34 Correct 690 ms 95572 KB Output is correct
35 Correct 711 ms 96080 KB Output is correct
36 Correct 662 ms 96292 KB Output is correct
37 Correct 1030 ms 101468 KB Output is correct
38 Correct 598 ms 97836 KB Output is correct
39 Correct 956 ms 97252 KB Output is correct
40 Correct 654 ms 94300 KB Output is correct
41 Correct 497 ms 94692 KB Output is correct
42 Correct 502 ms 94392 KB Output is correct
43 Correct 494 ms 94524 KB Output is correct
44 Correct 517 ms 94832 KB Output is correct
45 Correct 505 ms 95056 KB Output is correct
46 Correct 2 ms 6744 KB Output is correct
47 Correct 3 ms 6748 KB Output is correct
48 Correct 3 ms 6748 KB Output is correct
49 Correct 2 ms 6748 KB Output is correct
50 Correct 2 ms 6744 KB Output is correct
51 Correct 1 ms 6748 KB Output is correct
52 Correct 970 ms 97392 KB Output is correct
53 Correct 630 ms 94212 KB Output is correct
54 Correct 878 ms 99892 KB Output is correct
55 Correct 855 ms 95580 KB Output is correct
56 Correct 784 ms 95736 KB Output is correct
57 Correct 789 ms 96040 KB Output is correct
58 Correct 679 ms 96188 KB Output is correct
59 Correct 1101 ms 99880 KB Output is correct
60 Correct 673 ms 97980 KB Output is correct
61 Correct 1002 ms 97360 KB Output is correct
62 Correct 642 ms 94292 KB Output is correct
63 Correct 3 ms 6748 KB Output is correct
64 Correct 2 ms 6748 KB Output is correct
65 Correct 3 ms 6748 KB Output is correct
66 Correct 2 ms 6748 KB Output is correct
67 Correct 3 ms 6748 KB Output is correct
68 Correct 2 ms 6748 KB Output is correct
69 Correct 2 ms 6744 KB Output is correct
70 Correct 2 ms 6748 KB Output is correct
71 Correct 2 ms 6748 KB Output is correct
72 Correct 2 ms 6748 KB Output is correct
73 Correct 2 ms 6748 KB Output is correct
74 Correct 2 ms 6748 KB Output is correct
75 Correct 3 ms 6744 KB Output is correct
76 Correct 2 ms 6748 KB Output is correct
77 Correct 2 ms 6748 KB Output is correct
78 Correct 1 ms 6772 KB Output is correct
79 Correct 1110 ms 99132 KB Output is correct
80 Correct 857 ms 96640 KB Output is correct
81 Correct 854 ms 97372 KB Output is correct
82 Correct 800 ms 94544 KB Output is correct
83 Correct 714 ms 94440 KB Output is correct
84 Correct 705 ms 94804 KB Output is correct
85 Correct 639 ms 94692 KB Output is correct
86 Correct 1029 ms 97536 KB Output is correct
87 Correct 888 ms 97520 KB Output is correct
88 Correct 965 ms 94808 KB Output is correct
89 Correct 693 ms 94156 KB Output is correct
90 Correct 571 ms 94840 KB Output is correct
91 Correct 580 ms 95600 KB Output is correct
92 Correct 2 ms 6748 KB Output is correct
93 Correct 2 ms 6748 KB Output is correct
94 Correct 2 ms 6748 KB Output is correct
95 Correct 2 ms 6748 KB Output is correct
96 Correct 2 ms 6748 KB Output is correct
97 Correct 1 ms 6748 KB Output is correct
98 Correct 1053 ms 99528 KB Output is correct
99 Correct 869 ms 95756 KB Output is correct
100 Correct 852 ms 97844 KB Output is correct
101 Correct 777 ms 95976 KB Output is correct
102 Correct 722 ms 96004 KB Output is correct
103 Correct 690 ms 95824 KB Output is correct
104 Correct 634 ms 96104 KB Output is correct
105 Correct 1078 ms 100756 KB Output is correct
106 Correct 899 ms 97836 KB Output is correct
107 Correct 961 ms 97228 KB Output is correct
108 Correct 688 ms 94380 KB Output is correct
109 Correct 586 ms 94816 KB Output is correct
110 Correct 590 ms 95720 KB Output is correct
111 Correct 2 ms 7000 KB Output is correct
112 Correct 2 ms 6744 KB Output is correct
113 Correct 2 ms 6956 KB Output is correct
114 Correct 2 ms 6748 KB Output is correct
115 Correct 2 ms 6748 KB Output is correct
116 Correct 973 ms 95692 KB Output is correct
117 Correct 782 ms 94036 KB Output is correct
118 Correct 900 ms 99668 KB Output is correct
119 Correct 829 ms 95868 KB Output is correct
120 Correct 762 ms 95784 KB Output is correct
121 Correct 766 ms 96336 KB Output is correct
122 Correct 686 ms 96240 KB Output is correct
123 Correct 1060 ms 100608 KB Output is correct
124 Correct 985 ms 96412 KB Output is correct
125 Correct 977 ms 96748 KB Output is correct
126 Correct 815 ms 94380 KB Output is correct
127 Correct 811 ms 93936 KB Output is correct
128 Correct 732 ms 95084 KB Output is correct
129 Correct 750 ms 96124 KB Output is correct