Submission #928535

#	Time	Username	Problem	Language	Result	Execution time	Memory
928535		boris_mihov	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	644 ms	64896 KiB

sprinkler

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXD = 40 + 5;

int n, q, l;
int par[MAXN];
int multBy[MAXN][MAXD];
std::vector <int> g[MAXN];
int h[MAXN];

void dfs(int node, int p)
{
    par[node] = p;
    for (const int &u : g[node])
    {
        if (u == p)
        {
            continue;
        }

        dfs(u, node);
    }
}

void ennactQuery(int node, int d, int val)
{
    if (d < 0)
    {
        return;
    }

    multBy[node][d] = (1LL * multBy[node][d] * val) % l;
    if (d > 0) multBy[node][d - 1] = (1LL * multBy[node][d - 1] * val) % l;
    if (node != 1)
    {
        ennactQuery(par[node], d - 1, val);
    } else
    {
        for (int i = 0 ; i < d - 1 ; ++i)
        {
            multBy[node][i] = (1LL * multBy[node][i] * val) % l;
        }
    }
}

int answerQuery(int node, int d, int val)
{
    if (node == 0 || d > 40)
    {
        return val;
    }

    return answerQuery(par[node], d + 1, (1LL * val * multBy[node][d]) % l);
}

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        std::fill(multBy[i], multBy[i] + MAXD, 1);
    }

    dfs(1, 0);
    for (int i = 1 ; i <= q ; ++i)
    {
        int qType;
        std::cin >> qType;

        if (qType == 1)
        {
            int node, d, val;
            std::cin >> node >> d >> val;
            ennactQuery(node, d, val);
        } else
        {
            int node;
            std::cin >> node;
            std::cout << answerQuery(node, 0, h[node]) << '\n';
        }
    }
}

void input()
{
    std::cin >> n >> l;
    for (int i = 1 ; i < n ; ++i)
    {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> h[i];
    }

    std::cin >> q;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    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