Submission #1267003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267003		hahahoang132	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	652 ms	89720 KiB

sprinkler

//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const ll N = 3e5 + 5;
const ll inf = LLONG_MAX/5;
#define bit(x,y) ((x >> y) & 1LL)

ll n,mod;
ll mul[50][N],h[N],p[N];
vector<ll> a[N];
void build(ll x, ll px)
{
    for(auto y : a[x])
    {
        if(y == px) continue;
        p[y] = x;
        build(y,x);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> mod;
    ll i,j;
    for(i = 1;i < n;i++)
    {
        ll u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }

    for(i = n + 40;i >= n + 2;i--)
    {
        a[i].push_back(i - 1);
        a[i - 1].push_back(i);
    }
    a[n + 1].push_back(1);
    a[1].push_back(n + 1);
    build(n + 40,0);
    for(i = 1;i <= n;i++) cin >> h[i];
    for(i = 0;i <= 40;i++)
    {
        for(j = 1;j <= n + 40;j++) mul[i][j] = 1;
    }
    ll q;
    cin >> q;
    for(i = 1;i <= q;i++)
    {
        ll qr;
        cin >> qr;
        if(qr == 1)
        {
            ll x,d,w;
            cin >> x >> d >> w;
            ll i,j;
            while(x != 0 && d >= 0)
            {
                mul[d][x] *= w;
                mul[d][x] %= mod;
                d--;
                if(d >= 0)
                {
                    mul[d][x] *= w;
                    mul[d][x] %= mod;
                }
                x = p[x];
            }
        }else
        {
            ll x;
            cin >> x;
            ll ans = h[x];
            ll d = 0;
            while(x != 0 && d <= 40)
            {
                ans *= mul[d][x];
                ans %= mod;
                x = p[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