Submission #1274054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274054		tatas07	Sprinkler (JOI22_sprinkler)	C++20	0 / 100	1087 ms	91672 KiB

sprinkler

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