제출 #1274375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274375		warrenn	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	1126 ms	88616 KiB

sprinkler

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

const int maxn=2e5;
vector<int>adj[maxn+2];
int dp[maxn+2][42],par[maxn+2],h[maxn+2];
int n,mod;

int mul(int a,int b){
    return (a*b)%mod;
}

void dfs(int cur,int ort){
    par[cur]=ort;
    for(auto x : adj[cur]){
        if(x==ort)continue;
        dfs(x,cur);
    }
}

signed main(){
    cin>>n>>mod;
    for(int q=1;q<=n;q++){
        for(int w=0;w<=41;w++){
            dp[q][w]=1;
        }
    }
    for(int q=1;q<n;q++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,-1);
    for(int q=1;q<=n;q++)cin>>h[q];

    int qu;
    cin>>qu;
    while(qu--){
        int ty;
        cin>>ty;
        if(ty==1){
            int x,d,w;
            cin>>x>>d>>w;
            while(x!=-1 && d>=0){
                dp[x][d]=mul(dp[x][d],w);
                d--;
                x=par[x];
            }
        }
        else{
            int x;
            cin>>x;
            int ans=h[x];
            for(int q=0;q<=40;q++){
                if(x==1){
                    for(int w=q;w<=40;w++){
                        ans=mul(ans,dp[1][w]);
                    }
                    break;
                }
                else{
                    ans=mul(ans,dp[x][q]);
                    ans=mul(ans,dp[x][q+1]);
                    x=par[x];
                }
            }
            cout<<ans<<endl;
        }
    }

}

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