Submission #704481

#	Time	Username	Problem	Language	Result	Execution time	Memory
704481		piOOE	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	717 ms	57272 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, MOD;
    cin >> n >> MOD;

    vector<vector<int>> adj(n);

    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        a -= 1, b -= 1;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> parent(n, -1), depth(n);

    auto dfs = [&](auto self, int v) -> void {
        for (int to : adj[v]) {
            if (to != parent[v]) {
                depth[to] = depth[v] + 1;
                parent[to] = v;
                self(self, to);
            }
        }
    };

    dfs(dfs, 0);

    vector<int> h(n);

    for (int &x : h) {
        cin >> x;
    }

    int q;
    cin >> q;

    constexpr int maxD = 40;

    vector<array<int, maxD + 1>> kek(n);

    for (int i = 0; i < n; ++i) {
        fill(kek[i].begin(), kek[i].end(), 1);
    }

    for (int i = 0; i < q; ++i) {
        int t, v;
        cin >> t >> v;
        v -= 1;

        if (t == 1) {
            int dist;
            ll weight;
            cin >> dist >> weight;

            while (v != 0 && dist > 0) {
                kek[v][dist] = weight * kek[v][dist] % MOD;
                kek[v][dist - 1] = weight * kek[v][dist - 1] % MOD;
                v = parent[v];
                dist -= 1;
            }

            for (int j = 0; j <= dist; ++j) {
                kek[v][j] = kek[v][j] * weight % MOD;
            }
        } else {
            int dist = 0, ans = h[v];

            while (v != -1 && dist <= maxD) {
                ans = 1LL * ans * kek[v][dist] % MOD;
                v = parent[v];
                dist += 1;
            }

            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