제출 #779198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
779198		boris_mihov	Sprinkler (JOI22_sprinkler)	C++17	9 / 100	4037 ms	51124 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 INF  = 1e9;

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

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

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

        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)
    {
        // std::cout << "update: " << l << ' ' << r << ' ' << node  << '\n' << std::flush;
        push(node, l, r);
        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);
    }

    int query(int l, int r, int node, int pos)
    {
        push(node, l, r);
        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 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 tourIN[MAXN];
int timer;

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;

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

        dfs(u, node);
    }

    out[node] = timer;
}

int findLeft(int node, int depth)
{
    int l = -1, r = byLevel[depth].size(), mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (in[byLevel[depth][mid]] < in[node]) l = mid;
        else r = mid;
    }

    return r;
}

int findRight(int node, int depth)
{
    int l = -1, r = byLevel[depth].size(), mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (in[byLevel[depth][mid]] <= out[node]) l = mid;
        else r = mid;
    }

    return l;
}

void updateLevel(int node, int depth, int val)
{
    // std::cout << "update level: " << node << ' ' << depth << ' ' << val << '\n' << std::flush;
    int l = findLeft(node, depth);
    int r = findRight(node, depth);
    // std::cout << "l, r: " << l << ' ' << r << '\n' << std::flush;
    if (l <= r)
    {
        assert(l >= 0);
        assert(r < byLevel[depth].size());
        // std::cout << "update: " << byLevel[depth][l] << ' ' << tourIN[byLevel[depth][l]] << ' ' << tourIN[byLevel[depth][r]] << '\n' << std::flush;
        tree.update(tourIN[byLevel[depth][l]], tourIN[byLevel[depth][r]], val);
    }
}

int recurse(int node, int depth, int w)
{
    // std::cout << "recurse: " << node << ' ' << depth << ' ' << w << '\n' << std::flush;
    if (node == 0 || depth < 0)
    {
        return 0;
    }

    int res = std::max(recurse(p[node], depth - 1, w), d[node]);
    for (int i = res ; i <= 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;
        // std::cout << "HERE: " << top << ' ' << d[top] << ' ' << tourIN[top] << '\n';

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

            queue.push(u);
        }
    }

    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;
        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
*/

컴파일 시 표준 에러 (stderr) 메시지

In file included from /usr/include/c++/10/cassert:44,
                 from sprinkler.cpp:4:
sprinkler.cpp: In function 'void updateLevel(int, int, int)':
sprinkler.cpp:166:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |         assert(r < byLevel[depth].size());
      |                ~~^~~~~~~~~~~~~~~~~~~~~~~

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