Submission #1239854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239854		harvsftw	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	617 ms	65996 KiB

sprinkler

#pragma GCC optimize("O3,inline,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define F(i, n) for(int i = 0; i < (n); i++)
#define F_reverse(i, n) for(int i = (n - 1); i >= 0; i--)
#define FF(i, s, n) for(int i = (s); i < (n); i++)
#define dcout if(0) cout

#define N 200000
#define D 41


void skibidi() {
    int n, l;
    cin >> n >> l;

    vector<vector<int>> e(n);
    vector<int> parent(n);
    F(i, n - 1) {
        int u, v;
        cin >> u >> v;
        u--, v--;

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

    int (*val)[D] = (int (*)[D])malloc(sizeof(int) * n * D);
    F(i, n) {
        int init_val;
        cin >> init_val;
        val[i][0] = init_val;
        FF(j, 1, D) {
            val[i][j] = 1;
        }
    }

    function<void(int, int)> dfs = [&](int u, int p) {
        parent[u] = p;
        for(int v : e[u]) {
            if(v != p) {
                dfs(v, u);
            }
        }
    };

    dfs(0, -1);

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

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

            while(d >= 0) {
                //cout << "add condition that those at node " << (x + 1) << "'s depth " << og_d << " should be multiplied by " << w << endl;
                val[x][d] = (int64_t)val[x][d] * w % l;
                if(d > 0) {
                    val[x][d - 1] = (int64_t)val[x][d - 1] * w % l;
                }
                d--;
                if(parent[x] != -1) {
                    x = parent[x];
                } else {
                    // if staying on same node, subtract again since we already added that d
                    d--;
                }
            }
        } else {
            int x;
            cin >> x;
            x--;
            
            int ans = 1;
            F(i, D) {
                //cout << "that those at node " << (x + 1) << "'s depth " << i << " should be multiplied by " << val[x][i] << endl;
                ans = (int64_t)ans * val[x][i] % l;
                x = parent[x];
                if(x == -1) {
                    break;
                }
            }
            cout << (ans) << endl;
        }
    }


    free(val);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    //cin >> t;
    while(t--) skibidi();
}    

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17