Submission #721410

#	Time	Username	Problem	Language	Result	Execution time	Memory
721410		lam	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	828 ms	95864 KiB

sprinkler

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
int n,mod,q;
vector <int> adj[maxn];
int a[maxn];
int par[maxn];
int dp[maxn][41];

void dfs(int x, int p)
{
    for (int i:adj[x])
        if (i!=p)
    {
        par[i]=x;
        dfs(i,x);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>mod;
    for (int i=1; i<n; i++)
    {
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,1);
    par[1]=0;
    for (int i=1; i<=n; i++) cin>>a[i];
    cin>>q;
    for (int i=1; i<=n; i++)
        for (int j=0; j<=40; j++) dp[i][j]=1LL;
    for (int i=1; i<=q; i++)
    {
        int t; cin>>t;
        if (t==1)
        {
            int x,d,w; cin>>x>>d>>w;
            for (int p = x; p>0&&d>=0; p=par[p], d--)
            {
                dp[p][d]=(dp[p][d]*w)%mod;
                if (d>0) dp[p][d-1]=(dp[p][d-1]*w)%mod;
            }
            for (d--; d>=0; d--)
            {
                dp[1][d]=(dp[1][d]*w)%mod;
            }
        }
        else
        {
            int x; cin>>x;
            int ans=a[x]%mod;
            for (int p=x, d=0; p>0&&d<=40; p=par[p], d++)
            {
                ans=(ans*dp[p][d])%mod;
            }
            cout<<ans<<'\n';
        }

    }
}

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