Submission #1245941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245941		tapilyoca	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	807 ms	96008 KiB

sprinkler

/***********************************************
* auth: tapilyoca                              *
* date: 07/22/2025 at 23:51:49                 *
* dots: https://github.com/tapilyoca/dotilyoca * 
***********************************************/

#include <bits/stdc++.h>
using namespace std;

template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using vvll = vec<vll>;
using pll = pair<ll,ll>;
using str = string;
#define pb push_back
#define dbg(x) if(1) cerr << #x << ": " << x << endl;

/***********************************************/

ll MOD, n;
vll up;
vvll adj, mult;

void dfs(ll u, ll p) {
    up[u] = p;
    for(ll &v : adj[u]) if(v != p) dfs(v,u);
}

void solve() {
    cin >> n >> MOD;
    adj.resize(n); up.resize(n); mult.assign(n,vll(41,1));

    for(int i = 0; i < n-1; i++) {
        ll u, v; cin >> u >> v;
        u--; v--;
        adj[u].pb(v);
        adj[v].pb(u);
    } dfs(0,-1);

    for(int i = 0; i < n; i++) cin >> mult[i][0];
    ll q;
    cin >> q;


    // cerr << "Dfs done" << endl;

    while(q--) {
        // cerr << mult[0][0] << " " << mult[1][0] << " " << mult[2][0] << " " << mult[3][0] << endl;
        ll type;
        cin >> type;
        if(type == 1) {
            ll x, d, w;
            cin >> x >> d >> w;
            x--;

            // cerr << "Upd on " << x << " " << d << " " << w << endl;

            while(d >= 0) {
                if(up[x] == -1) {
                    for(int i = 0; i <= d; i++) mult[x][i] = (mult[x][i] * w) % MOD;
                    break;
                }
                mult[x][d] = (mult[x][d] * w) % MOD;
                if(d) mult[x][d-1] = (mult[x][d-1] * w) % MOD;
                x = up[x]; d--;
            }

        } else {
            ll x, ans = 1, at = 0;
            cin >> x; x--;
            // cerr << "qry " << x << endl;
            
            while(x != -1 and at <= 40) {
                ans = (ans * mult[x][at]) % MOD;
                x = up[x];
                at++;
            }
            cout << ans << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;

    while(t--) {
        solve();
    }

    return 0;
}

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