Submission #905776

#	Time	Username	Problem	Language	Result	Execution time	Memory
905776		Tuanlinh123	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1086 ms	101776 KiB

sprinkler

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=200005;
ll h[maxn], pa[maxn], m[maxn][45];
vector <ll> A[maxn];

void dfs(ll u)
{
    for (ll v:A[u])
        if (v!=pa[u])
            pa[v]=u, dfs(v);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, Mod; cin >> n >> Mod;
    for (ll i=1; i<=n; i++)
        for (ll j=0; j<=40; j++)
            m[i][j]=1;
    for (ll i=1; i<n; i++)
    {
        ll u, v; cin >> u >> v;
        A[u].pb(v); A[v].pb(u);
    }
    dfs(1);
    for (ll i=1; i<=n; i++)
        cin >> h[i];
    ll q; cin >> q;
    for (ll i=1; i<=q; i++)
    {
        ll t, x; cin >> t >> x;
        if (t==1)
        {
            ll d, w; cin >> d >> w;
            while (d>=0 && x)
            {
                if (x==1)
                {
                    for (ll i=d; i>=0; i--)
                        m[x][i]=m[x][i]*w%Mod;
                    break;
                }
                m[x][d]=m[x][d]*w%Mod;
                if (d) m[x][d-1]=m[x][d-1]*w%Mod;
                d--, x=pa[x];
            }
        }
        else
        {
            ll dis=0, ans=h[x];
            while (dis<=40 && x)
            {
                ans=ans*m[x][dis]%Mod;
                dis++, x=pa[x];
            }
            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