oj.uz

Submission #894062

# Submission time Handle Problem Language Result Execution time Memory
894062 2023-12-27T23:07:12 Z juliany2 Sprinkler (JOI22_sprinkler) C++17
0 / 100
 858 ms 93400 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 2e5 + 7, D = 41;
int n, mod;
vector<int> adj[N];
int p[N];
ll h[N], lz[N][D];

void dfs(int v = 1) {
    for (int u : adj[v]) {
        if (u != p[v]) {
            p[u] = v;
            dfs(u);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> mod;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++)
        cin >> h[i];

    dfs();

    for (int i = 1; i <= n; i++)
        fill(lz[i], lz[i] + D, 1);

    int q;
    cin >> q;

    while (q--) {
        int t;
        cin >> t;

        if (t == 1) {
            int x, d, w;
            cin >> x >> d >> w;

            for (; d >= 0 && x > 0; d--, x = p[x])
                (lz[x][d] *= w) %= mod;
        }
        else {
            int x;
            cin >> x;

            ll ans = h[x];

            vector<int> a;
            int d = 0;
            for (; d < D && x > 0; d++, x = p[x])
                a.push_back(x);

            reverse(all(a));

            for (int v : a) {
                d--;
                if (d == 0) {
                    for (int i = 0; i < D; i++)
                        (ans *= lz[v][i]) %= mod;
                }
                else
                    (ans *= lz[v][d] * lz[v][d + 1] % mod) %= mod;
            }

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

    return 0;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Incorrect 634 ms 89664 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Incorrect 634 ms 89664 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Incorrect 837 ms 92520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Incorrect 858 ms 93400 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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