Submission #1261475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261475		chikien2009	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	712 ms	89776 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, l, a, b, c, par[200000];
vector<int> g[200000];
long long v[200000][41], res;

inline void DFS(int node)
{
    for (auto & i : g[node])
    {
        if (i != par[node])
        {
            par[i] = node;
            DFS(i);
        }
    }
}

int main()
{
    setup();

    cin >> n >> l;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    for (int i = 0; i < n; ++i)
    {
        fill_n(v[i], 41, 1);
        cin >> v[i][0];
    }
    par[0] = -1;
    DFS(0);
    cin >> n;
    while (n--)
    {
        cin >> a;
        if (a == 1)
        {
            cin >> a >> b >> c;
            a--;
            while (0 <= b)
            {
                (v[a][b] *= c) %= l;
                if (--b < 0)
                {
                    break;
                }
                (v[a][b] *= c) %= l;
                if (a != 0)
                {
                    a = par[a];
                }
                else
                {
                    b--;
                }
            }
        }
        else
        {
            cin >> a;
            res = 1;
            a--;
            b = 0;
            while (a != -1 && b <= 40)
            {
                (res *= v[a][b]) %= l;
                a = par[a];
                b++;
            }
            cout << res << "\n";
        }   
    }
    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