Submission #1224947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224947		minhpk	Sprinkler (JOI22_sprinkler)	C++20	50 / 100	574 ms	105976 KiB

sprinkler

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,mod;
vector <int> z[1000005];
int par[1000005];
int dp[250005][42];
void dfs(int i){
    for (auto p:z[i]){
         if (p==par[i]){
             continue;
         }
         par[p]=i;
         dfs(p);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> mod;
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    dfs(1);
    for (int i=0;i<=a;i++){
         for (int j=1;j<=40;j++){
             dp[i][j]=1;
         }
    }
    for (int i=1;i<=a;i++){
         cin >> dp[i][0];
    }
    int q;
    cin >> q;
    while (q--){
         int c;
         cin >> c;
         if (c==1){
             int x,d,w;
             cin >> x >> d >> w;
             int cur = x;
for (int i = d; i >= 0; i--) {
    dp[cur][i] = dp[cur][i] * w % mod;
    if (i > 0) {
        dp[cur][i-1] = dp[cur][i-1] * w % mod;
    }
    cur = par[cur];
}

         }else{
             int x;
             cin >> x;
             int res=1;
             for (int i=0;i<=40;i++){
                  res=res*dp[x][i]%mod;
                  x=par[x];
             }
             cout << res << "\n";
         }
    }
    return 0;
}

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