Submission #952799

#	Time	Username	Problem	Language	Result	Execution time	Memory
952799		vladilius	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1112 ms	82024 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int sz = 45;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, L; cin>>n>>L;
    vector<int> g[n + 1];
    for (int i = 1; i < n; i++){
        int a, b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> h(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>h[i];
    }
    
    vector<int> p(n + 1);
    function<void(int, int)> dfs = [&](int v, int pr){
        p[v] = pr;
        for (int i: g[v]){
            if (i == pr) continue;
            dfs(i, v);
        }
    };
    dfs(1, 0);
    
    vector<vector<int>> T(n + 1, vector<int>(sz, 1));
    
    int q; cin>>q;
    while (q--){
        int type, x; cin>>type>>x;
        if (type == 1){
            int d, w; cin>>d>>w;
            while (x > 1 && d >= 0){
                T[x][d] = (1LL * T[x][d] * w) % L;
                if (d) T[x][d - 1] = (1LL * T[x][d - 1] * w) % L;
                x = p[x];
                d--;
            }
            for (int i = 0; i <= d; i++){
                T[x][i] = (1LL * T[x][i] * w) % L;
            }
        }
        else {
            int out = h[x];
            for (int i = 0; i < sz; i++){
                out = (1LL * out * T[x][i]) % L;
                x = p[x];
            }
            cout<<out<<"\n";
        }
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17