Submission #779225

#	Time	Username	Problem	Language	Result	Execution time	Memory
779225		boris_mihov	Sprinkler (JOI22_sprinkler)	C++17	53 / 100	4067 ms	133148 KiB

sprinkler

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXD = 50;
const int INF = 1e9;

int n, MOD, q;
struct SegmentTree
{
    bool all[4*MAXN];
    int tree[4*MAXN];
    void build(int l, int r, int node, int vals[])
    {
        if (l == r)
        {
            tree[node] = vals[l];
            all[node] = (vals[l] == 0);
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node, vals);
        build(mid + 1, r, 2*node + 1, vals);
        all[node] = all[2*node] & all[2*node + 1];
        tree[node] = 1;
    }

    void push(int node, int l, int r)
    {
        if (tree[node] == 1)
        {
            return;
        }

        all[node] |= (tree[node] % MOD == 0);
        if (l < r)
        {
            tree[2*node] = (1LL * tree[2*node] * tree[node]) % MOD;
            tree[2*node + 1] = (1LL * tree[2*node + 1] * tree[node]) % MOD;
            tree[node] = 1;
        }
    }

    void update(int l, int r, int node, int queryL, int queryR, int val)
    {
        push(node, l, r);
        if (all[node])
        {
            return;
        }

        // std::cout << "update: " << l << ' ' << r << ' ' << node  << '\n' << std::flush;
        if (queryL <= l && r <= queryR)
        {
            tree[node] = (1LL * tree[node] * val) % MOD;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        if (queryL <= mid) update(l, mid, 2*node, queryL, queryR, val);
        if (mid + 1 <= queryR) update(mid + 1, r, 2*node + 1, queryL, queryR, val);
        all[node] = all[2*node] & all[2*node + 1];
    }

    int query(int l, int r, int node, int pos)
    {
        push(node, l, r);
        if (all[node])
        {
            return 0;
        }
        
        if (l == r)
        {
            return tree[node];
        }

        int mid = (l + r) / 2;
        if (pos <= mid) return query(l, mid, 2*node, pos);
        else return query(mid + 1, r, 2*node + 1, pos);
    }

    void build(int vals[])
    {
        build(0, n - 1, 1, vals);
    }

    void update(int l, int r, int val)
    {
        update(0, n - 1, 1, l, r, val);
    }

    int query(int pos)
    {
        return query(0, n - 1, 1, pos);
    }
};

int h[MAXN];
int p[MAXN];
int d[MAXN];
int maxD[MAXN];
int vals[MAXN];
SegmentTree tree;
std::queue <int> queue;
std::vector <int> tour;
std::vector <int> byLevel[MAXN];
std::vector <int> g[MAXN];
int in[MAXN], out[MAXN];
int tour2IN[MAXN];
int tourIN[MAXN];
int timer;

int leftIN[MAXN][MAXD];
int rightIN[MAXN][MAXD];

bool inSubtree(int x, int y)
{
    return in[y] <= in[x] && in[x] <= out[y];
}

void dfs(int node, int par)
{
    p[node] = par;
    d[node] = d[par] + 1;
    in[node] = ++timer;
    maxD[node] = d[node];

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

        dfs(u, node);
        maxD[node] = std::max(maxD[node], maxD[u]);
    }

    out[node] = timer;
}

void dfsIN(int node)
{
    leftIN[node][0] = tour2IN[node];
    rightIN[node][0] = tour2IN[node];

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

        dfsIN(u);
    }

    for (int i = 1 ; i < MAXD ; ++i)
    {
        leftIN[node][i] = INF;
        rightIN[node][i] = -INF;
        for (const int &u : g[node])
        {
            if (u == p[node])
            {
                continue;
            }

            leftIN[node][i] = std::min(leftIN[node][i], leftIN[u][i - 1]);
            rightIN[node][i] = std::max(rightIN[node][i], rightIN[u][i - 1]);
        }
    }
}

void updateLevel(int node, int depth, int val)
{
    int l = leftIN[node][depth - d[node]];
    int r = rightIN[node][depth - d[node]];
    if (l <= r)
    {
        tree.update(tourIN[byLevel[depth][l]], tourIN[byLevel[depth][r]], val);
    }
}

int recurse(int node, int depth, int w)
{
    if (node == 0)
    {
        return 0;
    }

    if (depth == 0)
    {
        tree.update(tourIN[node], tourIN[node], w);
        return d[node];
    }

    int res = std::max(recurse(p[node], depth - 1, w) + 1, d[node]);
    for (int i = res ; i <= std::min(maxD[node], d[node] + depth) ; ++i)
    {
        updateLevel(node, i, w);
    }

    return d[node] + depth;
}

void solve()
{
    dfs(1, 0);
    queue.push(1);

    while (queue.size())
    {
        int top = queue.front();
        queue.pop();

        byLevel[d[top]].push_back(top);
        tour.push_back(top);
        tourIN[top] = tour.size() - 1;
        tour2IN[top] = byLevel[d[top]].size() - 1;
        // std::cout << "HERE: " << top << ' ' << d[top] << ' ' << tourIN[top] << '\n';

        for (const int &u : g[top])
        {
            if (u == p[top])
            {
                continue;
            }

            queue.push(u);
        }
    }

    dfsIN(1);
    for (int i = 1 ; i <= n ; ++i)
    {
        vals[tourIN[i]] = h[i];
    }

    tree.build(vals);
    std::cin >> q;

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

        if (qType == 2)
        {
            int node;
            std::cin >> node;
            std::cout << tree.query(tourIN[node]) << '\n';
            continue;
        }

        assert(qType == 1);
        int node, depth, w;
        std::cin >> node >> depth >> w;
        if (w == 1) continue;
        recurse(node, depth, w);
    }
}

void input()
{
    std::cin >> n >> MOD;
    for (int i = 2 ; 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];
    }
}

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

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

/*
4 7
1 2
2 3
3 4
1
1
1
1
5
1 2 1 2
2 1
2 2
2 3
2 4
*/

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