Submission #793564

#	Time	Username	Problem	Language	Result	Execution time	Memory
793564		vjudge1	Sprinkler (JOI22_sprinkler)	C++17	12 / 100	814 ms	94948 KiB

sprinkler

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,l;
ll p[maxN],h[maxN];
ll q;
vector<ll>g[maxN];
void dfs(ll u,ll P=0)
{
    p[u]=P;
    for(int v:g[u])
    {
        if(v!=P) dfs(v,u);
    }
}
ll lazy[maxN][42];
void solve()
{
    cin >> n >> l;
    for(int i=1;i<n;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i=1;i<=n;i++) cin >> h[i];
    cin >> q;
    for(int i=1;i<=n;i++) for(int j=0;j<=41;j++) lazy[i][j]=1;
    dfs(1);
    while(q--)
    {
        ll t;
        cin >> t;
        if(t==1)
        {
            ll u,d,w;
            cin >> u >> d >> w;
            ll x=u;
            for(int i=0;i<=d;i++)
            {
                ll &k=lazy[x][d-i];
                k=k*w%l;
                if(x!=1&&d-i>0)
                {
                    lazy[x][d-i-1]=lazy[x][d-i-1]*w%l;
                }
                if(p[x]!=0) x=p[x];
            }
        }
        else
        {
            ll u;
            cin >> u;
            ll ans=h[u];
            for(int i=0;i<=41;i++)
            {
                ans=ans*lazy[u][i]%mod;
                if(p[u]==0) break;
                else u=p[u];
            }
            cout << ans<<'\n';
        }

    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

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