oj.uz

Submission #704470

# Submission time Handle Problem Language Result Execution time Memory
704470 2023-03-02T07:25:42 Z piOOE Sprinkler (JOI22_sprinkler) C++17
0 / 100
 675 ms 64128 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, MOD;
    cin >> n >> MOD;

    vector<vector<int>> adj(n);

    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        a -= 1, b -= 1;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> parent(n, -1), depth(n);

    auto dfs = [&](auto self, int v) -> void {
        for (int to : adj[v]) {
            if (to != parent[v]) {
                depth[to] = depth[v] + 1;
                parent[to] = v;
                self(self, to);
            }
        }
    };

    dfs(dfs, 0);

    vector<int> h(n);

    for (int &x : h) {
        cin >> x;
    }

    int q;
    cin >> q;

    constexpr int maxD = 43;

    vector<array<int, maxD>> kek(n);

    for (int i = 0; i < n; ++i) {
        fill(kek[i].begin(), kek[i].end(), 1);
    }

    for (int i = 0; i < q; ++i) {
        int t, v;
        cin >> t >> v;
        v -= 1;

        if (t == 1) {
            int dist;
            ll weight;
            cin >> dist >> weight;

            while (v != 0 && dist > 0) {
                kek[v][dist] = weight * kek[v][dist] % MOD;
                kek[v][dist - 1] = weight * kek[v][dist - 1] % MOD;
                v = parent[v];
                dist -= 1;
            }

            for (int j = 0; j <= dist; ++j) {
                kek[v][j] = kek[v][j] * weight % MOD;
            }
        } else {
            int dist = 0, ans = h[v];

            while (v != -1 && dist <= maxD) {
                ans = 1LL * ans * kek[v][dist] % MOD;
                v = parent[v];
                dist += 1;
            }

            cout << ans << '\n';
        }
    }

    return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 568 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 524 ms 59140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 524 ms 59140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 666 ms 64084 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 675 ms 64128 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 568 KB Output isn't correct
5 Halted 0 ms 0 KB -