oj.uz

Submission #894064

# Submission time Handle Problem Language Result Execution time Memory
894064 2023-12-27T23:23:31 Z juliany2 Sprinkler (JOI22_sprinkler) C++17
9 / 100
 254 ms 101748 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 = 45;
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];
            (ans *= lz[x][0] * lz[x][1] % mod) %= mod;
            if (x > 1)
                (ans *= lz[p[x]][1]) %= mod;

            /*
            vector<int> a;
            int d = 0;
            for (; d < D - 1 && 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 Incorrect 2 ms 7772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 223 ms 87776 KB Output is correct
3 Correct 246 ms 96568 KB Output is correct
4 Correct 217 ms 100020 KB Output is correct
5 Correct 228 ms 96320 KB Output is correct
6 Correct 206 ms 95844 KB Output is correct
7 Correct 202 ms 96396 KB Output is correct
8 Correct 181 ms 96964 KB Output is correct
9 Correct 235 ms 101748 KB Output is correct
10 Correct 221 ms 101700 KB Output is correct
11 Correct 210 ms 95900 KB Output is correct
12 Correct 212 ms 96340 KB Output is correct
13 Correct 161 ms 96712 KB Output is correct
14 Correct 170 ms 97288 KB Output is correct
15 Correct 168 ms 96652 KB Output is correct
16 Correct 168 ms 97168 KB Output is correct
17 Correct 174 ms 97604 KB Output is correct
18 Correct 3 ms 8024 KB Output is correct
19 Correct 2 ms 8028 KB Output is correct
20 Correct 2 ms 8024 KB Output is correct
21 Correct 2 ms 8028 KB Output is correct
22 Correct 2 ms 8028 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 223 ms 87776 KB Output is correct
3 Correct 246 ms 96568 KB Output is correct
4 Correct 217 ms 100020 KB Output is correct
5 Correct 228 ms 96320 KB Output is correct
6 Correct 206 ms 95844 KB Output is correct
7 Correct 202 ms 96396 KB Output is correct
8 Correct 181 ms 96964 KB Output is correct
9 Correct 235 ms 101748 KB Output is correct
10 Correct 221 ms 101700 KB Output is correct
11 Correct 210 ms 95900 KB Output is correct
12 Correct 212 ms 96340 KB Output is correct
13 Correct 161 ms 96712 KB Output is correct
14 Correct 170 ms 97288 KB Output is correct
15 Correct 168 ms 96652 KB Output is correct
16 Correct 168 ms 97168 KB Output is correct
17 Correct 174 ms 97604 KB Output is correct
18 Correct 3 ms 8024 KB Output is correct
19 Correct 2 ms 8028 KB Output is correct
20 Correct 2 ms 8024 KB Output is correct
21 Correct 2 ms 8028 KB Output is correct
22 Correct 2 ms 8028 KB Output is correct
23 Correct 2 ms 7772 KB Output is correct
24 Incorrect 228 ms 96164 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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