Submission #894066

#	Time	Username	Problem	Language	Result	Execution time	Memory
894066		juliany2	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	871 ms	101912 KiB

sprinkler

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 2e5 + 7, D = 45;
int n, mod;
vector<int> adj[N];
int p[N];
ll h[N], lz[N][D];

void dfs(int v = 1) {
    for (int u : adj[v]) {
        if (u != p[v]) {
            p[u] = v;
            dfs(u);
        }
    }
}

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

    cin >> n >> mod;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++)
        cin >> h[i];

    dfs();

    for (int i = 1; i <= n; i++)
        fill(lz[i], lz[i] + D, 1);

    int q;
    cin >> q;

    while (q--) {
        int t;
        cin >> t;

        if (t == 1) {
            int x, d, w;
            cin >> x >> d >> w;

            for (; d >= 0 && x > 0; d--, x = p[x])
                (lz[x][d] *= w) %= mod;
        }
        else {
            int x;
            cin >> x;

            ll ans = h[x];

            vector<int> a;
            int d = 0;
            for (; d < D - 1 && x > 0; d++, x = p[x])
                a.push_back(x);

            reverse(all(a));

            for (int v : a) {
                d--;
                if (v == a.front()) {
                    for (int i = d; i < D; i++)
                        (ans *= lz[v][i]) %= mod;
                }
                else
                    (ans *= lz[v][d] * lz[v][d + 1] % mod) %= mod;
            }

            cout << ans << '\n';
        }
    }

    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