oj.uz

Submission #850809

# Submission time Handle Problem Language Result Execution time Memory
850809 2023-09-17T13:22:53 Z EJIC_B_KEDAX Sprinkler (JOI22_sprinkler) C++14
41 / 100
 4000 ms 141648 KB 
#include <bits/stdc++.h>
#include <random>

#ifndef LOCAL
    #pragma GCC optimize("O3")
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
typedef long long ll;
typedef double dd;
typedef long double ld;
typedef unsigned int uii;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()



void solve();

mt19937_64 mt(1);

int32_t main() {
#ifdef LOCAL
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //freopen("amusing.in", "r", stdin);
    //freopen("amusing.out", "w", stdout);
#endif
    cout << fixed << setprecision(30);
    int tests = 1;
    //cin >> tests;
    while (tests--) {
        solve();
    }
}

ll mod;

class SegmentTree {
public:
    void build(const vector<int>& b) {
        int sz = 1;
        while (sz < b.size()) {
            sz *= 2;
        }
        x.resize(2 * sz - 1);
        vn.resize(2 * sz - 1, 1);
        size = 2 * sz - 1;
        for (int i = sz - 1; i < 2 * sz - 1; i++) {
            if (i - sz + 1 < b.size()) {
                x[i] = b[i - sz + 1];
            } else {
                x[i] = 0;
            }
        }
        for (int i = sz - 2; i >= 0; i--) {
            //update(i);
            x[i] = 0;
        }
    }

    int get(int l, int r, int i = 0, int lx = 0, int rx = -1) {
        if (rx == -1) {
            rx = size / 2;
        }
        if (lx > r || rx < l) {
            return 0;
        }

        if (lx >= l && rx <= r) {
            return x[i];
        }

        updateVN(i);
        return get(l, r, 2 * i + 1, lx, (rx + lx) / 2) + get(l, r, 2 * i + 2, (rx + lx) / 2 + 1, rx);
    }

    void change(int ind, int c, int i = 0, int lx = 0, int rx = -1) {
        if (rx == -1) {
            rx = size / 2;
        }
        if (lx == rx) {
            x[i] = c;
            return;
        }
        updateVN(i);
        if ((rx + lx) / 2 >= ind) {
            change(ind, c, 2 * i + 1, lx, (rx + lx) / 2);
        } else {
            change(ind, c, 2 * i + 2, (rx + lx) / 2 + 1, rx);
        }
        //update(i);
    }
    void plusOtr(int l, int r, ll p, int i = 0, int lx = 0, int rx = -1) {
        if (r < l) {
            return;
        }
        if (rx == -1) {
            rx = size / 2;
        }
        if (lx >= l && rx <= r) {
            x[i] = (x[i] * p) % mod;
            vn[i] = (vn[i] * p) % mod;
            return;
        }
        if (lx > r || rx < l) {
            return;
        }
        updateVN(i);
        plusOtr(l, r, p, 2 * i + 1, lx, (rx + lx) / 2);
        plusOtr(l, r, p, 2 * i + 2, (rx + lx) / 2 + 1, rx);
        //update(i);
    }
private:
    vector<ll> x, vn;
    int size;
    void updateVN(int i) {
        if (2 * i + 2 < size) {
            if (vn[i] != 1) {
                x[2 * i + 1] = (x[2 * i + 1] * vn[i]) % mod;
                vn[2 * i + 1] = (vn[2 * i + 1] * vn[i]) % mod;
                x[2 * i + 2] = (x[2 * i + 2] * vn[i]) % mod;
                vn[2 * i + 2] = (vn[2 * i + 2] * vn[i]) % mod;
                vn[i] = 1;
            }
        }
    }
    void update(int i) {
        if (2 * i + 2 < size) {
            x[i] = x[2 * i + 1] + x[2 * i + 2];
        }
    }
};

pair<int, int> seg[200200][41];

void dfs(int s, int p, vector<vector<int>>& g, int dist[], vector<vector<int>>& d, int pr[]) {
    if (p != -1) {
        dist[s] = dist[p] + 1;
    } else {
        dist[s] = 0;
    }
    pr[s] = p;
    d[dist[s]].push_back(s);
    seg[s][0] = {d[dist[s]].size() - 1, d[dist[s]].size() - 1};
    for (int i = 1; i < 41; i++) {
        seg[s][i] = {INT32_MAX, INT32_MIN};
    }
    bool f = true;
    for (int i : g[s]) {
        if (i != p) {
            dfs(i, s, g, dist, d, pr);
            for (int j = 1; j < 41; j++) {
                seg[s][j].x = min(seg[s][j].x, seg[i][j - 1].x);
            }
            for (int j = 1; j < 41; j++) {
                seg[s][j].y = max(seg[s][j].y, seg[i][j - 1].y);
            }
        }
    }
}

void solve() {
    int n;
    cin >> n >> mod;
    vector<vector<int>> g(n), d(n);
    int deg[200200], dist[200200], h[200200], p[200200];
    for (int i = 0; i < n; i++) {
        deg[i] = 0;
    }
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v; u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    int root = 0;
    for (int i = 0; i < n; i++) {
        if (deg[i] == 1) {
            root = i;
            break;
        }
    }
    dfs(root, -1, g, dist, d, p);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d[i].size(); j++) {
            d[i][j] = h[d[i][j]];
        }
    }
    SegmentTree dec[200200];
    for (int i = 0; i < n; i++) {
        dec[i].build(d[i]);
    }
    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, dk, wk;
            cin >> x >> dk >> wk; x--;
            int nw = x, lev = 0, nlev = 0;
            for (int l = -dk; l <= dk; l++) {
                if (dist[x] - l < 0) {
                    break;
                }
                if (dist[x] - l >= n) {
                    continue;
                }
                int c = (dk + l) / 2;
                while (c > nlev) {
                    nlev++;
                    if (p[nw] != -1) {
                        lev++;
                        nw = p[nw];
                    }
                }
                if (c - l >= 0 && c - l <= dk) {
                    int l1, r1;
                    l1 = seg[nw][lev - l].x;
                    r1 = seg[nw][lev - l].y;
                    dec[dist[x] - l].plusOtr(l1, r1, wk);
                }
            }
        } else {
            int x;
            cin >> x; x--;
            cout << (dec[dist[x]].get(seg[x][0].x, seg[x][0].y) % mod + mod) % mod << '\n';
        }
    }
}

Compilation message

sprinkler.cpp: In member function 'void SegmentTree::build(const std::vector<int>&)':
sprinkler.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         while (sz < b.size()) {
      |                ~~~^~~~~~~~~~
sprinkler.cpp:57:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             if (i - sz + 1 < b.size()) {
      |                 ~~~~~~~~~~~^~~~~~~~~~
sprinkler.cpp: In function 'void dfs(int, int, std::vector<std::vector<int> >&, int*, std::vector<std::vector<int> >&, int*)':
sprinkler.cpp:156:10: warning: unused variable 'f' [-Wunused-variable]
  156 |     bool f = true;
      |          ^
sprinkler.cpp: In function 'void solve()':
sprinkler.cpp:198:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |         for (int j = 0; j < d[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 10 ms 14428 KB Output is correct
3 Correct 8 ms 14424 KB Output is correct
4 Correct 9 ms 16984 KB Output is correct
5 Correct 9 ms 16984 KB Output is correct
6 Correct 9 ms 16984 KB Output is correct
7 Correct 9 ms 16732 KB Output is correct
8 Correct 9 ms 16728 KB Output is correct
9 Correct 8 ms 14424 KB Output is correct
10 Correct 8 ms 14424 KB Output is correct
11 Correct 8 ms 14428 KB Output is correct
12 Correct 8 ms 14424 KB Output is correct
13 Correct 8 ms 14428 KB Output is correct
14 Correct 8 ms 14428 KB Output is correct
15 Correct 8 ms 14424 KB Output is correct
16 Correct 8 ms 14428 KB Output is correct
17 Correct 8 ms 14424 KB Output is correct
18 Correct 9 ms 14424 KB Output is correct
19 Correct 8 ms 14424 KB Output is correct
20 Correct 8 ms 14424 KB Output is correct
21 Correct 8 ms 14424 KB Output is correct
22 Correct 9 ms 14428 KB Output is correct
23 Correct 8 ms 14424 KB Output is correct
24 Correct 11 ms 14424 KB Output is correct
25 Correct 8 ms 14424 KB Output is correct
26 Correct 8 ms 14424 KB Output is correct
27 Correct 8 ms 14424 KB Output is correct
28 Correct 9 ms 14424 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14424 KB Output is correct
2 Correct 353 ms 120556 KB Output is correct
3 Correct 453 ms 117840 KB Output is correct
4 Correct 390 ms 140004 KB Output is correct
5 Correct 383 ms 119072 KB Output is correct
6 Correct 393 ms 119372 KB Output is correct
7 Correct 396 ms 118696 KB Output is correct
8 Correct 334 ms 118592 KB Output is correct
9 Correct 407 ms 141564 KB Output is correct
10 Correct 437 ms 138712 KB Output is correct
11 Correct 358 ms 120440 KB Output is correct
12 Correct 450 ms 117584 KB Output is correct
13 Correct 326 ms 118064 KB Output is correct
14 Correct 441 ms 119436 KB Output is correct
15 Correct 454 ms 118124 KB Output is correct
16 Correct 454 ms 118476 KB Output is correct
17 Correct 471 ms 117840 KB Output is correct
18 Correct 8 ms 14424 KB Output is correct
19 Correct 8 ms 14424 KB Output is correct
20 Correct 8 ms 14428 KB Output is correct
21 Correct 8 ms 14424 KB Output is correct
22 Correct 8 ms 14424 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14424 KB Output is correct
2 Correct 353 ms 120556 KB Output is correct
3 Correct 453 ms 117840 KB Output is correct
4 Correct 390 ms 140004 KB Output is correct
5 Correct 383 ms 119072 KB Output is correct
6 Correct 393 ms 119372 KB Output is correct
7 Correct 396 ms 118696 KB Output is correct
8 Correct 334 ms 118592 KB Output is correct
9 Correct 407 ms 141564 KB Output is correct
10 Correct 437 ms 138712 KB Output is correct
11 Correct 358 ms 120440 KB Output is correct
12 Correct 450 ms 117584 KB Output is correct
13 Correct 326 ms 118064 KB Output is correct
14 Correct 441 ms 119436 KB Output is correct
15 Correct 454 ms 118124 KB Output is correct
16 Correct 454 ms 118476 KB Output is correct
17 Correct 471 ms 117840 KB Output is correct
18 Correct 8 ms 14424 KB Output is correct
19 Correct 8 ms 14424 KB Output is correct
20 Correct 8 ms 14428 KB Output is correct
21 Correct 8 ms 14424 KB Output is correct
22 Correct 8 ms 14424 KB Output is correct
23 Correct 8 ms 14424 KB Output is correct
24 Correct 357 ms 120656 KB Output is correct
25 Correct 531 ms 118100 KB Output is correct
26 Correct 405 ms 140112 KB Output is correct
27 Correct 425 ms 118968 KB Output is correct
28 Correct 469 ms 119632 KB Output is correct
29 Correct 444 ms 119624 KB Output is correct
30 Correct 418 ms 118596 KB Output is correct
31 Correct 389 ms 141648 KB Output is correct
32 Correct 491 ms 138608 KB Output is correct
33 Correct 369 ms 120844 KB Output is correct
34 Correct 546 ms 117280 KB Output is correct
35 Correct 8 ms 14424 KB Output is correct
36 Correct 8 ms 14424 KB Output is correct
37 Correct 8 ms 14424 KB Output is correct
38 Correct 8 ms 14424 KB Output is correct
39 Correct 8 ms 14424 KB Output is correct
40 Correct 8 ms 14424 KB Output is correct
41 Correct 8 ms 14424 KB Output is correct
42 Correct 8 ms 14424 KB Output is correct
43 Correct 8 ms 14424 KB Output is correct
44 Correct 8 ms 14424 KB Output is correct
45 Correct 8 ms 14424 KB Output is correct
46 Correct 8 ms 14424 KB Output is correct
47 Correct 8 ms 14424 KB Output is correct
48 Correct 8 ms 14424 KB Output is correct
49 Correct 8 ms 14424 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14424 KB Output is correct
2 Correct 625 ms 139348 KB Output is correct
3 Correct 2322 ms 138332 KB Output is correct
4 Correct 943 ms 139064 KB Output is correct
5 Correct 1532 ms 117392 KB Output is correct
6 Correct 1645 ms 118200 KB Output is correct
7 Correct 1049 ms 118444 KB Output is correct
8 Correct 434 ms 117004 KB Output is correct
9 Correct 706 ms 139076 KB Output is correct
10 Correct 2530 ms 138308 KB Output is correct
11 Correct 878 ms 118228 KB Output is correct
12 Execution timed out 4042 ms 117140 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14428 KB Output is correct
2 Correct 673 ms 141564 KB Output is correct
3 Correct 2622 ms 138932 KB Output is correct
4 Correct 986 ms 139908 KB Output is correct
5 Correct 1746 ms 119124 KB Output is correct
6 Correct 1653 ms 119364 KB Output is correct
7 Correct 1058 ms 118204 KB Output is correct
8 Correct 403 ms 118588 KB Output is correct
9 Correct 621 ms 141648 KB Output is correct
10 Correct 2379 ms 138984 KB Output is correct
11 Correct 816 ms 120656 KB Output is correct
12 Execution timed out 4027 ms 118044 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 10 ms 14428 KB Output is correct
3 Correct 8 ms 14424 KB Output is correct
4 Correct 9 ms 16984 KB Output is correct
5 Correct 9 ms 16984 KB Output is correct
6 Correct 9 ms 16984 KB Output is correct
7 Correct 9 ms 16732 KB Output is correct
8 Correct 9 ms 16728 KB Output is correct
9 Correct 8 ms 14424 KB Output is correct
10 Correct 8 ms 14424 KB Output is correct
11 Correct 8 ms 14428 KB Output is correct
12 Correct 8 ms 14424 KB Output is correct
13 Correct 8 ms 14428 KB Output is correct
14 Correct 8 ms 14428 KB Output is correct
15 Correct 8 ms 14424 KB Output is correct
16 Correct 8 ms 14428 KB Output is correct
17 Correct 8 ms 14424 KB Output is correct
18 Correct 9 ms 14424 KB Output is correct
19 Correct 8 ms 14424 KB Output is correct
20 Correct 8 ms 14424 KB Output is correct
21 Correct 8 ms 14424 KB Output is correct
22 Correct 9 ms 14428 KB Output is correct
23 Correct 8 ms 14424 KB Output is correct
24 Correct 11 ms 14424 KB Output is correct
25 Correct 8 ms 14424 KB Output is correct
26 Correct 8 ms 14424 KB Output is correct
27 Correct 8 ms 14424 KB Output is correct
28 Correct 9 ms 14424 KB Output is correct
29 Correct 8 ms 14424 KB Output is correct
30 Correct 353 ms 120556 KB Output is correct
31 Correct 453 ms 117840 KB Output is correct
32 Correct 390 ms 140004 KB Output is correct
33 Correct 383 ms 119072 KB Output is correct
34 Correct 393 ms 119372 KB Output is correct
35 Correct 396 ms 118696 KB Output is correct
36 Correct 334 ms 118592 KB Output is correct
37 Correct 407 ms 141564 KB Output is correct
38 Correct 437 ms 138712 KB Output is correct
39 Correct 358 ms 120440 KB Output is correct
40 Correct 450 ms 117584 KB Output is correct
41 Correct 326 ms 118064 KB Output is correct
42 Correct 441 ms 119436 KB Output is correct
43 Correct 454 ms 118124 KB Output is correct
44 Correct 454 ms 118476 KB Output is correct
45 Correct 471 ms 117840 KB Output is correct
46 Correct 8 ms 14424 KB Output is correct
47 Correct 8 ms 14424 KB Output is correct
48 Correct 8 ms 14428 KB Output is correct
49 Correct 8 ms 14424 KB Output is correct
50 Correct 8 ms 14424 KB Output is correct
51 Correct 8 ms 14424 KB Output is correct
52 Correct 357 ms 120656 KB Output is correct
53 Correct 531 ms 118100 KB Output is correct
54 Correct 405 ms 140112 KB Output is correct
55 Correct 425 ms 118968 KB Output is correct
56 Correct 469 ms 119632 KB Output is correct
57 Correct 444 ms 119624 KB Output is correct
58 Correct 418 ms 118596 KB Output is correct
59 Correct 389 ms 141648 KB Output is correct
60 Correct 491 ms 138608 KB Output is correct
61 Correct 369 ms 120844 KB Output is correct
62 Correct 546 ms 117280 KB Output is correct
63 Correct 8 ms 14424 KB Output is correct
64 Correct 8 ms 14424 KB Output is correct
65 Correct 8 ms 14424 KB Output is correct
66 Correct 8 ms 14424 KB Output is correct
67 Correct 8 ms 14424 KB Output is correct
68 Correct 8 ms 14424 KB Output is correct
69 Correct 8 ms 14424 KB Output is correct
70 Correct 8 ms 14424 KB Output is correct
71 Correct 8 ms 14424 KB Output is correct
72 Correct 8 ms 14424 KB Output is correct
73 Correct 8 ms 14424 KB Output is correct
74 Correct 8 ms 14424 KB Output is correct
75 Correct 8 ms 14424 KB Output is correct
76 Correct 8 ms 14424 KB Output is correct
77 Correct 8 ms 14424 KB Output is correct
78 Correct 9 ms 14424 KB Output is correct
79 Correct 625 ms 139348 KB Output is correct
80 Correct 2322 ms 138332 KB Output is correct
81 Correct 943 ms 139064 KB Output is correct
82 Correct 1532 ms 117392 KB Output is correct
83 Correct 1645 ms 118200 KB Output is correct
84 Correct 1049 ms 118444 KB Output is correct
85 Correct 434 ms 117004 KB Output is correct
86 Correct 706 ms 139076 KB Output is correct
87 Correct 2530 ms 138308 KB Output is correct
88 Correct 878 ms 118228 KB Output is correct
89 Execution timed out 4042 ms 117140 KB Time limit exceeded
90 Halted 0 ms 0 KB -