Submission #1013371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013371		12345678	Sprinkler (JOI22_sprinkler)	C++17	38 / 100	195 ms	34384 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

#define ll long long

ll n, u, v, q, l, h[nx], lz1[nx], lz2[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 w)
{
    h[u]=(h[u]*w)%l;
    if (pa[u]!=u) h[pa[u]]=(h[pa[u]]*w)%l;
    lz1[u]=(lz1[u]*w)%l;
}

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], lz1[i]=1, lz2[i]=1;
    dfs(1, 1);
    cin>>q;
    while (q--)
    {
        cin>>t;
        if (t==1)
        {
            cin>>x>>ds>>w;
            if (ds==0) h[x]=(h[x]*w)%l;
            else if (ds==1) update(x, w);
            else
            {
                if (pa[x]!=x) update(pa[x], w);
                else h[x]=(h[x]*w)%l;
                lz1[x]=(lz1[x]*w)%l;
                lz2[x]=(lz2[x]*w)%l;
            }
        }
        else
        {
            cin>>u;
            ll res=h[u];
            if (pa[u]!=u) 
            {
                res=(res*lz1[pa[u]])%l;
                if (pa[pa[u]]!=pa[u]) res=(res*lz2[pa[pa[u]]])%l;
            }
            cout<<res<<'\n';
        }
    }
}

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