Submission #704480

#	Time	Username	Problem	Language	Result	Execution time	Memory
704480		piOOE	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1002 ms	57664 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b; // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
};

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


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

    FastMod F(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] = F.reduce(weight * kek[v][dist]);
                kek[v][dist - 1] = F.reduce(weight * kek[v][dist - 1]);
                v = parent[v];
                dist -= 1;
            }

            for (int j = 0; j <= dist; ++j) {
                kek[v][j] = F.reduce(kek[v][j] * weight);
            }
        } else {
            int dist = 0;
            ll ans = h[v];

            while (v != -1 && dist <= maxD) {
                ans = F.reduce(ans * kek[v][dist]);
                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