Submission #1274051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274051		tatas07	Sprinkler (JOI22_sprinkler)	C++20	0 / 100	925 ms	54472 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
#define long long int
vector<int> adj[200045];
int par[200045];
int h[200045];
void dfs(int u,int p){
    for(int next:adj[u]){
        if(next==p){
            continue;
        }
        par[next]=u;
        dfs(next,u);
    }
}
signed main(){
    int n,mod;
    cin>>n>>mod;
    for (int i = 1; i <= n-1; i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
    {
        cin>>h[i];
    }
    int dp[n+45][45];
    memset(dp,1,sizeof(dp));
    for (int i = 1; i <=40; i++)
    {
        adj[i+n].push_back(i+n-1);
        adj[i+n-1].push_back(i+n);
    }
    dfs(n+40,0);
    int q;
    cin>>q;
    while(q--){
        int jenis;
        cin>>jenis;
        if(jenis==1){
            int x,d,w;
            cin>>x>>d>>w;
            while (x!=0 && d>=0)
            {
                dp[x][d]*=w;
                dp[x][d]%=mod;
                d--;
                if(d>=0){
                    dp[x][d]*=w;
                    dp[x][d]%=mod; 
                }
                x=par[x];
            }
            
        }else{
            int x;
            int d=0;
            cin>>x;
            int res=h[x];
            while(x!=0 && d<=40){
                res*=dp[x][d];
                res%=mod;
                d++;
                x=par[x];
            }
            cout<<res<<endl;
        }
    }
}

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