oj.uz

Submission #824072

# Submission time Handle Problem Language Result Execution time Memory
824072 2023-08-13T13:00:00 Z Cookie Sprinkler (JOI22_sprinkler) C++14
12 / 100
 777 ms 93988 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]) % mod;
                x = pa[x]; cnt++;
                if(cnt > 40 || x  == -1)break;
            }
            cout << ans << "\n";
        }
    }
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5028 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 777 ms 93468 KB Output is correct
3 Correct 686 ms 92624 KB Output is correct
4 Correct 608 ms 92428 KB Output is correct
5 Correct 484 ms 87756 KB Output is correct
6 Correct 307 ms 88052 KB Output is correct
7 Correct 277 ms 87976 KB Output is correct
8 Correct 214 ms 88500 KB Output is correct
9 Correct 765 ms 91656 KB Output is correct
10 Correct 659 ms 93420 KB Output is correct
11 Correct 582 ms 87304 KB Output is correct
12 Correct 514 ms 88244 KB Output is correct
13 Correct 373 ms 89080 KB Output is correct
14 Correct 388 ms 89760 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 4948 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 776 ms 93988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5028 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -