Submission #1274210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274210		lechaa	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	1185 ms	100644 KiB

sprinkler

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

vector<int> par;
vector<vector<int>> g;

void fpar(int k, int p){
    par[k] = p;
    for(int i = 0; i < g[k].size(); i++){
        if(g[k][i] == p) continue;
        fpar(g[k][i], k);
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("a.in", "r", stdin);
    // freopen("pertahanan_6.out", "w", stdout);
    int n, l; cin >> n >> l;
    vector<vector<int>> dp(n+1, vector<int>(42, 1));
    par.resize(n+1);
    g.resize(n+1);
    for(int i = 0; i < n-1; i++){
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> h(n+1);
    for(int i = 1; i <= n; i++){
        cin >> h[i];
    }
    fpar(1, -1);
    int q; cin >> q;
    while(q--){
        int t; cin >> t;
        if(t == 1){
            int k, d, w; cin >> k >> d >> w;
            while(d >= 0 && k != -1){
                dp[k][d] *= w;
                dp[k][d]%=l;
                k = par[k];
                d--;
            }
        }else{
            int k; cin >> k;
            int ns = h[k];
            int ls = 0;
            for(int i = 0; i <= 40 && k != -1; i++){
                ns *= dp[k][i];
                ns%=l;
                ns *= dp[k][i+1];
                ls = i+2;
                ns%=l;
                k = par[k];
            }
            if(k == -1){
                for(int y = ls; y <= 40; y++){
                    ns *= dp[1][y];
                    ns%=l;
                }
            }
            cout << ns << "\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