Submission #1141231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141231		denislav	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	521 ms	85788 KiB

sprinkler

# include <iostream>
# include <vector>
# include <queue>
using namespace std;

const int MAX=2e5+11+40;

int n,q;
long long bgn[MAX],MOD;
vector<int> adj[MAX];

void read()
{
    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);
    }

    for(int i=1;i<=n;i++) cin>>bgn[i];
}

int up[MAX];

void dfs(int curr, int par)
{
    up[curr]=par;
    for(int nxt: adj[curr])
    {
        if(nxt==par) continue;
        dfs(nxt,curr);
    }
}

void tree_basics()
{
    dfs(1,0);
    up[1]=n+1;
    for(int i=n+1;i<=n+39;i++) up[i]=i+1;
}

long long source[41][MAX];

void update(int u, int power, long long w)
{
    for(int i=0;i<=power;i++)
    {
        int j=power-i;
        source[j][u]*=w;source[j][u]%=MOD;
        if(j==0) break;
        source[j-1][u]*=w;source[j-1][u]%=MOD;
        u=up[u];
    }
}

void query(int u)
{
    long long ans=bgn[u];
    for(int i=0;i<=40;i++)
    {
        ans*=source[i][u];ans%=MOD;
        u=up[u];
    }

    cout<<ans<<"\n";
}

void solve()
{
    for(int j=0;j<=40;j++)
    {
        for(int i=1;i<=n+40;i++) source[j][i]=1;
    }

    cin>>q;
    while(q--)
    {
        int tp;
        cin>>tp;

        if(tp==1)
        {
            int u,d,w;
            cin>>u>>d>>w;
            update(u,d,w);
        }
        else if(tp==2)
        {
            int u;
            cin>>u;
            query(u);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    read();
    tree_basics();
    solve();

    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