Submission #576256

#	Time	Username	Problem	Language	Result	Execution time	Memory
576256		erekle	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	2128 ms	72740 KiB

sprinkler

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_D = 40;

int n;
vector<vector<int>> g;
vector<int> parent;
void dfs(int i) {
    for (int j : g[i]) {
        if (!parent[j]) parent[j] = i, dfs(j);
    }
}

int main() {
    int l;
    cin >> n >> l;
    g.resize(1+n);
    for (int i = 1; i < n; ++i) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    parent.resize(1+n);
    parent[1] = -1;
    dfs(1);
    parent[1] = 0;

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

    vector<vector<int>> multiplyDown(1+n, vector<int>(1+MAX_D, 1));
    // all nodes distance j below node i need to be multiplied by multiplyDown[i][j]
    int q; cin >> q;
    while (q--) {
        int t, x; cin >> t >> x;
        if (t == 1) {
            int d, w;
            // we do not want same node to be multiplied by multiple ancestors
            // so every node will only be multiplied by the highest node that can multiply it
            for (cin >> d >> w; d >= 0 && x; --d, x = parent[x]) {
                multiplyDown[x][d] = (long long)multiplyDown[x][d] * w % l;
                if (d) multiplyDown[x][d-1] = (long long)multiplyDown[x][d-1] * w % l;
                if (!parent[x]) {
                    for (int k = d-2; k >= 0; --k) {
                        multiplyDown[x][k] = (long long)multiplyDown[x][k] * w % l;
                    }
                }
            }
        } else {
            int v = h[x];
            for (int d = 0; d <= MAX_D && x; ++d, x = parent[x]) {
                v = (long long)v * multiplyDown[x][d] % l;
            }
            cout << v << endl;
        }
    }
    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