oj.uz

Submission #779225

# Submission time Handle Problem Language Result Execution time Memory
779225 2023-07-11T09:16:15 Z boris_mihov Sprinkler (JOI22_sprinkler) C++17
53 / 100
 4000 ms 133148 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 8 ms 10324 KB Output is correct
5 Correct 9 ms 10196 KB Output is correct
6 Correct 8 ms 10276 KB Output is correct
7 Correct 7 ms 10196 KB Output is correct
8 Correct 6 ms 10248 KB Output is correct
9 Correct 5 ms 9780 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9768 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 5 ms 9788 KB Output is correct
20 Correct 5 ms 9684 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 5 ms 9684 KB Output is correct
23 Correct 6 ms 9684 KB Output is correct
24 Correct 5 ms 9684 KB Output is correct
25 Correct 5 ms 9776 KB Output is correct
26 Correct 7 ms 9780 KB Output is correct
27 Correct 5 ms 9792 KB Output is correct
28 Correct 5 ms 9684 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 432 ms 109528 KB Output is correct
3 Correct 653 ms 106316 KB Output is correct
4 Correct 634 ms 120732 KB Output is correct
5 Correct 528 ms 107904 KB Output is correct
6 Correct 471 ms 107660 KB Output is correct
7 Correct 503 ms 108012 KB Output is correct
8 Correct 656 ms 109116 KB Output is correct
9 Correct 569 ms 129520 KB Output is correct
10 Correct 849 ms 124484 KB Output is correct
11 Correct 442 ms 109376 KB Output is correct
12 Correct 688 ms 106452 KB Output is correct
13 Correct 856 ms 107320 KB Output is correct
14 Correct 916 ms 107516 KB Output is correct
15 Correct 828 ms 106948 KB Output is correct
16 Correct 678 ms 106764 KB Output is correct
17 Correct 758 ms 106996 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 7 ms 9684 KB Output is correct
20 Correct 5 ms 9684 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 5 ms 9684 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 432 ms 109528 KB Output is correct
3 Correct 653 ms 106316 KB Output is correct
4 Correct 634 ms 120732 KB Output is correct
5 Correct 528 ms 107904 KB Output is correct
6 Correct 471 ms 107660 KB Output is correct
7 Correct 503 ms 108012 KB Output is correct
8 Correct 656 ms 109116 KB Output is correct
9 Correct 569 ms 129520 KB Output is correct
10 Correct 849 ms 124484 KB Output is correct
11 Correct 442 ms 109376 KB Output is correct
12 Correct 688 ms 106452 KB Output is correct
13 Correct 856 ms 107320 KB Output is correct
14 Correct 916 ms 107516 KB Output is correct
15 Correct 828 ms 106948 KB Output is correct
16 Correct 678 ms 106764 KB Output is correct
17 Correct 758 ms 106996 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 7 ms 9684 KB Output is correct
20 Correct 5 ms 9684 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 5 ms 9684 KB Output is correct
23 Correct 5 ms 9764 KB Output is correct
24 Correct 443 ms 109488 KB Output is correct
25 Correct 893 ms 106412 KB Output is correct
26 Correct 687 ms 126968 KB Output is correct
27 Correct 510 ms 107840 KB Output is correct
28 Correct 498 ms 107796 KB Output is correct
29 Correct 518 ms 107832 KB Output is correct
30 Correct 644 ms 109060 KB Output is correct
31 Correct 573 ms 122916 KB Output is correct
32 Correct 981 ms 124716 KB Output is correct
33 Correct 447 ms 109456 KB Output is correct
34 Correct 883 ms 106292 KB Output is correct
35 Correct 5 ms 9684 KB Output is correct
36 Correct 5 ms 9756 KB Output is correct
37 Correct 5 ms 9684 KB Output is correct
38 Correct 5 ms 9716 KB Output is correct
39 Correct 5 ms 9684 KB Output is correct
40 Correct 5 ms 9724 KB Output is correct
41 Correct 5 ms 9684 KB Output is correct
42 Correct 5 ms 9684 KB Output is correct
43 Correct 5 ms 9684 KB Output is correct
44 Correct 6 ms 9684 KB Output is correct
45 Correct 6 ms 9684 KB Output is correct
46 Correct 7 ms 9688 KB Output is correct
47 Correct 5 ms 9684 KB Output is correct
48 Correct 5 ms 9684 KB Output is correct
49 Correct 5 ms 9684 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9692 KB Output is correct
2 Correct 888 ms 126412 KB Output is correct
3 Correct 2492 ms 121264 KB Output is correct
4 Correct 1103 ms 130504 KB Output is correct
5 Correct 747 ms 115024 KB Output is correct
6 Correct 410 ms 114956 KB Output is correct
7 Correct 431 ms 115200 KB Output is correct
8 Correct 485 ms 116240 KB Output is correct
9 Correct 786 ms 128276 KB Output is correct
10 Correct 2430 ms 133148 KB Output is correct
11 Correct 474 ms 114668 KB Output is correct
12 Correct 1245 ms 115520 KB Output is correct
13 Correct 1090 ms 116232 KB Output is correct
14 Correct 1132 ms 117020 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9736 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 5 ms 9736 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 1305 ms 122132 KB Output is correct
3 Execution timed out 4067 ms 115780 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 8 ms 10324 KB Output is correct
5 Correct 9 ms 10196 KB Output is correct
6 Correct 8 ms 10276 KB Output is correct
7 Correct 7 ms 10196 KB Output is correct
8 Correct 6 ms 10248 KB Output is correct
9 Correct 5 ms 9780 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9768 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 5 ms 9788 KB Output is correct
20 Correct 5 ms 9684 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 5 ms 9684 KB Output is correct
23 Correct 6 ms 9684 KB Output is correct
24 Correct 5 ms 9684 KB Output is correct
25 Correct 5 ms 9776 KB Output is correct
26 Correct 7 ms 9780 KB Output is correct
27 Correct 5 ms 9792 KB Output is correct
28 Correct 5 ms 9684 KB Output is correct
29 Correct 5 ms 9684 KB Output is correct
30 Correct 432 ms 109528 KB Output is correct
31 Correct 653 ms 106316 KB Output is correct
32 Correct 634 ms 120732 KB Output is correct
33 Correct 528 ms 107904 KB Output is correct
34 Correct 471 ms 107660 KB Output is correct
35 Correct 503 ms 108012 KB Output is correct
36 Correct 656 ms 109116 KB Output is correct
37 Correct 569 ms 129520 KB Output is correct
38 Correct 849 ms 124484 KB Output is correct
39 Correct 442 ms 109376 KB Output is correct
40 Correct 688 ms 106452 KB Output is correct
41 Correct 856 ms 107320 KB Output is correct
42 Correct 916 ms 107516 KB Output is correct
43 Correct 828 ms 106948 KB Output is correct
44 Correct 678 ms 106764 KB Output is correct
45 Correct 758 ms 106996 KB Output is correct
46 Correct 4 ms 9684 KB Output is correct
47 Correct 7 ms 9684 KB Output is correct
48 Correct 5 ms 9684 KB Output is correct
49 Correct 5 ms 9684 KB Output is correct
50 Correct 5 ms 9684 KB Output is correct
51 Correct 5 ms 9764 KB Output is correct
52 Correct 443 ms 109488 KB Output is correct
53 Correct 893 ms 106412 KB Output is correct
54 Correct 687 ms 126968 KB Output is correct
55 Correct 510 ms 107840 KB Output is correct
56 Correct 498 ms 107796 KB Output is correct
57 Correct 518 ms 107832 KB Output is correct
58 Correct 644 ms 109060 KB Output is correct
59 Correct 573 ms 122916 KB Output is correct
60 Correct 981 ms 124716 KB Output is correct
61 Correct 447 ms 109456 KB Output is correct
62 Correct 883 ms 106292 KB Output is correct
63 Correct 5 ms 9684 KB Output is correct
64 Correct 5 ms 9756 KB Output is correct
65 Correct 5 ms 9684 KB Output is correct
66 Correct 5 ms 9716 KB Output is correct
67 Correct 5 ms 9684 KB Output is correct
68 Correct 5 ms 9724 KB Output is correct
69 Correct 5 ms 9684 KB Output is correct
70 Correct 5 ms 9684 KB Output is correct
71 Correct 5 ms 9684 KB Output is correct
72 Correct 6 ms 9684 KB Output is correct
73 Correct 6 ms 9684 KB Output is correct
74 Correct 7 ms 9688 KB Output is correct
75 Correct 5 ms 9684 KB Output is correct
76 Correct 5 ms 9684 KB Output is correct
77 Correct 5 ms 9684 KB Output is correct
78 Correct 5 ms 9692 KB Output is correct
79 Correct 888 ms 126412 KB Output is correct
80 Correct 2492 ms 121264 KB Output is correct
81 Correct 1103 ms 130504 KB Output is correct
82 Correct 747 ms 115024 KB Output is correct
83 Correct 410 ms 114956 KB Output is correct
84 Correct 431 ms 115200 KB Output is correct
85 Correct 485 ms 116240 KB Output is correct
86 Correct 786 ms 128276 KB Output is correct
87 Correct 2430 ms 133148 KB Output is correct
88 Correct 474 ms 114668 KB Output is correct
89 Correct 1245 ms 115520 KB Output is correct
90 Correct 1090 ms 116232 KB Output is correct
91 Correct 1132 ms 117020 KB Output is correct
92 Correct 5 ms 9684 KB Output is correct
93 Correct 5 ms 9684 KB Output is correct
94 Correct 5 ms 9736 KB Output is correct
95 Correct 4 ms 9684 KB Output is correct
96 Correct 5 ms 9736 KB Output is correct
97 Correct 4 ms 9684 KB Output is correct
98 Correct 1305 ms 122132 KB Output is correct
99 Execution timed out 4067 ms 115780 KB Time limit exceeded
100 Halted 0 ms 0 KB -