Submission #1224767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224767		jerzyk	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	514 ms	91908 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;
#define st first
#define nd second
#define pb push_back
typedef long long ll;
typedef long double ld;
ll M;
const int N = 1<<18;
const int K = 42;
vector<int> ed[N];
int oj[N];
ll mn[N][K];

void DFS(int v)
{
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(oj[ed[v][i]]) continue;
        oj[ed[v][i]] = v;
        DFS(ed[v][i]);
    }
}

void Solve()
{
    int n, q, a, b;
    cin >> n >> M;
    ed[n + 1].pb(1);
    for(int i = 2; i <= 40; ++i)
        ed[n + i].pb(n + i - 1);
    for(int i = 1; i < n; ++i)
    {
        cin >> a >> b;
        ed[a].pb(b); ed[b].pb(a);
    }
    oj[n + 40] = n + 40;
    DFS(n + 40);
    for(int i = 1; i <= n + 40; ++i)
        for(int j = 0; j <= 40; ++j)
            mn[i][j] = 1LL;
    for(int i = 1; i <= n; ++i)
        cin >> mn[i][0];
    cin >> q;
    for(int i = 1; i <= q; ++i)
    {
        int r, a, d;
        ll x;
        cin >> r >> a;
        if(r == 2)
        {
            ll ans = 1LL;
            for(int l = 0; l <= 40; ++l)
            {
                ans = (ans * mn[a][l]) % M;
                a = oj[a];
            }
            cout << ans << "\n";
            continue;
        }
        cin >> d >> x;
        for(int l = 0; l <= d; ++l)
        {
            mn[a][d - l] = (mn[a][d - l] * x) % M;
            if(d - l > 0) mn[a][d - l - 1] = (mn[a][d - l - 1] * x) % M;
            a = oj[a];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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