Submission #1121265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121265		dwuy	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	729 ms	63208 KiB

sprinkler

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

const int MX = 202020;
int n, q, MOD;
vector<int> G[MX];
int p[MX], h[MX], f[MX][41];

int add(int a, int b){
    return (a += b) + (a >= MOD? -MOD : a<0? MOD : 0);
}

int mul(int a, int b){
    return 1LL * a * b % MOD;
}

void dfs(int u){
    for(int v: G[u]) if(v != p[u]){
        p[v] = u;
        dfs(v);
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> MOD;
    for(int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=n+1; i<=n+40; i++){
        G[i].push_back(i + 1);
    }
    G[n+41].push_back(1);
    for(int i=1; i<=n; i++) cin >> h[i];
    dfs(n + 1);
    cin >> q;
    for(int i=0; i<MX; i++) for(int j=0; j<41; j++) f[i][j] = 1;
    while(q--){
        int oper;
        cin >> oper;
        if(oper == 1){
            int u, d, w;
            cin >> u >> d >> w;
            while(d>=0){
                f[u][d] = mul(f[u][d], w);
                if(d && u) f[u][d-1] = mul(f[u][d-1], w);
                u = p[u];
                d--;
            }
        }
        if(oper == 2){
            int u; cin >> u;
            int res = h[u];
            for(int i=0; i<=40; i++){
                res = mul(res, f[u][i]);
                u = p[u];
            }
            cout << res << '\n';
        }
    }

    return 0;
}

Compilation message (stderr)

sprinkler.cpp: In function 'int add(int, int)':
sprinkler.cpp:10:15: warning: operation on 'a' may be undefined [-Wsequence-point]
   10 |     return (a += b) + (a >= MOD? -MOD : a<0? MOD : 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