Submission #1105867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105867		Perl32	Sprinkler (JOI22_sprinkler)	C++14	3 / 100	4064 ms	92276 KiB

sprinkler

//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 (stderr)

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 / 3
• Subtask 2: 0 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17