Submission #561739

#	Time	Username	Problem	Language	Result	Execution time	Memory
561739		Jomnoi	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	851 ms	99572 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5 + 5;
const int MAX_D = 45;

int N, L;
int H[MAX_N];
vector <int> graph[MAX_N];
int parent[MAX_N];
long long keep[MAX_N][MAX_D];

void dfs(int u, int p) {
    for(auto v : graph[u]) {
        if(v != p) {
            parent[v] = u;
            dfs(v, u);
        }
    }
}

void update(int u, int d, int w) {
    while(u != 1 and d >= 0) {
        keep[u][d] = (keep[u][d] * w) % L;

        u = parent[u];
        d--;
    }
    while(d >= 0) {
        keep[1][d] = (keep[1][d] * w) % L;
        d--;
    }
}

int query(int u) {
    long long res = H[u];
    int d = 0;
    while(u != 0 and d <= 40) {
        res = (res * keep[u][d]) % L;
        if(u != 1 and d < 40) {
            res = (res * keep[u][d + 1]) % L;
        }

        u = parent[u];
        d++;
    }
    return res;
}

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

    cin >> N >> L;

    for(int i = 1; i <= N - 1; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i = 1; i <= N; i++) {
        cin >> H[i];
    }

    dfs(1, 0);

    for(int i = 0; i < MAX_N; i++) {
        for(int j = 0; j < MAX_D; j++) {
            keep[i][j] = 1;
        }
    }

    int Q;
    cin >> Q;

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

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

            update(x, d, w);
        }
        else {
            int x;
            cin >> x;

            cout << query(x) << '\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