Submission #544574

#	Time	Username	Problem	Language	Result	Execution time	Memory
544574		Rafi22	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	619 ms	89048 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=200107,D=42;

vector<int>G[N];
int o[N];

void dfs(int v)
{
    for(auto u:G[v])
    {
        if(u==o[v]) continue;
        o[u]=v;
        dfs(u);
    }
}

ll T[N][D];
ll h[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q,a,b;
    cin>>n>>mod;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        G[a].pb(b);
        G[b].pb(a);
    }
    dfs(1);
    for(int i=n+1;i<n+41;i++) o[i]=i+1;
    o[1]=n+1;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n+41;i++)
    {
        for(int j=0;j<=41;j++) T[i][j]=1;
    }
    cin>>q;
    while(q--)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int x,d,w;
            cin>>x>>d>>w;
            for(int i=0;i<=d;i++)
            {
                T[x][d-i]=T[x][d-i]*w%mod;
                x=o[x];
            }
        }
        else
        {
            int x;
            cin>>x;
            ll ans=h[x];
            for(int i=0;i<41;i++)
            {
                ans=ans*T[x][i]%mod;
                ans=ans*T[x][i+1]%mod;
                x=o[x];
            }
            cout<<ans<<endl;
        }
    }

    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