Submission #1224948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224948		minhpk	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	583 ms	105992 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;
    }
    if (par[cur]==0){
        for (int j=i-2;j>=0;j--){
             dp[cur][j]=dp[cur][j]* w % mod;
        }
        break;
    }
    cur = par[cur];
}

         }else{
             int x;
             cin >> x;
             int res=1;
             for (int i=0;i<=40;i++){
                  if (x==0){
                    break;
                  }
                  res=res*dp[x][i]%mod;
                  x=par[x];
             }
             cout << res << "\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