oj.uz

Submission #824073

# Submission time Handle Problem Language Result Execution time Memory
824073 2023-08-13T13:01:35 Z Cookie Sprinkler (JOI22_sprinkler) C++14
100 / 100
 692 ms 96440 KB 
#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>

const ll mod = 1e9 + 7;
const int mxn = 2e5, mxr = 25e3, sq = 500, mxv = 1e6 + 5, mxvv = 130;
int n, l;
vt<int>adj[mxn + 1];
ll comp[mxn  + 1][41], h[mxn + 5], pa[mxn + 4];
void dfs(int s, int pre){
    pa[s] = pre;
    for(auto i: adj[s]){
        if(i != pre){
            dfs(i, s);
        }
    }
}
void solve(ll x, ll d, ll w){
    if(d == -1)return;
    if(x == 1){
        for(int i = 0; i <= d; i++){
            comp[x][i] = (comp[x][i] * w) % l;
        }
        return;
    }
    
    if(d){
        comp[x][d - 1] = (comp[x][d - 1] * w) % l;
    }
    comp[x][d] = (comp[x][d] * w) % l;
    int to = pa[x];
    solve(to, d - 1, w);
}
int main(){
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     cin >> n >> l;
     for(int i = 1; i <= n; i++){
         for(int j = 0; j <= 40; j++){
             comp[i][j] = 1;
         }
     }
     for(int i = 1; i < n; i++){
         int u, v; cin >> u >> v;
         adj[u].pb(v); adj[v].pb(u);
     }
    dfs(1, -1);
    for(int i = 1; i <= n; i++)cin >> h[i];
    int q; cin >> q;
    while(q--){
        int idq; cin >> idq;
        if(idq == 1){
            ll x, d, w; cin >> x >> d >> w;
            solve(x, d, w);
        }else{
            int x; cin >> x;
            int cnt = 0;
            ll ans = h[x];
            while(1){
                ans = (ans * comp[x][cnt]) % l;
                x = pa[x]; cnt++;
                if(cnt > 40 || x  == -1)break;
            }
            cout << ans << "\n";
        }
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5460 KB Output is correct
5 Correct 3 ms 5424 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 3 ms 5460 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 2 ms 5032 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 2 ms 5048 KB Output is correct
12 Correct 2 ms 5040 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 5076 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5032 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 2 ms 5024 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 3 ms 5020 KB Output is correct
24 Correct 3 ms 5028 KB Output is correct
25 Correct 2 ms 5024 KB Output is correct
26 Correct 2 ms 5076 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 2 ms 4948 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 464 ms 90492 KB Output is correct
3 Correct 311 ms 90956 KB Output is correct
4 Correct 427 ms 94528 KB Output is correct
5 Correct 372 ms 90800 KB Output is correct
6 Correct 266 ms 90188 KB Output is correct
7 Correct 278 ms 90932 KB Output is correct
8 Correct 215 ms 91428 KB Output is correct
9 Correct 555 ms 96156 KB Output is correct
10 Correct 298 ms 96300 KB Output is correct
11 Correct 454 ms 90408 KB Output is correct
12 Correct 274 ms 90904 KB Output is correct
13 Correct 198 ms 91240 KB Output is correct
14 Correct 191 ms 91712 KB Output is correct
15 Correct 186 ms 90992 KB Output is correct
16 Correct 188 ms 91596 KB Output is correct
17 Correct 196 ms 92004 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 2 ms 5036 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 2 ms 5040 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 464 ms 90492 KB Output is correct
3 Correct 311 ms 90956 KB Output is correct
4 Correct 427 ms 94528 KB Output is correct
5 Correct 372 ms 90800 KB Output is correct
6 Correct 266 ms 90188 KB Output is correct
7 Correct 278 ms 90932 KB Output is correct
8 Correct 215 ms 91428 KB Output is correct
9 Correct 555 ms 96156 KB Output is correct
10 Correct 298 ms 96300 KB Output is correct
11 Correct 454 ms 90408 KB Output is correct
12 Correct 274 ms 90904 KB Output is correct
13 Correct 198 ms 91240 KB Output is correct
14 Correct 191 ms 91712 KB Output is correct
15 Correct 186 ms 90992 KB Output is correct
16 Correct 188 ms 91596 KB Output is correct
17 Correct 196 ms 92004 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 2 ms 5036 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 2 ms 5040 KB Output is correct
23 Correct 2 ms 4948 KB Output is correct
24 Correct 457 ms 90356 KB Output is correct
25 Correct 287 ms 90956 KB Output is correct
26 Correct 456 ms 96440 KB Output is correct
27 Correct 391 ms 90668 KB Output is correct
28 Correct 283 ms 90828 KB Output is correct
29 Correct 254 ms 90472 KB Output is correct
30 Correct 233 ms 91444 KB Output is correct
31 Correct 546 ms 94516 KB Output is correct
32 Correct 308 ms 96336 KB Output is correct
33 Correct 474 ms 90348 KB Output is correct
34 Correct 312 ms 90884 KB Output is correct
35 Correct 3 ms 4948 KB Output is correct
36 Correct 2 ms 5076 KB Output is correct
37 Correct 2 ms 5076 KB Output is correct
38 Correct 2 ms 5036 KB Output is correct
39 Correct 2 ms 5076 KB Output is correct
40 Correct 2 ms 4948 KB Output is correct
41 Correct 2 ms 4948 KB Output is correct
42 Correct 2 ms 4948 KB Output is correct
43 Correct 2 ms 4948 KB Output is correct
44 Correct 2 ms 5028 KB Output is correct
45 Correct 2 ms 5032 KB Output is correct
46 Correct 2 ms 4948 KB Output is correct
47 Correct 2 ms 5036 KB Output is correct
48 Correct 2 ms 4948 KB Output is correct
49 Correct 2 ms 5076 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 572 ms 85464 KB Output is correct
3 Correct 628 ms 83164 KB Output is correct
4 Correct 520 ms 83820 KB Output is correct
5 Correct 448 ms 79024 KB Output is correct
6 Correct 275 ms 79176 KB Output is correct
7 Correct 259 ms 79284 KB Output is correct
8 Correct 225 ms 79704 KB Output is correct
9 Correct 549 ms 83732 KB Output is correct
10 Correct 663 ms 84136 KB Output is correct
11 Correct 480 ms 79384 KB Output is correct
12 Correct 491 ms 78752 KB Output is correct
13 Correct 345 ms 79528 KB Output is correct
14 Correct 350 ms 80032 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 5020 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 571 ms 86056 KB Output is correct
3 Correct 681 ms 91636 KB Output is correct
4 Correct 527 ms 92780 KB Output is correct
5 Correct 447 ms 89320 KB Output is correct
6 Correct 306 ms 89444 KB Output is correct
7 Correct 290 ms 89204 KB Output is correct
8 Correct 216 ms 89560 KB Output is correct
9 Correct 568 ms 95604 KB Output is correct
10 Correct 641 ms 94100 KB Output is correct
11 Correct 471 ms 90000 KB Output is correct
12 Correct 501 ms 88484 KB Output is correct
13 Correct 350 ms 89272 KB Output is correct
14 Correct 355 ms 89716 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 5028 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5460 KB Output is correct
5 Correct 3 ms 5424 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 3 ms 5460 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 2 ms 5032 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 2 ms 5048 KB Output is correct
12 Correct 2 ms 5040 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 5076 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5032 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 2 ms 5024 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 3 ms 5020 KB Output is correct
24 Correct 3 ms 5028 KB Output is correct
25 Correct 2 ms 5024 KB Output is correct
26 Correct 2 ms 5076 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 2 ms 4948 KB Output is correct
29 Correct 2 ms 4948 KB Output is correct
30 Correct 464 ms 90492 KB Output is correct
31 Correct 311 ms 90956 KB Output is correct
32 Correct 427 ms 94528 KB Output is correct
33 Correct 372 ms 90800 KB Output is correct
34 Correct 266 ms 90188 KB Output is correct
35 Correct 278 ms 90932 KB Output is correct
36 Correct 215 ms 91428 KB Output is correct
37 Correct 555 ms 96156 KB Output is correct
38 Correct 298 ms 96300 KB Output is correct
39 Correct 454 ms 90408 KB Output is correct
40 Correct 274 ms 90904 KB Output is correct
41 Correct 198 ms 91240 KB Output is correct
42 Correct 191 ms 91712 KB Output is correct
43 Correct 186 ms 90992 KB Output is correct
44 Correct 188 ms 91596 KB Output is correct
45 Correct 196 ms 92004 KB Output is correct
46 Correct 3 ms 4948 KB Output is correct
47 Correct 3 ms 5076 KB Output is correct
48 Correct 2 ms 5036 KB Output is correct
49 Correct 3 ms 5076 KB Output is correct
50 Correct 2 ms 5040 KB Output is correct
51 Correct 2 ms 4948 KB Output is correct
52 Correct 457 ms 90356 KB Output is correct
53 Correct 287 ms 90956 KB Output is correct
54 Correct 456 ms 96440 KB Output is correct
55 Correct 391 ms 90668 KB Output is correct
56 Correct 283 ms 90828 KB Output is correct
57 Correct 254 ms 90472 KB Output is correct
58 Correct 233 ms 91444 KB Output is correct
59 Correct 546 ms 94516 KB Output is correct
60 Correct 308 ms 96336 KB Output is correct
61 Correct 474 ms 90348 KB Output is correct
62 Correct 312 ms 90884 KB Output is correct
63 Correct 3 ms 4948 KB Output is correct
64 Correct 2 ms 5076 KB Output is correct
65 Correct 2 ms 5076 KB Output is correct
66 Correct 2 ms 5036 KB Output is correct
67 Correct 2 ms 5076 KB Output is correct
68 Correct 2 ms 4948 KB Output is correct
69 Correct 2 ms 4948 KB Output is correct
70 Correct 2 ms 4948 KB Output is correct
71 Correct 2 ms 4948 KB Output is correct
72 Correct 2 ms 5028 KB Output is correct
73 Correct 2 ms 5032 KB Output is correct
74 Correct 2 ms 4948 KB Output is correct
75 Correct 2 ms 5036 KB Output is correct
76 Correct 2 ms 4948 KB Output is correct
77 Correct 2 ms 5076 KB Output is correct
78 Correct 2 ms 4948 KB Output is correct
79 Correct 572 ms 85464 KB Output is correct
80 Correct 628 ms 83164 KB Output is correct
81 Correct 520 ms 83820 KB Output is correct
82 Correct 448 ms 79024 KB Output is correct
83 Correct 275 ms 79176 KB Output is correct
84 Correct 259 ms 79284 KB Output is correct
85 Correct 225 ms 79704 KB Output is correct
86 Correct 549 ms 83732 KB Output is correct
87 Correct 663 ms 84136 KB Output is correct
88 Correct 480 ms 79384 KB Output is correct
89 Correct 491 ms 78752 KB Output is correct
90 Correct 345 ms 79528 KB Output is correct
91 Correct 350 ms 80032 KB Output is correct
92 Correct 2 ms 4948 KB Output is correct
93 Correct 2 ms 4948 KB Output is correct
94 Correct 2 ms 5020 KB Output is correct
95 Correct 2 ms 4948 KB Output is correct
96 Correct 3 ms 4948 KB Output is correct
97 Correct 2 ms 4948 KB Output is correct
98 Correct 571 ms 86056 KB Output is correct
99 Correct 681 ms 91636 KB Output is correct
100 Correct 527 ms 92780 KB Output is correct
101 Correct 447 ms 89320 KB Output is correct
102 Correct 306 ms 89444 KB Output is correct
103 Correct 290 ms 89204 KB Output is correct
104 Correct 216 ms 89560 KB Output is correct
105 Correct 568 ms 95604 KB Output is correct
106 Correct 641 ms 94100 KB Output is correct
107 Correct 471 ms 90000 KB Output is correct
108 Correct 501 ms 88484 KB Output is correct
109 Correct 350 ms 89272 KB Output is correct
110 Correct 355 ms 89716 KB Output is correct
111 Correct 2 ms 4948 KB Output is correct
112 Correct 2 ms 4948 KB Output is correct
113 Correct 2 ms 4948 KB Output is correct
114 Correct 2 ms 4948 KB Output is correct
115 Correct 2 ms 5028 KB Output is correct
116 Correct 528 ms 88488 KB Output is correct
117 Correct 530 ms 91036 KB Output is correct
118 Correct 587 ms 96248 KB Output is correct
119 Correct 483 ms 90768 KB Output is correct
120 Correct 347 ms 90360 KB Output is correct
121 Correct 314 ms 91112 KB Output is correct
122 Correct 284 ms 91456 KB Output is correct
123 Correct 613 ms 95212 KB Output is correct
124 Correct 692 ms 94288 KB Output is correct
125 Correct 488 ms 89808 KB Output is correct
126 Correct 567 ms 90892 KB Output is correct
127 Correct 545 ms 91364 KB Output is correct
128 Correct 451 ms 92296 KB Output is correct
129 Correct 511 ms 92548 KB Output is correct