Submission #1245166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245166		jasonic	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	736 ms	103712 KiB

sprinkler

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

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

ll n, MOD;
ll prods[200'005][50];
ll heights[200'005];
ll par[200'005];

vector<vector<int>> adjlist;

void dfs(int v, int p = -1) {
    par[v] = p;
    for(auto i : adjlist[v]) if(i != p) dfs(i, v);
}

int main() {
    fastIO;
    
    cin >> n >> MOD;
    adjlist = vector<vector<int>>(n);

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

    dfs(0);

    for(int i = 0; i < n; i++) cin >> heights[i];
    for(int i = 0; i < n; i++) for(int j = 0; j <= 40; j++) prods[i][j] = 1ll;

    int Q; cin >> Q;

    for(int q = 0; q < Q; q++) {
        int t; cin >> t;
        if(t == 1) {
            ll x, d, w; cin >> x >> d >> w; x--;

            while(d >= 0) {
                prods[x][d] = (prods[x][d] * w) % MOD;

                if(x != 0 && d != 0) prods[x][d-1] = (prods[x][d-1] * w) % MOD;
                if(x != 0) x = par[x];
                
                d--;
            }
            
        } else {
            int x; cin >> x; x--;
            // query
            ll ans = heights[x];
            int node = x;

            for(int i = 0; i <= 40; i++) {
                ans = (ans * prods[node][i]) % MOD;
                node = par[node];
                if(node == -1) break;
            }

            printf("%lld\n", ans);
        }
    }
    
    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