oj.uz

Submission #1105867

# Submission time Handle Problem Language Result Execution time Memory
1105867 2024-10-28T06:58:56 Z Perl32 Sprinkler (JOI22_sprinkler) C++14
3 / 100
 4000 ms 92276 KB 
//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template <class Info, class Merge = plus<Info>>
class SPT { //0-indexed, [l, r]
 public:
    int n;
    vector<vector<Info>> mat;
    const Merge merge;

    SPT(vector<Info> a, const Info x = Info()) : merge(Merge()) {
        n = static_cast<int>(a.size());
        int max_log = 32 - __builtin_clz(n);
        mat.resize(max_log);
        mat[0] = a;
        for (int j = 1; j < max_log; j++) {
            mat[j].resize(n - (1 << j) + 1);
            for (int i = 0; i <= n - (1 << j); i++) {
                mat[j][i] = merge(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    Info get(int from, int to) const {
        assert(0 <= from && from <= to && to <= n - 1);
        int lg = 32 - __builtin_clz(to - from + 1) - 1;
        return merge(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
    }
};

struct Info {
    int u, d;

    Info() = default;
    Info(int _u, int _d) : u(_u), d(_d) {}
};

Info operator+(const Info &a, const Info &b) {
    Info ret;
    if (a.d < b.d) ret = a;
    else ret = b;
    return ret;
}

const int K = 777;

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, L;
    cin >> n >> L;
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<Info> ord;
    vector<int> tin(n), dep(n);
    auto Dfs = [&](auto&& self, int u, int p) -> void {
        tin[u] = (int) ord.size();
        ord.push_back({u, dep[u]});
        for (auto to : g[u]) {
            if (to == p) continue;
            dep[to] = dep[u] + 1;
            self(self, to, u);
            ord.push_back({u, dep[u]});
        }
    };
    dep[0] = 0;
    Dfs(Dfs, 0, -1);
    SPT<Info> kek(ord);
    auto lca = [&](int u, int v) {
        u = tin[u], v = tin[v];
        if (u > v) swap(u, v);
        return kek.get(u, v).u;
    };
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    int q;
    cin >> q;
    for (int i = 0; i < q; i += K) {
        vector<array<int, 3>> lazy;
        for (int j = 0; j < min(q - i, K); ++j) {
            int t, u;
            cin >> t >> u;
            --u;
            if (t == 1) {
                int d, w;
                cin >> d >> w;
                lazy.push_back({u, d, w});
            } else {
                int cur = a[u];
                for (auto [x, y, w] : lazy) {
                    int dst = dep[u] + dep[x] - 2 * dep[lca(u, x)];
                    if (dst <= y) cur = (1ll * cur * w) % L;
                }
                cout << cur << '\n';
            }
        }
        for (auto& [x, y, w] : lazy) {
            queue<array<int, 3>> que;
            que.push({x, -1, 0});
            while (!que.empty()) {
                auto [u, p, d] = que.front(); que.pop();
                a[u] = (1ll * a[u] * w) % L;
                if (d == y) continue;
                for (auto to : g[u]) {
                    if (to == p) continue;
                    que.push({to, u, d + 1});
                }
            }
        }
    }
}

/*

 */

Compilation message

sprinkler.cpp: In function 'int main(int32_t, char**)':
sprinkler.cpp:106:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  106 |                 for (auto [x, y, w] : lazy) {
      |                           ^
sprinkler.cpp:113:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |         for (auto& [x, y, w] : lazy) {
      |                    ^
sprinkler.cpp:117:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |                 auto [u, p, d] = que.front(); que.pop();
      |                      ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 5 ms 592 KB Output is correct
6 Correct 6 ms 724 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 7 ms 592 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 2 ms 592 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 2 ms 608 KB Output is correct
28 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 470 ms 85120 KB Output is correct
3 Correct 678 ms 85792 KB Output is correct
4 Correct 735 ms 89964 KB Output is correct
5 Correct 934 ms 85376 KB Output is correct
6 Correct 890 ms 84824 KB Output is correct
7 Correct 894 ms 85604 KB Output is correct
8 Correct 759 ms 86252 KB Output is correct
9 Correct 388 ms 92276 KB Output is correct
10 Correct 526 ms 92124 KB Output is correct
11 Correct 458 ms 85112 KB Output is correct
12 Correct 552 ms 85656 KB Output is correct
13 Execution timed out 4054 ms 80736 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 470 ms 85120 KB Output is correct
3 Correct 678 ms 85792 KB Output is correct
4 Correct 735 ms 89964 KB Output is correct
5 Correct 934 ms 85376 KB Output is correct
6 Correct 890 ms 84824 KB Output is correct
7 Correct 894 ms 85604 KB Output is correct
8 Correct 759 ms 86252 KB Output is correct
9 Correct 388 ms 92276 KB Output is correct
10 Correct 526 ms 92124 KB Output is correct
11 Correct 458 ms 85112 KB Output is correct
12 Correct 552 ms 85656 KB Output is correct
13 Execution timed out 4054 ms 80736 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 728 ms 89244 KB Output is correct
3 Correct 1381 ms 88268 KB Output is correct
4 Correct 1000 ms 88184 KB Output is correct
5 Correct 2597 ms 82528 KB Output is correct
6 Execution timed out 4042 ms 78520 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 643 ms 89596 KB Output is correct
3 Correct 1417 ms 87044 KB Output is correct
4 Correct 1093 ms 88128 KB Output is correct
5 Correct 2576 ms 84144 KB Output is correct
6 Execution timed out 4064 ms 78528 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 5 ms 592 KB Output is correct
6 Correct 6 ms 724 KB Output is correct
7 Correct 6 ms 592 KB Output is correct
8 Correct 7 ms 592 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 2 ms 592 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 2 ms 608 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 470 ms 85120 KB Output is correct
31 Correct 678 ms 85792 KB Output is correct
32 Correct 735 ms 89964 KB Output is correct
33 Correct 934 ms 85376 KB Output is correct
34 Correct 890 ms 84824 KB Output is correct
35 Correct 894 ms 85604 KB Output is correct
36 Correct 759 ms 86252 KB Output is correct
37 Correct 388 ms 92276 KB Output is correct
38 Correct 526 ms 92124 KB Output is correct
39 Correct 458 ms 85112 KB Output is correct
40 Correct 552 ms 85656 KB Output is correct
41 Execution timed out 4054 ms 80736 KB Time limit exceeded
42 Halted 0 ms 0 KB -