Submission #1287460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287460		duckindog	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	645 ms	60272 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, M, q;
vector<int> ad[N];
int h[N];

int par[N];
void dfs(int u, int p = -1) { 
    par[u] = p;
    for (const auto& v : ad[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
}

int lazy[N][50];
inline void upd(int u, int d, int x) { 
    for (; u != -1 && d >= 0; u = par[u], --d) { 
        if (par[u] == -1) { 
            for (int i = 0; i <= d; ++i) lazy[u][i] = 1ll * lazy[u][i] * x % M;
        } else if (!d) { 
            lazy[u][0] = 1ll * lazy[u][0] * x % M;
        } else { 
            lazy[u][d] = 1ll * lazy[u][d] * x % M;
            lazy[u][d - 1] = 1ll * lazy[u][d - 1] * x % M;
        }
    }
}
inline int get(int u) { 
    int ret = h[u];
    for (int d = 0; u != -1 && d <= 40; u = par[u], ++d) { 
        ret = 1ll * ret * lazy[u][d] % M;
    }
    return ret;
}


int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> M;
    for (int i = 1; i < n; ++i) { 
        int u, v; cin >> u >> v;
        ad[u].push_back(v);
        ad[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) cin >> h[i];
    
    dfs(1);
    { // init
        for (int i = 1; i <= n; ++i) { 
            fill(lazy[i], lazy[i] + 40 + 1, 1);
        }
    }
    
    cin >> q;
    while (q--) { 
        int type; cin >> type;
        
        if (type == 1) { 
            int u, d, x; cin >> u >> d >> x;
            upd(u, d, x);
        }

        if (type == 2) {
            int x; cin >> x;
            cout << get(x) << "\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