Submission #1013385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013385		12345678	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	588 ms	95352 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5, kx=41;

#define ll long long

ll n, u, v, q, l, h[nx], lz[kx][nx], pa[nx], t, x, ds, w;
vector<ll> d[nx];

void dfs(int u, int p)
{
    pa[u]=p;
    for (auto v:d[u]) if (v!=p) dfs(v, u);
}

void update(int u, ll ds, ll w)
{
    if (ds==0) return lz[0][u]=(lz[0][u]*w)%l, void(); 
    if (pa[u]==u) for (int i=0; i<=ds; i++) lz[i][u]=(lz[i][u]*w)%l;
    else lz[ds][u]=(lz[ds][u]*w)%l, lz[ds-1][u]=(lz[ds-1][u]*w)%l, update(pa[u], ds-1, w);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>l;
    for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    for (int i=1; i<=n; i++) cin>>h[i];
    for (int i=0; i<kx; i++) for (int j=1; j<=n; j++) lz[i][j]=1;
    dfs(1, 1);
    cin>>q;
    while (q--)
    {
        cin>>t;
        if (t==1) cin>>x>>ds>>w, update(x, ds, w);
        else
        {
            cin>>u;
            ll lvl=0, res=h[u];
            while (lvl<=40&&pa[u]!=u) res=(res*lz[lvl][u])%l, u=pa[u], lvl++;
            if (pa[u]==u&&lvl<=40) res=(res*lz[lvl][u])%l;
            cout<<res<<'\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