Submission #1148733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148733		ace5	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	505 ms	52868 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 200001;
const int maxd = 41;

vector<int> g[maxn];
int p[maxn];
int h[maxn];
int mn[maxd][maxn];

void add(int x,int d,int w,int L)
{
    x--;
    for(int j = 0;j <= d && x != -1;++j)
    {
        mn[d-j][x] = (ll(mn[d-j][x])*w)%L;
        x = p[x];
    }
}
int ans(int x,int L)
{
    x--;
    int res = h[x];
    for(int j = 0;j <= 40;++j)
    {
        res = (ll(res)*mn[j][x])%L;
        if(j != 40 && x != 0)
            res = (ll(res)*mn[j+1][x])%L;
        x = (x == 0 ? x : p[x]);
    }
    return res;
}
void dfs(int v,int pp)
{
    p[v] = pp;
    for(auto u:g[v])
    {
        if(u != pp)
            dfs(u,v);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,L;
    cin >> n >> L;
    for(int i = 0;i < n-1;++i)
    {
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 0;i <= 40;++i)
    {
        for(int j = 0;j < n;++j)
            mn[i][j] = 1;
    }
    dfs(0,-1);
    for(int i = 0;i < n;++i)
    {
        cin >> h[i];
    }
    int q;
    cin >> q;
    while(q--)
    {
        int t;
        cin >> t;
        if(t == 1)
        {
            int x,d,w;
            cin >> x >> d >> w;
            add(x,d,w,L);
        }
        else
        {
            int x;
            cin >> x;
            cout << ans(x,L) << "\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