Submission #1068754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068754		DucNguyen2007	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	513 ms	61328 KiB

sprinkler

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=2e5+5;
const ll inf=2e18;
int n,q,f[maxN+1][41],L,h[maxN+1],parent[maxN+1];
vector<int> adj[maxN+1];
void dfs(int u,int p)
{
    parent[u]=p;
    for(auto v:adj[u])
    {
        if(v!=p)
        {
            dfs(v,u);
        }
    }
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>L;
    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>>h[i];
        for(int j=0;j<=40;j++)
        {
            f[i][j]=1;
        }
    }
    dfs(1,0);
    cin>>q;
    while(q--)
    {
        int s;
        cin>>s;
        if(s==1)
        {
            int x,d,w;
            cin>>x>>d>>w;
            while(d>=0&&x>0)
            {
                if(x==1)
                {
                    while(d>=0)
                    {
                        f[x][d]=(1LL*f[x][d]*w)%L;
                        d--;
                    }
                }
                else
                {
                    f[x][d]=(1LL*f[x][d]*w)%L;
                    if(d>0)
                    {
                        f[x][d-1]=(1LL*f[x][d-1]*w)%L;
                    }
                }
                x=parent[x];
                d--;
            }
        }
        else
        {
            int x;
            cin>>x;
            int ans=h[x];
            int d=0;
            while(d<=40&&x>0)
            {
                ans=(1LL*ans*f[x][d])%L;
                x=parent[x];
                d++;
            }
            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