Submission #544507

#	Time	Username	Problem	Language	Result	Execution time	Memory
544507		model_code	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1014 ms	52340 KiB

sprinkler

#include <array>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int D_MAX = 40;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;
    auto mul = [M](int a, int b) -> int { return int64_t(a) * b % M; };
    vector g(N, vector<int>{});
    for(int i = 0; i < N - 1; i++){
        int A, B;
        cin >> A >> B;
        A--; B--;
        g[A].push_back(B);
        g[B].push_back(A);
    }
    vector<int> parent(N);
    auto dfs = [&](int par, int x, auto dfs) -> void {
        parent[x] = par;
        for(int y : g[x]) if(y != par) dfs(x, y, dfs);
    };
    dfs(-1, 0, dfs);
    vector dp(N, array<int, D_MAX + 1>{});
    for(auto& v : dp) v.fill(1);
    for(int i = 0; i < N; i++) cin >> dp[i][0];
    int Q;
    cin >> Q;
    for(int t = 0; t < Q; t++){
        int type, x;
        cin >> type >> x;
        x--;
        if(type == 1){
            int d, c;
            cin >> d >> c;
            while(1){
                dp[x][d] = mul(dp[x][d], c);
                if(d-- == 0) break;
                dp[x][d] = mul(dp[x][d], c);
                if(x) x = parent[x];
                else if(d-- == 0) break;
            }
        }
        else{
            int ans = 1;
            for(int d = 0; d <= D_MAX && x >= 0; d++, x = parent[x]){
                ans = mul(ans, dp[x][d]);
            }
            cout << ans << '\n';
        }
    }
}

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